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

Question

如果我要统计一个字符串中字符出现的次数，我可以在类似下面这样的命令式语言中使用数组轻松地实现：

char values[256]; char c;

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

我可以看到如何使用类似于 Data.Vector.Mutable 的 Haskell 包来实现 int-indexed 可变数组的快速实现。

但是如果没有额外的包和/或扩展，我该如何轻松地使用纯 Haskell 实现？换句话说，如何实现具有索引和可变性的快速 O(1) 集合？

- Jakub Arnold

---

你为什么想要不使用额外的包来完成呢？如果你需要一个可变数组，那么Data.Vector.Mutable正是为此而生！ - Tom Ellis

它可能是通过编译器内置函数实现的。如果您想自己实现类似的东西，您可能需要使用 FFI - 外部函数接口。这并不难，但对于新手来说可能看起来很奇怪。 - Sassa NF

@josejuan 这不是重复问题，参考的问题使用 vector 来解决。我所问的是如何实现一个具有类似于向量属性的数据结构。请阅读问题的更新标题。 - Jakub Arnold

你可以使用array包中的STUArray实现相同的（命令式）算法，该包与GHC一起提供。 - Alp Mestanogullari

我认为你会发现它最终使用了hackage.haskell.org/package/primitive-0.2.1/docs/src/Data-Primitive-Array.html - 在这里你可以看到像primitive_ (writeArray# arr# i# x)这样的东西。我不知道如何解析它们，但我敢打赌它们来自于GHC特定的内部函数。 - Sassa NF

Answer 1

vector 的实现使用了 GHC 内部的 primops 函数。你可以在预装在 GHC 中的 ghc-prim 包中找到它们。该包提供了以下数组函数：

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本身实现的，但它们非常低级。 primitive包提供了这些函数的更好的封装。对于数组，这些函数包括：

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 包，这个包更加优化（流融合等）且易于使用。

- bennofs