Today’s Programming Praxis
problem was to
create a hash table with linear probing, but where the buckets are ordered. This
is easily done by using the insert, delete and find functions from
Data.List.
This means that inserts take longer, but that lookups (even unsuccessful ones) can – on average – terminate half-way through the list.
import Prelude hiding (lookup)
import qualified Data.Vector as V
import Data.Hashable (Hashable, hash)
import qualified Data.List as L (delete, find, insert)
import Data.Maybe (isJust, isNothing)
data HT a = HT (V.Vector [a]) deriving Show
empty :: (Hashable a, Ord a) => Int -> HT a
empty size = HT (V.replicate size [])
insert :: (Hashable a, Ord a) => HT a -> a -> HT a
insert (HT bs) e = let pos = hash e `mod` V.length bs
bucket = L.insert e $ bs V.! pos
in HT (V.update bs (V.singleton (pos,bucket)))
delete :: (Hashable a, Ord a) => HT a -> a -> HT a
delete (HT bs) e = let pos = hash e `mod` V.length bs
bucket = L.delete e $ bs V.! pos
in HT (V.update bs (V.singleton (pos, bucket)))
lookup :: (Hashable a, Ord a) => HT a -> a -> Maybe a
lookup (HT bs) e = let pos = hash e `mod` V.length bs
bucket = bs V.! pos
in L.find (==e) bucket
main :: IO ()
main = do
-- some simple tests
let ht = foldr (flip insert) (empty 10 :: HT Int) [0..99]
print . isNothing $ lookup ht 100
print . isJust $ lookup ht 50
print . isNothing $ lookup (delete ht 50) 50
print . all isNothing $ map (lookup (foldr (flip delete) ht [0..99])) [0..99]