如果我计算字符串中字符的出现次数,我可以使用命令式语言中的数组轻松实现这一点,例如:
char values[256]; char c;
while (c = readChar()) {
values[c] += 1;
}
我可以看到如何在 Haskell 中使用类似
Data.Vector.Mutable
的东西来做到这一点。 ,它提供了 int 索引可变数组的快速实现。但是我怎么能只使用 Haskell 而没有额外的包和/或扩展来轻松地做到这一点呢? 换句话说,如何实现具有索引和可变性的快速 O(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
包,这是更加优化(流融合,...),也更容易使用。
关于haskell - 如何在 Haskell 中实现具有 O(1) 索引和可变性的集合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27169611/