HashTable.hs (1340B)
1 {-# OPTIONS_GHC -Wall #-} 2 3 -- Just working through the following for this one: 4 -- 5 -- http://hamberg.no/erlend/posts/2013-08-02-ordered-hash-table.html 6 7 module HashTable where 8 9 import Data.Hashable 10 import qualified Data.List as L 11 import Data.Vector (Vector, (!), unsafeIndex) 12 import qualified Data.Vector as V 13 import Prelude hiding (lookup) 14 15 newtype HashTable a = HashTable (Vector [a]) deriving Show 16 17 -- Exported functions ---------------------------------------------------------- 18 19 empty :: Int -> HashTable a 20 empty s = HashTable $ V.replicate s [] 21 22 insert :: (Hashable a, Ord a) => HashTable a -> a -> HashTable a 23 insert (HashTable bs) e = HashTable $ V.update bs (V.singleton (pos, bucket)) 24 where pos = position bs e 25 bucket = L.insert e $ bs `unsafeIndex` pos 26 27 delete :: (Hashable a, Ord a) => HashTable a -> a -> HashTable a 28 delete (HashTable bs) e = HashTable $ V.update bs (V.singleton (pos, bucket)) 29 where pos = position bs e 30 bucket = L.delete e $ bs `unsafeIndex` pos 31 32 lookup :: (Hashable a, Ord a) => HashTable a -> a -> Maybe a 33 lookup (HashTable bs) e = L.find (== e) bucket 34 where pos = position bs e 35 bucket = bs ! pos 36 37 -- Utilities ------------------------------------------------------------------- 38 39 position :: Hashable a => Vector b -> a -> Int 40 position bs e = hash e `mod` V.length bs 41