来自 ST monad 的 Haskell 哈希表

Question

我正在尝试使用 Haskell St monad，但是不幸的是，我不明白如何将纯函数和这个 monad 结合起来。以下是需要计算文本中单个单词的程序示例，通过拆分单词并将它们添加到哈希表中。函数 count 尝试构建 HashMap。 Map 有简洁的（注释的）解决方案，具有 fromListWith，但是来自 ST monad 的可变 HashTable 没有这个，但它具有函数 mutate，可能可以执行构建 hashmap。不幸的是，我只能执行单个插入操作 示例：

    (do{ht <- H.new;H.mutate ht "abcd" (\v->case v of {
    Nothing ->(Just 1,"abcd");
    Just x ->(Just(x+1),"abcd")});
    return ht}) 

如果在foldl(r)内部执行则不起作用。将函数应用于累加器（哈希表）后，返回 ST monad 中的对象。我可以将标准循环函数与 ST 哈希表一起使用吗？或者有一些我不知道的一元运算符？

    {-# LANGUAGE TupleSections #-}
    import Data.Char(toLower)
    import Data.Hashable(Hashable)
    --import Data.HashMap(Map, fromListWith)
    import Text.Regex.TDFA
    import Control.Monad.ST;import Data.STRef
    import qualified Data.HashTable.ST.Basic as H
    import qualified Data.HashTable.Class as C
    type HashTable s k v = H.HashTable s k v
    st = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor             incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat     non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. "
    re = "[a-z0-9]+"
    --count :: (Hashable a, Ord a) => [a] -> Map a Int
    {-count = Map.fromListWith (+) . map (,1)-}
    count ws =do{ht <- H.new;
    foldl (\ht w -> H.mutate ht w
    (\v -> case v of 
      {Nothing ->(Just 1,w);
       Just x ->(Just(x+1),w)}
    )
          ) ht ws;
     return ht}
    --main = putStr $ show $ count (getAllTextMatches((map toLower st) =~ re) :: [String])

Answer 1

以下

count ws

的定义应该有效：

count :: [String] -> [(String, Int)]
count ws = runST $ do
  ht <- H.new
  mapM_ (\w -> H.mutate ht w $ \v -> case v of
            Nothing -> (Just 1, ())
            Just x -> (Just (x+1), ())) ws
  C.toList ht

注意有关此功能的几点：

• 为了将

  count

  编写为类型签名中没有

  ST

  的纯函数，它必须使用

  runST

  来实际执行变异

  do

  块，并且它不能返回

  H.Hashtable s String Int 类型的哈希表

  ，因为这种类型只能“存在”于

  ST

  monad 中。这就是为什么我们需要在末尾将最终结果转换为列表

  C.toList ht

  。

• H.mutate

  函数创建一个单子动作。具体来说，它有以下类型：

  H.mutate ht w f :: ST s a
  

  您不能将其折叠在哈希表上

  ht

  ，因为它不返回哈希表值。要处理这样的一元动作序列，您需要使用

  sequence

  、

  mapM

  、

  foldM

  等函数及其一些变体，您可以在

  Control.Monad

  中找到它们。在这种情况下，您有一个纯值列表

  ws :: [String]

  ，您希望将其转换为按顺序执行的一系列单子操作，并且

  mapM

  （或其变体

  mapM_

  ）将起作用。

  （请注意，我正在谈论

  mapM_

  中的

  Control.Monad

  ，而不是

  mapM_

  中出现的函数

  Data.Hashtable.Class

  。该哈希表版本有不同的用途，在这里没有用处。）

• 出现在元组后半部分的

  H.mutate

  的“返回值”（例如，

  w

  中的

  (Just 1, w)

  ）仅在您希望

  H.mutate

  从哈希表中读取信息时才重要。在

  H.mutate

  操作本身之外使用。这里，我们只需要在

  H.mutate

  操作中从哈希表中读取信息，来读取并递增计数器，因此这个返回值对我们来说没有用处。这就是为什么我们可以只返回单位值

  ()

  。

这是一个独立的示例，演示了此版本的

count

：

import Data.Char(toLower)
import Text.Regex.TDFA
import Control.Monad.ST
import qualified Data.HashTable.ST.Basic as H
import qualified Data.HashTable.Class as C

st :: String
st = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor \
     \incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud \
     \exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute \
     \irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla \
     \pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia \
     \deserunt mollit anim id est laborum."

re :: String
re = "[a-z0-9]+"

count :: [String] -> [(String, Int)]
count ws = runST $ do
  ht <- H.new
  mapM_ (\w -> H.mutate ht w $ \v -> case v of
            Nothing -> (Just 1, ())
            Just x -> (Just (x+1), ())) ws
  C.toList ht

main :: IO ()
main = putStrLn $ show $ count (getAllTextMatches (map toLower st =~ re))