How to transpose a 2D vector

Question

How to represent a 2d array integers in Haskell so that I can access any element with (i, j) in O(1) or O(logN)?

What's the difference between defining with Data.Array and Data.Vector? Which one is more practical

data Matrix = Vector (Vector Int)

If I define as the above, how to make a function that transposes this Matrix?

For instance: transposing a [[1,2,3],[4,5,6],[7,8,9]] would return [[1,4,7],[2,5,8],[3,6,9]]

Answer 1

Array and Vector have similar internal representations, but the API of Array is designed for indexing operations (through the Ix class) while Vector has a more list-like interface and relies on fusion to combine these operations efficiently. Both allow O(1) random access.

As an aside, Array is available in base while Vector is defined the vector package, so you can use Array if you wish to avoid an additional dependency.

In either case, transposition can be implemented in terms of indices. It’s perhaps slightly more natural using Array, which can be indexed by a pair to make a 2D array that’s guaranteed to be rectangular:

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
  ]

For Vector, you will just need to index twice:

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

Note that there is no guarantee that Vector (Vector a) is not a “jagged” 2D array, in which the inner vectors are of different lengths, like so:

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

This just means that you need to check that the input is well-formed. In addition, Vector (Vector a) is not contiguous in memory: it’s an array of pointers to vectors of elements, while an Array (Int, Int) a is a single block of memory, so Vector imposes a constant overhead with this representation. In case performance is a concern, you can remove this indirection by using a Vector a of length rows * cols and indexing it manually as row * cols + col; this is essentially what Array does internally via Ix.