haskell 。在 O(1) 中更新单个 Vector 元素

Question

我想写一个函数来更新 O(1) 中的单个向量元素:

Vector Integer -> Int -> Integer -> Vector Integer
upd v ind x

通过复制整个向量来更新值很容易:

upd v ind x = v // [(ind,x)]

但这太慢了。

我创建一个矢量作为 Data.Vector.Generic.fromList 并且不卡住它。

为了就地修改向量，我找到了函数Data.Vector.modify、Data.Vector.Mutable.write 和 Data.Vector.Mutable.unsafeWrite，但我想不通如何使用它们中的任何一个。

当我尝试这样做时:

upd v ind x = do DVM.write v ind x

编译器提示:

Couldn't match type `()' with `Integer'
Expected type: DV.Vector Integer
  Actual type: DV.Vector ()
In the return type of a call of `DVM.write'
In a stmt of a 'do' block: DVM.write v ind x
In the expression: do { DVM.write v ind x }

(DV = Data.Vector，DVM = Data.Vector.Mutable)，

感谢任何帮助。我非常乐意获得使用 Data.Vector.modify 的示例。

Answer 1

首先请注意，带有单个表达式的 do block 始终与该表达式本身相同。所以你也可以写

upd v ind x = DVM.write v ind x

但这没有意义，原因有几个。

1. v 仍然是一个不可变向量。可变向量是完全不同的东西，它们是通过引用 PrimMonad 的状态来实现的——纯 Haskell 计算通常不需要类似的东西，因为引用透明性保证了状态总是相同的。当然，这正是阻止您在 O (1) 中进行更新的原因，并且没有真正的方法可以规避它。您需要输入其中一个 monad 才能获得此类更新。
2. 因为可变向量“隐藏”在 monad 的状态中，所以您不能简单地将它们作为函数结果单独返回。这会将状态泄露给纯功能语言，从而违反引用透明性。你有两个选择:
   • 将可变向量卡住为不可变向量，并将其作为结果返回。当然，这再次只能通过整个事情的副本¹ 安全地完成，因此与更简单的 // 解决方案相比，它不会给您带来任何好处。<
   • 只要您需要进行更新，就留在 monad 中。你永远不会卡住向量，它只是在可变状态下保持“ float ”。这意味着您不能拥有像 upd 这样的函数签名，而只需要使用 monadic 操作。正如 Louis Wasserman 所说，这正是 write 已经完成的工作，所以您真的不需要做任何更多的事情。 (这是有道理的:如果像您设想的 upd 这样的函数是可能的，那么它肯定已经在 vector 库中了。)

现在，这并没有完全解释如何使用可变向量，但要做到这一点，我们需要知道您希望使用 upd 的上下文。然而，在你完全改变之前:为什么你如此确定一个简单的纯更新会减慢你的目的？ vector 库非常擅长通过流融合“批处理”此类更新；如果您正在进行 O (n) 次独立更新，那么每个更新平均可以 O (1)，因为只有一个副本是为所有更新。

---

¹ _{解冻 当您将向量注入(inject) monad 以变为可变时，可能也已经需要一个副本。}