Implementing Transpose

Question

I'm implementing transpose in Haskell.

-- transpose [[1,2,3],[4,5,6],[7,8,9]]  
-- [[1,4,7],[2,5,8],[3,6,9]]

Please give it a look. Note that I'm trying not to use any built-in functions (excluding map and ++):

transpose' :: [[a]] -> [[a]]
transpose' ys
   | null $ filter (not . null) ys = []
   | otherwise = [flatten' $ map head' ys] ++ transpose' (map tail' ys)

head' :: [a] -> [a]
head' []     = []
head' (x:xs) = [x]

tail' :: [a] -> [a]
tail' []     = []
tail' (x:xs) = xs

flatten' :: [[a]] -> [a]
flatten' as = foldl (\acc x -> acc ++ x)  [] as

Side note - I know that I could look at the Haskell source, but I appreciate the comments & thoughtful insights here.

Answer 1

I see a few problems, mostly similar to my remarks in a previous answer:

1. Your definition of head' is unconventional. Its definition should be

   head' :: [a] -> a
   head (x:_) = x
   

   Furthermore, your problematic definition of head' is making you define flatten'. If you fix head' as suggested above, thenflatten' becomes unnecessary.

2. The definition of tail' is too complicated. It could just be

   tail' :: [a] -> [a]
   tail (_:xs) = xs
   

3. For clarity, I would rename the parameter to transpose' from ys to rows.

4. The base case of transpose' is too complicated. Also, it can be done using pattern matching.

   transpose' [[]]    = []
   transpose' [[], _] = []
   

5. Prefer x:xs to [x] ++ xs.

6. Scope your helper functions using where.

Here's what I came up with:

transpose' :: [[a]] -> [[a]]
transpose' [[]]    = []
transpose' [[], _] = []
transpose' rows    = (map head' rows) : transpose' (map tail' rows)
  where
    head' (x:_) = x
    tail' (_:xs) = xs

Answer 2

Good job doing it the hard way. Definitely take a peek at the implementations of functions in base after you're done rewriting them though, understanding the "canonical" implementation will do a lot to help you develop an idiomatic style.

1. Your definition of head' is non-standard. Here's the signature of head from the Prelude.

   head :: [a] -> a
   

   Your version isn't wrong per se, it's valid to return a list of 0 elements for a computation that may fail, but usually only when success will return 1 or more elements. The standard way to write safeHead is to encode failure using Maybe like so.

   head' :: [a] -> Maybe a
   head' []    = Nothing
   head' (x:_) = Just x
   

   This is the 'smallest' correct definition, in the sense of not including additional unnecessary functionality.

2. Replace the identifiers for unused arguments/patterns with an underscore (like I did just above). This can be helpful in catching some subtle errors early if you compile with -fwarn-unused-matches (included in -Wall). Here's a good StackOverflow answer about when that might be the case, and it's a good habit to have even for simpler functions like this.

3. Here's where looking at the docs afterward can help, your function flatten' is named concat in the standard List functions. And in fact mapping over a list and then flattening it is so common that there's even a function for that, creatively named concatMap.

4. Consider the lambda you use in the definition of flatten'.

   (\acc x -> acc ++ x)
   

   The strength of functional languages is being able to pass functions as values, which is of course what you're doing here with a lambda, but did you know that operators like ++ can already be used like any other old function? Wrap infix operators in parentheses to treat them like regular functions.

   ... = foldl (++) [] as -- Identical to the above!
   

5. foldl is broken! This might be more advanced reading than you're comfortable with now, but the bottom line is that foldl typically has unwanted performance characteristics, and to be safe you should use foldl' (import Data.List (foldl') at the start of your file, then change all foldls to foldl's) or foldr.

Answer 3

This is a surprisingly tricky function. I played with the solutions provided and realized they were not generic. For instance, the solution that only relies on fmap (a.k.a map if applied to a list), only worked with a list with two lists (i.e., [[],_] only works on a list length of two).

Here is a solution that builds on what was provided to generalize it to a list of any number of lists.

trans :: [[a]] -> [[a]]
trans [] = []
trans ([]:xss) = trans xss
trans ((x:xs):xss) = (x : fmap head' xss) : trans (xs : fmap tail' xss)
    where head' (x:_) = x
          tail' (_:xs) = xs

The benefits of this approach:

1. there is no need to pattern match a list of empty lists; a surprisingly verbose approach that requires the use of a reduction such as concat. Part of the trick to avoiding this is the ([]:xss) = trans xss recursion.
2. the trans ((x:xs):xss) is key to the solution. This pattern match and subsequent reassembly is a useful idiom worth being familiar with.
3. the approach avoids having to define safehead; the safeguard of calling head on an empty list is moot because we have trans [] = [] which will pattern match before xss reaches a call to head'.

What made it tricky was my being stuck on trying to pattern match a list of empty lists e.g., [[],[],[]]. I could not find a way to pattern match on a list of empty lists for any number of empty lists without resorting to using concat xss with a pattern match to [].