CODEWITHSUNDEEP
haskell
Sara Takaya
Sara Takaya

Reputation: 298

Matrix Transpose with Tail Recursion Runs Forever

I am working on the transpose with matrix transpose but this wants to run forever. What am I doing wrong here?

transpose'' :: [[Int]] -> [[Int]] -> [[Int]]
transpose'' [] acc = acc
transpose'' m acc = transpose'' (map tail m) (acc ++ [map head m])

transpose' m = transpose'' m []

Now I have a check for empty sublist, but is there a more elegant way to do it?

transpose' :: [[Int]] -> [[Int]]
check m
    |head m == [] = []
    |otherwise    = m
transpose'' [] acc = acc
transpose'' m acc = transpose'' (check (map tail m)) (acc ++ [map head m])
transpose' m = transpose'' m []

Upvotes: 3

Views: 246

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153102

In this clause:

transpose'' m acc = transpose'' (map tail m) (acc ++ [map head m])

We know if we reach this clause, then m /= []. Observe that map tail m has the same length as m, hence in particular cannot be [], no matter what m is. Therefore the recursion cannot terminate.

To deal with this, you have a couple of options; one is to prune away empty sublists, and another is to use the first clause to check that all sublists are empty instead of checking that the list itself is empty. In either case, you will likely need to be more graceful about accepting lists with empty sublists; tail and head are bad functions to call on empty lists.

Upvotes: 4

Related Questions