4

所以，这是我在 Haskell 中实现链式 HashTable 的笨拙代码。

{-# 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 k v = [(k, v)]

chainWith :: (Eq k) => Chain k v -> (k, v) -> Chain k v
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 k v -> k -> Chain k v
chainWithout cs k = filter ((/= k) . fst) cs 


data Hash k v = Hash {
    hashFunc   :: (k -> Integer)
  , chainTable :: Array Integer (Chain k v) 
} 

--type HState k v = State (Hash k v)

instance (Show k, Show v) => Show (Hash k v) where
    show = show . concat . elems . chainTable


type HashFuncForSize k = Integer -> k -> Integer

createHash :: HashFuncForSize k -> Integer -> Hash k v
createHash hs sz = Hash (hs sz) (array (1, sz) [(i, []) | i <- [1..sz]])


withSlot :: Hash k v -> k -> (Chain k v -> Chain k v) -> Hash k v
withSlot h k 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 k v -> (k, v) -> Hash k v
insert' h p@(k, v) = withSlot h k (flip chainWith p)


delete' :: (Eq k) => Hash k v -> k -> Hash k v
delete' h k = withSlot h k (flip chainWithout k)


insert :: (Eq k) => Hash k v -> Chain k v -> Hash k v
insert src pairs = foldl' insert' src pairs


delete :: (Eq k) => Hash k v -> [k] -> Hash k v
delete src keys = foldl' delete' src keys


search :: (Eq k) => k -> Hash k v -> Maybe v
search k h
    | rows < hashed = Nothing
    | otherwise     = k `lookup` (ht!hashed) 
  where hf     = hashFunc h
        ht     = chainTable h
        rows   = snd (bounds ht)
        hashed = hf k

问题是我不想编写这样的代码：

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

我相信它以某种方式用 State Monad 进行了修改，但是在阅读了在线教程后，我无法完全理解它是如何完成的。

所以你能告诉我如何至少实现插入、删除、搜索或其中任何一个来进行说明。

4

1 回答 1

4

在一天结束时，您的“状态”将是一个Hash k v. 让我们将接口函数分成两组。首先是“状态相关”函数，例如search k，它的类型类似于Hash k v -> _（_仅表示“某物”）。其次是“状态更新”功能flip insert (k, v)，flip delete ks例如Hash k v -> Hash k v.

正如您所指出的，您已经可以通过手动传递Hash k v参数来模拟“状态”。Statemonad 只不过是使这更容易的类型魔法。

如果你看Control.Monad.State你会看到modify :: (s -> s) -> State s ()和gets :: (s -> a) -> State s a。这些函数将您的“状态更新”和“状态相关”函数转换为“State单子动作”。所以现在我们可以像这样编写一个组合的Statemonad 动作

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

然后我们可以将更大的计算排序在一起

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

然后通过“运行”State单子来执行它们

runState computation (createHash f 100)
于 2013-05-23T02:57:53.660 回答