Skip to content

Instantly share code, notes, and snippets.

@nitrix
Last active November 8, 2015 11:00
Show Gist options
  • Select an option

  • Save nitrix/267bc0c42355e6c39983 to your computer and use it in GitHub Desktop.

Select an option

Save nitrix/267bc0c42355e6c39983 to your computer and use it in GitHub Desktop.
HashMap attempt in Haskell
import Data.Array
import Data.Maybe
import Data.Bits
type Hash = Integer
type HashMap k v = Array Hash [(k,v)]
hmCreate :: (Eq k, Show k) => HashMap k v -> k -> v -> HashMap k v
hmCreate hm k v = hm // [(hmHash hm k, after)]
where
before = hm ! hmHash hm k
after = maybe ((k,v) : before) (const before) $ hmRead hm k
hmRead :: (Eq k, Show k) => HashMap k v -> k -> Maybe v
hmRead hm k = lookup k $ hm ! hmHash hm k
hmUpdate :: (Eq k, Show k) => HashMap k v -> k -> v -> HashMap k v
hmUpdate hm k v = hm // [(hmHash hm k, after)]
where
before = hm ! hmHash hm k
after = maybe before go $ hmRead hm k
go x = (k,v) : filter ((/= k) . fst) before
hmRemove:: (Eq k, Show k) => HashMap k v -> k -> HashMap k v
hmRemove hm k = hm // [(hmHash hm k, after)]
where
before = hm ! hmHash hm k
after = filter ((/= k) . fst) before
hmInsert :: (Eq k, Show k) => HashMap k v -> k -> v -> HashMap k v
hmInsert hm k v = hmCreate (hmRemove hm k) k v
hmHash :: Show k => HashMap k v -> k -> Hash
hmHash hm k = foldl (\h c -> 33 * h `xor` (toInteger . fromEnum) c) 5381 (show k) `mod` mb
where
(lb,mb) = bounds hm
main = do
let x = array (0,100) [(i, []) | i <- [1..100]]
print $ hmRead (hmInsert x "hello" "world") "hello"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment