HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Implementing Transpose

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
transposeimplementingstackoverflow

Problem

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.

Solution

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

-
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.

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

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


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

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

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


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

-
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

Code Snippets

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

Context

StackExchange Code Review Q#48451, answer score: 7

Revisions (0)

No revisions yet.