Data.Vector.modify 带有嵌套向量

Question

我有一个向量嵌套在另一个向量中。 I want to use modify 就地更新此矩阵。所以我将它用于内部向量，但我是否也需要将它用于外部向量？

Answer 1

我在评论中的建议仍然有效，如果您不需要对参差不齐的数组进行操作，那么通常的矩形数组实现会更好。以下是 vector of vector 的缺点的简短列表：

性能损失：外部向量必须装箱（这意味着额外的指针间接）
安全：您不能保证所有行的长度相同
在参差不齐的数组上操作很麻烦

尽管如此，问题仍然存在：您将如何就地修改向量的向量。下面我将提供一个示例函数，它使用突变来反转参差不齐的数组的行，以及另一个函数来反转行和列。不同之处在于，前者我们只改变每一行的元素，而后者我们还改变对应于行本身的外框向量：

{-# LANGUAGE RankNTypes #-}
import Control.Monad as M
import Control.Monad.ST
import Prelude as P
import Data.Vector as V
import Data.Vector.Generic.Mutable as VGM
import Data.Vector.Mutable as VM
import Data.Vector.Primitive as VP
import Data.Vector.Primitive.Mutable as VPM

raggedModifyRows ::
     VP.Prim a
  => (forall s. V.Vector (VPM.MVector s a) -> ST s ())
  -> V.Vector (VP.Vector a)
  -> V.Vector (VP.Vector a)
raggedModifyRows action arr = runST $ do
  -- thaw will create a copy of each row, so they can be safely modified
  mvs <- V.mapM VP.thaw arr
  action mvs
  -- We are freezing mutated copies, so it is safe to use unsafeFreeze here too
  V.mapM VP.unsafeFreeze mvs

raggedModify ::
     VP.Prim a
  => (forall s. VM.MVector s (VPM.MVector s a) -> ST s ())
  -> V.Vector (VP.Vector a)
  -> V.Vector (VP.Vector a)
raggedModify action arr = runST $ do
  arr' <- V.mapM VP.thaw arr
  -- mapM already created a copy of a boxed vector, so we can use unsafeThaw
  mv <- V.unsafeThaw arr'
  action mv
  v <- V.unsafeFreeze mv
  V.mapM VP.unsafeFreeze v

generateMatrix ::
     Prim a => (Int, Int) -> ((Int, Int) -> a) -> V.Vector (VP.Vector a)
generateMatrix (m, n) f = V.generate m $ \ i -> VP.generate n $ \j -> f (i, j)

generateRagged ::
     Prim a => V.Vector Int -> ((Int, Int) -> a) -> V.Vector (VP.Vector a)
generateRagged v f = V.imap (\ i n -> VP.generate n $ \j -> f (i, j)) v

reverseST :: (VGM.MVector v a) => v s a -> ST s ()
reverseST mv =
  let n = VGM.length mv
   in M.forM_ [0 .. (n `div` 2) - 1] $ \j -> VGM.swap mv j (n - j - 1)

reverseRaggedRows :: Prim a => V.Vector (VP.Vector a) -> V.Vector (VP.Vector a)
reverseRaggedRows = raggedModifyRows $ \rows -> V.forM_ rows reverseST

reverseRagged :: Prim a => V.Vector (VP.Vector a) -> V.Vector (VP.Vector a)
reverseRagged =
  raggedModify $ \mrows -> do
    let reverse' i = VM.read mrows i >>= reverseST
    let m = VM.length mrows
    M.forM_ [0 .. (m `div` 2) - 1] $ \i -> do
      reverse' i
      VM.swap mrows i (m - i - 1)
      reverse' i
    M.when (odd m) $ reverse' (m `div` 2)

可以这样使用：

λ> m = generateMatrix (3, 4) $ \(i, j) -> i+j
λ> m
[[0,1,2,3],[1,2,3,4],[2,3,4,5]]
λ> reverseRaggedRows m
[[3,2,1,0],[4,3,2,1],[5,4,3,2]]
λ> reverseRagged m
[[5,4,3,2],[4,3,2,1],[3,2,1,0]]
λ> m = generateRagged (V.fromList [1,2,3]) $ \(i, j) -> i+j
λ> m
[[0],[1,2],[2,3,4]]
λ> reverseRaggedRows m
[[0],[2,1],[4,3,2]]
λ> reverseRagged m
[[4,3,2],[2,1],[0]]

或者，我们可以使用 Data.Vector.modify 对外部向量进行操作，或者映射一个在所有行中使用 modify 的破坏性操作。有各种各样的方法可以解决这个问题，具体取决于您要实现的目标，例如：

λ> m = generateRagged (V.fromList [1,2,3]) $ \(i, j) -> i+j
λ> V.map (VP.modify reverseST) m
[[0],[2,1],[4,3,2]]
λ> V.modify reverseST (V.map (VP.modify reverseST) m)
[[4,3,2],[2,1],[0]]

我确实推荐使用 massiv for regular multidimensional arrays. Therefore here is also an example of how to achieve the same with withMArrayST:

{-# LANGUAGE FlexibleContexts #-}
import Control.Monad as M
import Data.Massiv.Array as A

reverseMatrix :: Mutable r Ix2 e => Array r Ix2 e -> Array r Ix2 e
reverseMatrix arr =
  withMArrayST arr $ \marr -> do
    let Sz2 m n = msize marr
        ix2@(m2 :. n2) = m `div` 2 :. n `div` 2
    A.forM_ (0 ..: ix2) $ \ix@(i :. j) -> do
      A.swapM_ marr ix (m - i - 1 :. n - j - 1)
      A.swapM_ marr (i :. n - j - 1) (m - i - 1 :. j)
    when (odd m) $ A.forM_ (0 ..: n2) $ \ j ->
      A.swapM_ marr (m2 :. j) (m2 :. n - j - 1)
    when (odd n) $ A.forM_ (0 ..: m2) $ \ i ->
      A.swapM_ marr (i :. n2) (m - i - 1 :. n2)

可以这样使用：

λ> a = makeArrayR P Seq (Sz2 3 4) $ \ (i :. j) -> i + j
λ> a
Array P Seq (Sz (3 :. 4))
  [ [ 0, 1, 2, 3 ]
  , [ 1, 2, 3, 4 ]
  , [ 2, 3, 4, 5 ]
  ]
λ> reverseMatrix a
Array P Seq (Sz (3 :. 4))
  [ [ 5, 4, 3, 2 ]
  , [ 4, 3, 2, 1 ]
  , [ 3, 2, 1, 0 ]
  ]

Data.Vector.modify 带有嵌套向量

Data.Vector.modify with nested vectors

haskell

haskell-vector