Haskell HashTable Helps Rewrite Using State Monad

Question

So, here is my awkward code implementing the HashTable chain in Haskell.

{-# LANGUAGE FlexibleInstances #-} import Data.Array(Array(..), array, bounds, elems, (//), (!)) import Data.List(foldl') import Data.Char import Control.Monad.State class HashTranform a where hashPrepare :: a -> Integer instance HashTranform Integer where hashPrepare = id instance HashTranform String where hashPrepare cs = fromIntegral (foldl' (flip ((+) . ord)) 0 cs) divHashForSize :: (HashTranform a) => Integer -> a -> Integer divHashForSize sz k = 1 + (hashPrepare k) `mod` sz type Chain kv = [(k, v)] chainWith :: (Eq k) => Chain kv -> (k, v) -> Chain kv chainWith cs p@ (k, v) = if (null after) then p:cs else before ++ p:(tail after) where (before, after) = break ((== k) . fst) cs chainWithout :: (Eq k) => Chain kv -> k -> Chain kv chainWithout cs k = filter ((/= k) . fst) cs data Hash kv = Hash { hashFunc :: (k -> Integer) , chainTable :: Array Integer (Chain kv) } --type HState kv = State (Hash kv) instance (Show k, Show v) => Show (Hash kv) where show = show . concat . elems . chainTable type HashFuncForSize k = Integer -> k -> Integer createHash :: HashFuncForSize k -> Integer -> Hash kv createHash hs sz = Hash (hs sz) (array (1, sz) [(i, []) | i <- [1..sz]]) withSlot :: Hash kv -> k -> (Chain kv -> Chain kv) -> Hash kv withSlot hk op | rows < hashed = h | otherwise = Hash hf (ht // [(hashed, op (ht!hashed))]) where hf = hashFunc h ht = chainTable h rows = snd (bounds ht) hashed = hf k insert' :: (Eq k) => Hash kv -> (k, v) -> Hash kv insert' h p@ (k, v) = withSlot hk (flip chainWith p) delete' :: (Eq k) => Hash kv -> k -> Hash kv delete' hk = withSlot hk (flip chainWithout k) insert :: (Eq k) => Hash kv -> Chain kv -> Hash kv insert src pairs = foldl' insert' src pairs delete :: (Eq k) => Hash kv -> [k] -> Hash kv delete src keys = foldl' delete' src keys search :: (Eq k) => k -> Hash kv -> Maybe v search kh | rows < hashed = Nothing | otherwise = k `lookup` (ht!hashed) where hf = hashFunc h ht = chainTable h rows = snd (bounds ht) hashed = hf k 

The problem is that I do not want this to be like this:

 new = intHash `insert` [(1112, "uygfd"), (211, "catdied")] new' = new `delete` [(1112, "uygfd")] 

I believe that it somehow changed with the help of State Monad, but after reading the online tutorials, I could not understand how exactly this is done.

So, you could show me how to implement at least insert, delete, search, or any of them to provide exposure.

Answer 1

At the end of the day, your “condition” will be Hash kv . Let me break down the interface functions into two groups. Firstly, these are state-dependent functions, such as search k , which is of type Hash kv -> _ (where _ just means “something”). Secondly, these are state update functions such as flip insert (k, v) and flip delete ks , which are of types like Hash kv -> Hash kv .

As you already noted, you can already simulate the “state” by manually bypassing the Hash kv argument. State Monad is nothing more than type magic to make this easier.

If you look at Control.Monad.State , you will see modify :: (s -> s) -> State s () and gets :: (s -> a) -> State sa . These functions transform your state update and state dependent functions into State monad actions. So now we can write the combined action of the State monad, like

 deleteIf :: (v -> Bool) -> k -> State (Hash kv) () deleteIf predicate k = do v <- gets $ search k case fmap predicate v of Nothing -> return () Just False -> return () Just True -> modify $ flip delete [k] 

and then we can combine the large computations sequentially

 computation = deleteIf (>0) 'a' >> deleteIf (>0) 'b' 

and then execute them by "launching" the State monad

 runState computation (createHash f 100)