哈斯克尔.更新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具有单个表达式的块始终与该表达式相同.所以你也可以写

upd v ind x = DVM.write v ind x

但由于几个原因,这没有意义.

1. v仍然是一个不可变的向量.可变向量是完全不同的东西,它们是通过引用a的状态实现的PrimMonad- 纯Haskell计算通常不需要类似的东西,因为引用透明性保证状态始终是相同的.当然,这正是阻止你在O(1)中进行更新的原因,而且没有真正的方法来规避这一点.您需要输入其中一个monad才能获得此类更新.
2. 因为可变向量在monad状态中是"隐藏的",所以你不能简单地将它们作为函数结果单独返回.这会将状态泄露给纯函数式语言,从而违反参照透明度.您有两种选择:
   • 将可变向量冻结为不可变向量,返回结果.当然,这只能通过整个事物¹的副本安全地完成,所以它不会通过更简单的//解决方案获得任何东西.
   • 只要你需要做更新,就留在monad.你永远不会冻结向量,它只是在可变状态下"浮动".这意味着你不能拥有类似的函数签名upd,但只需要使用monadic动作.正如路易斯沃瑟曼说,这是究竟是什么write已经这样做,所以你真的不需要做任何事情更多.(这是有道理的:如果upd你想象的功能是可能的,那肯定会在vector库中.)

现在,这并不能解释如何使用可变向量,但要做到这一点,我们需要知道您希望使用的上下文upd.但是,在你变得可变之前:为什么你如此确定一个简单的纯更新会慢慢达到你的目的？该vector库非常适合通过流融合"批处理"这样的更新; 如果你正在进行O(n)个独立更新,那么每个人都可以获得O(1),因为只有一个副本用于所有更新.

¹ _{而解冻当你注入载体导入单子变成可变可能已经需要一个副本了.}