Haskell中的位数组修改？

Question

[我们都知道，以函数样式修改列表的成员非常慢（向量为O（n），树为O（log n）），因此ghc编译器中存在优化方法，可将该操作优化为就地修改？如果是这样，它需要什么情况？如果修改是在函数中进行的，并且您要修改的列表是其参数之一，它是否起作用？

Answer 1

否，编译器不会检测到纯数据结构的“修改”，而是将其转换为就地修改。如果您确实需要可变数组的性能特征，则必须显式使用它们（如Willem在评论中所述）。

Answer 2

我不完全确定O（log n）这么慢。实际上，O（log n）通常被视为“快速”。大多数数据库索引使用B-trees [wiki]或类似的数据结构。尽管大多数数据库都不会以类似功能的样式来更新树，但是插入，检索，更新，删除等的时间复杂度也是O（log n）。除非数据量确实真正达到巨大规模，否则O（log n）可能就足够了，因为当然可以合理地实现该算法。

大多数发行版附带的流行软件包是array [hackage]，它允许快速编辑数组。它使用array或IO monad，以便在容器“外部”仍然是纯净的，在引擎盖下，它当然可以对数组进行修改。

ST在Haskell wiki数组上有一个示例。在这里我们做：

ST

因此，我们首先创建一个边界为

buildPair :: ST s (Int, Int)
buildPair = do
    arr <- newArray (1,10) 37 :: ST s (STArray s Int Int)
    a <- readArray arr 1
    writeArray arr 1 64
    b <- readArray arr 1
    return (a,b)

的数组，然后使用(1,10)初始化所有元素。接下来，我们在第一行读取该值，然后将其更改为64，然后再次读取该值。

请注意，37本身会做[[not”修改，您可以将其视为获得2元组ST s (Int, Int)的配方。如果再使用(Int, Int)，我们将运行配方并产生结果。

例如：

runST :: (forall s . ST s a) -> a