haskell - 如何在 Haskell 中实现具有 O(1) 索引和可变性的集合？

Question

如果我计算字符串中字符的出现次数，我可以使用命令式语言中的数组轻松实现这一点，例如:

char values[256]; char c;

while (c = readChar()) {
  values[c] += 1;
}

我可以看到如何在 Haskell 中使用类似 Data.Vector.Mutable 的东西来做到这一点。 ，它提供了 int 索引可变数组的快速实现。

但是我怎么能只使用 Haskell 而没有额外的包和/或扩展来轻松地做到这一点呢？ 换句话说，如何实现具有索引和可变性的快速 O(1) 集合？

Answer 1

vector的实现使用称为 primops 的内部 GHC 函数。您可以在包裹 ghc-prim 中找到它们。这是硬连线到 GHC。它提供了以下数组函数:

newArray# :: Int# -> a -> State# s -> (#State# s, MutableArray# s a#) 
readArray# :: MutableArray# s a -> Int# -> State# s -> (#State# s, a#)
writeArray# :: MutableArray# s a -> Int# -> a -> State# s -> State# s 

这些功能是由GHC自己实现的，但是真的很low。 primitive package 为这些函数提供了更好的包装。对于数组，它们是:

newArray :: PrimMonad m => Int -> a -> m (MutableArray (PrimState m) a) 
readArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> m a 
writeArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> a -> m () 

这是一个直接使用这些函数的简单示例(IO 是 PrimMonad):

import Data.Primitive.Array
import Control.Monad

main :: IO ()
main = do
  arr <- newArray 3 (0 :: Int)
  writeArray arr 0 1
  writeArray arr 1 3
  writeArray arr 2 7
  forM_ [0..2] $ \i -> putStr (show i ++ ":") >> readArray arr i >>= print

当然，在实践中你只需要使用 vector包，这是更加优化(流融合，...)，也更容易使用。