Reverse list of lists using foldr Haskell

Question

I'm trying to reverse list of lists in Haskell by using foldr. There is an example of what I want to do:

> reverse'' [[1,2,3],[3,4,5]]
[[5,4,3],[3,2,1]]

And my code (it is not working):

reverse'':: [[a]]->[[a]]
reverse'' x = foldr (\n acum -> acum:(foldr(\m acum1 -> acum1++[m])) [] n) [[]] x

My IDE reports me an error at the start of the second foldr.

Answer 1

To analyse your current solution, I've broken down your one-liner into some helper functions, with their type deduced based on their composition:

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [[]] x
    where
        f :: [a] -> a -> [a]
        f n acum = acum : reverse n

        reverse :: [a] -> [a]
        reverse n = foldr append [] n

        append :: a -> [a] -> [a]
        append m acum = acum ++ [m]

When I try to compile the above, ghc complains with the following error for the type signature of reverse'':

Expected type: [[a]] -> [[a]] -> [[a]]
  Actual type: [[a]] ->  [a]  -> [[a]]

I did some digging, and in order for reverse'' to have the type [[a]] -> [[a]], the function f needs to have the type [a] -> [[a]] -> [[a]]. However the current f has type [a] -> a -> [a], or in this case [[a]] -> [a] -> [[a]].

The following has the correct type, but inserts an extra [] value into the start of the array, due to the starting value of the accumulator:

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [[]] x
    where
        f :: [a] -> [[a]] -> [[a]]
        f n acum = acum ++ [reverse n]

        reverse :: [a] -> [a]
        reverse n = foldr append [] n

        append :: a -> [a] -> [a]
        append m acum = acum ++ [m]

The final solution

By changing the initial accumulator value to the empty list [], as opposed to a list of an empty list [[]], we end up at a working solution:

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [] x
    where
        f :: a -> [a] -> [a]
        f n acum = acum ++ [reverse n]

        reverse :: [a] -> [a]
        reverse n = foldr append [] n

        append :: a -> [a] -> [a]
        append m acum = acum ++ [m]

As a single line

If you really want this as a one-liner, here it is:

reverse'' :: [[a]] -> [[a]]
reverse'' = foldr (\n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]) []

With working:

append m acum = acum ++ [m]
append = \m acum1 -> acum1 ++ [m]

reverse n = foldr append [] n
reverse = \n -> foldr append [] n
reverse = foldr append []
reverse = foldr (\m acum1 -> acum1 ++ [m]) []

f n acum = acum ++ [reverse n]
f = \n acum -> acum ++ [reverse n]
f = \n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [] x
reverse'' x = foldr (\n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]) [] x
reverse'' = foldr (\n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]) []

Appendix: An explicitly recursive solution

Here is an explicitly recursive solution (i.e. not using a fold), with definitons of map and reverse provided.

reverse :: [a] -> [a]
reverse (x:xs) = reverse xs ++ [x]
reverse []     = []

map :: (a -> b) -> [a] -> [b]
map f (x:xs) = f x : map f xs
map _ [] = []

reverse'' :: [[a]] -> [[a]]
reverse'' ls = reverse $ map reverse ls