haskell - 如何转置二维向量

Question

如何在 Haskell 中表示二维数组整数，以便我可以在 O(1) 或 O(logN) 中使用 (i, j) 访问任何元素？

用 Data.Array 和 Data.Vector 定义有什么区别？哪个更实用

data Matrix = Vector (Vector Int)

如果我按照上面的定义，如何制作一个转置这个矩阵的函数？

例如:转置 [[1,2,3],[4,5,6],[7,8,9]]将返回 [[1,4,7],[2,5,8],[3,6,9]]

Answer 1

Array和 Vector有类似的内部表示，但是 Array 的 API设计用于索引操作(通过 Ix 类)，而 Vector有一个更像列表的界面，并依靠融合来有效地组合这些操作。两者都允许 O(1) 随机访问。

顺便说一句，Array可用 base而Vector定义为 vector包，所以你可以使用Array如果您希望避免额外的依赖。

在任何一种情况下，都可以根据索引来实现转置。使用 Array 可能更自然一些，它可以被一对索引以形成一个保证为矩形的二维数组:

import Data.Array (Array, (!))
import qualified Data.Array as Array

example1 :: Array (Int, Int) Char
example1 = Array.array ((0, 0), (1, 1))
  [ ((0, 0), 'a'), ((0, 1), 'b')
  , ((1, 0), 'c'), ((1, 1), 'd')
  ]

example2 :: Array (Int, Int) Int
example2 = Array.listArray ((0, 0), (2, 2))
  [ 1, 2, 3
  , 4, 5, 6
  , 7, 8, 9
  ]

transpose :: Array (Int, Int) a -> Array (Int, Int) a
transpose a = Array.array bounds
  [ ((row, col), a ! (col, row))
  | row <- [minRow .. maxRow]
  , col <- [minCol .. maxCol]
  ]
  where
    -- Note that indices need not be 0-based.
    bounds@((minRow, minCol), (maxRow, maxCol)) = Array.bounds a

transpose example1 == Array.array ((0, 0), (1, 1))
  [ ((0, 0), 'a'), ((0, 1), 'c')
  , ((1, 0), 'b'), ((1, 1), 'd')
  ]

Array.elems (transpose example2) ==
  [ 1, 4, 7
  , 2, 5, 8
  , 3, 6, 9
  ]

对于 Vector ，您只需要索引两次:

import Data.Vector (Vector, (!))
import qualified Data.Vector as Vector

-- Does not handle non-square arrays, nor
-- those with an outer dimension of zero.
transpose :: Vector (Vector a) -> Vector (Vector a)
transpose v = Vector.fromList
  [ Vector.fromList
    [ v ! col ! row
    | col <- [0 .. maxCol]
    ]
  | row <- [0 .. maxRow]
  ]
  where
    maxRow = Vector.length v - 1
    maxCol = Vector.length (v ! 0) - 1

请注意，不保证 Vector (Vector a)不是“锯齿状”二维数组，其中内部向量的长度不同，如下所示:

fromList
  [ fromList ['a', 'b']
  , fromList ['c']
  ]

这只是意味着您需要检查输入是否格式正确。此外， Vector (Vector a)在内存中不连续:它是一个指向元素向量的指针数组，而 Array (Int, Int) a是单个内存块，所以 Vector使用这种表示形式会产生恒定的开销。如果性能是一个问题，您可以使用 Vector a 删除此间接。长度 rows * cols并将其手动索引为 row * cols + col ;这本质上是 Array通过 Ix在内部进行.