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 块始终与该表达式本身相同。所以你也可以写

upd v ind x = DVM.write v ind x

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

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

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

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

Answer 2

您要的只是：

> :t modify (\mv ->  write mv 10 'a')
modify (\mv ->  write mv 10 'a') :: Vector Char -> Vector Char

>  modify (\mv ->  write mv 10 'a') (fromList "Hello good comrades")
fromList "Hello goodacomrades"

>   modify (\mv ->  unsafeWrite mv 0 100) (fromList [1..20::Integer])
fromList [100,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

并继续您提到的其他操作：

> :t  thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a'
thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a'
  :: Control.Monad.Primitive.PrimMonad m => m ()  -- i.e. IO or ST s

> :t  thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv
thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv
  :: Control.Monad.Primitive.PrimMonad m => m (Vector Char) 

> :t  thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv >>= print
thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv >>= print
  :: IO ()

> thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv >>= print
fromList "Hello goodacomrades"

现在为 runST

导入 Control.Monad.ST

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

> :t  thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a'
thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a'
 :: Control.Monad.Primitive.PrimMonad m => m ()  -- we will use ST s

> :t runST $ thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv
runST $ thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv
  :: Vector Char

> runST $ thaw (fromList "Hello good comrades") >>= \mv -> write mv 10 'a' >> freeze mv
fromList "Hello goodacomrades"

这就是为什么你给 runST 的论点就像你给 modify 的论点一样。

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

Haskell. update a single Vector element in O(1)

haskell

vector