Implementing the transpose of a matrix using only `!!` and `length`

Question

I'm trying to make up my mind on how to do a transpose of a matrix in Haskell using only !! and length. I have already written a function to get the column of a matrix at any given index i:

getCol :: [[Int]] -> Int -> [Int] 
getCol [] i = []
getCol (xs:xss) i = if isMatrix xss then (xs !! i) : getCol xss i else []

Plus, a function to return the length of a row:

rowLength :: [[Int]] -> Int
rowLength (x:xs) = length x

My plan right now is to fill a list n times with entries of getCol, with n being the rowLength of the list I call the function on.

So, for this sample list:

list = [[1,2,3],[4,5,6],[7,8,9]]

-- rowLength ---> 3
-- then fill another list with every column of list, 
--     for the indices 0..n (with n being rowLength)
-- resulting in [[1,4,7],[2,5,8],[3,6,9]

Problem is, I would normally do this with the head and tail functions, but I am only allowed to use length and !!.

My idea so far is

trav :: [[Int]] -> [[Int]]
trav xxs n = if (n <= rowLength) then getCol xxs n+1 : getCol xxs n else ?

my only issue is the else case. I know that it's mandatory in Haskell but I also know that my implementation doesn't make sense with an else case. This is my first time working with a functional language rather than an imperative one like Java, so I'm trying to somewhat simulate a loop here for the indices but don't know how to do that :(

Could anyone give me a tip? I would super appreciate that!!

Answer 1

You don't need (!!) or length; all you need is recursion, (:), and pattern matching.

transpose :: [[Int]] -> [[Int]]
transpose [] = []
transpose ([]:xss) = []
transpose m = let (h, t) = ht m in h : transpose t
  where
    ht :: [[Int]] -> ([Int], [[Int]])
    ht [] = ([], [])
    ht ((x:xs):xss) = let (hs, ts) = ht xss in (x:hs, xs:ts)

Try it online!

ht is a helper function that gives (heads, tails) for a list of [Int]. It's like doing (map head xss, map tail xss). The second equation takes a [[Int]] with a structure firstList:rest, finds the heads and tails (hs, ts) of the remaining lists rest, then appends the head and tail of firstList to hs and ts, respectively. The base case is with an empty matrix, where there are no more lists to find the heads and tails of.

The heads (the first element of the tuple) are the first column of the matrix (it's like doing map (!!0)). Thus, we have our first row h of the transposed matrix, and we prepend it to the result of transposing the rest of the columns (t, the tails). The base case is when all the inner lists are empty ([]:xss), so we return [], the empty matrix. All of the other lists are assumed to be empty - there is no verification that the input is indeed a matrix. Extra elements in rows will be silently ignored. The case transpose [] is only for transposing empty matrices.

Since (!!) and length are not particularly efficient for linked lists (the former is O(m) to find the element at index k, and the latter is O(n)), I'd recommend avoiding them.

However, if you really want to try indexing, think about how you would generate the indices first. You'd need two lists, one for the row numbers, one for the column numbers. Once you have those, you need to swap them (m!!i!!j becomes m!!j!!i if i is a row number and j is a column number). For that, you could try recursion, list comprehensions, or both.

Answer 2

Responding to my own question also because the solution was actually quite easier than I thought, using the functions I had already implemented myself.

trav :: [[Int]] -> [[Int]]
trav xss = transpose xss 0 

transpose :: [[Int]] -> Int -> [[Int]]
transpose xss n = if n < (rowLength xss) then getCol xss n : transpose xss (n+1)  else []

I didn't even realize that I don't need to simulate a loop. I had thought that in the transpose function, if it breaks down to the else-case eventually, it would merely return the empty list on its own. Little did I know this just puts it into the list that was already getting built up by the recursion!

Try it out :)

Answer 3

This is not what you asked about, and not at the level you're currently interested in, but as a curiosity this can also be defined as a one-liner,

transp :: Traversable t => t [a] -> [[a]]
--   or,                   [[a]] -> [[a]]
transp  =  takeWhile (not . null) . unfoldr (Just . traverse (splitAt 1))