I have a 2d list l, and

[l!!y!!x| x<-[0..length l-1], y<-[0..length l-1]]

will produce a 1d list where rows and columns are swapped.

How can I implement this without list comprehension(i.e. using map)?

CodePudding user response：

Since you wanted it without explicit recursion,

zipWith is also a binary map of sorts (and in some other languages map actually can take any number of argument lists). Hence,

transposed = foldr (zipWith (:)) (repeat [])

Trying it:

> transposed [[1,2,3],[11,12,13],[21,22,23,24]]
[[1,11,21],[2,12,22],[3,13,23]]

This can be simply composed with concat :: [[a]] -> [a] to concatenate the transposed lists.

CodePudding user response：

We can work with recursion for this: each time we yield the heads of the lists, and then recurse on the tails, so:

catTranspose :: [[a]] -> [a]
catTranspose ([]:_) = []
catTranspose xs = map head xs    …

where I leave filling in … as an exercise. It should make a recursive call where we map each item in xs to its tail.

If the list is rectangular, this will work, for non-rectangular 2d lists, you will need to work with functions that are more safe, and thus will not error like head does on an empty list.

One can also drop the explicit recursion and work for example with unfoldr :: (b -> Maybe (a, b)) -> b -> [a] and concat :: Foldable f => f [a] -> [a] that will then perform the recursion.

CodePudding user response：

Break down the problem into parts. To transpose a single row, you want to return a column where each row contains a single element.

transpose [row] = map (\ x -> [x]) row

E.g.: transpose [[1, 2, 3]] = [[1], [2], [3]].

\ x -> [x] can also be written as an operator section (: []) or pure from Applicative.

When you match on the outer list (input rows), you split the top row of the matrix from the remaining rows. The transpose of a matrix is the transposition of the first row prepended to the transposition of the remaining rows. You can join two matrices vertically with ( ) (or (<>) from Semigroup) or horizontally with zipWith ( ) (resp. zipWith (<>)).

transpose (top : down)
  = zipWith (  ) (transpose [top]) (transpose down)

E.g.: transpose [[1, 2], [3, 4], [5, 6]] = [[1] [3, 5], [2] [4, 6]].

This can also be expressed as zipWith (:) top (transpose down) since we know we have single elements to prepend; this skips some of the redundant effort of wrapping and then immediately unwrapping the elements of the input row / output column.

Finally, the transposition of an empty matrix with no rows is also the empty matrix.

transpose [] = []

Putting these together:

transpose :: [[a]] -> [[a]]
transpose [r] = map (: []) r
transpose (r : rs) = zipWith (:) r (transpose rs)
transpose [] = []

Follow-up: consider how this code responds to the edge cases where the input is non-rectangular or has an infinite number of rows or columns.

As Will Ness’s answer makes clear, this recursive function is nearly equivalent to a right fold, where the combining function is prepending of columns by zipWith (:), and the base accumulator is the empty column of indefinite height, repeat [], i.e. transpose m = foldr (zipWith (:)) (repeat []) m, or eta-reduced, transpose = foldr (zipWith (:)) (repeat []). However, they differ in an edge case: it produces an infinite list when given an empty input. That version is also equivalent to getZipList . traverse ZipList, based on the observation that traverse id :: (Traversable t, Applicative f) => t (f b) -> f (t b) is a kind of generalised transposition.