1

I know how to use recursion to reverse a list, but I am trying to use foldl to make it more efficient. My code is as follow:

reverse list = foldl (++) [] (map (\x -> [x]) list)

When running it in GHCi, it returns the same list as input. What goes wrong? I also try to finish it by foldr but it does not show any change.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
YM.Zhou
  • 19
  • 3
  • See https://stackoverflow.com/questions/26847192/reverse-a-list-in-haskell – icc97 Sep 02 '17 at 09:16
  • Possible duplicate of [Reverse a list in haskell](https://stackoverflow.com/questions/26847192/reverse-a-list-in-haskell) – icc97 Sep 02 '17 at 09:16
  • @icc97 though a correct `foldl` solution is given in that question, the question itself not really about that, so I wouldn't say it's a duplicate. – leftaroundabout Sep 02 '17 at 09:18
  • @leftaroundabout OP wants to use `foldl` to reverse a list the [top answer](https://stackoverflow.com/a/26847373/327074) to the duplicate question gives: `reverseList = foldl (\acc x -> x : acc) []` – icc97 Sep 02 '17 at 09:19
  • 1
    As I was saying, the solution is sure there. Just, a _question duplicate_ should actually be asking the same question, and it's not really adressed over there why `foldl` without `flip` gives the the result in the wrong order. – leftaroundabout Sep 02 '17 at 09:22
  • your definition gives `reverse [1,2,3] = (([] ++ [1]) ++ [2]) ++ [3]`. the same definition with `foldr` would produce `reverse [1,2,3] = [1] ++ reverse [2,3]`. – Will Ness Sep 02 '17 at 17:30

2 Answers2

3

foldl passes the accumulator as the first argument to the function. ++ concatenates the first argument to the second, but, to reverse a list, you need to concatenate the second to the first. You can do this using flip (++):

Prelude> let reverse list = foldl (flip (++)) [] (map (\x -> [x]) list)
Prelude> reverse [1..5]
[5,4,3,2,1]
Dogbert
  • 212,659
  • 41
  • 396
  • 397
3

Instead of first converting all elements of the list to singleton lists (which is expensive as well), you can use the cons (:) function:

reverse :: Foldable t => t a  -> [a]
reverse = foldl (flip (:)) []

So here we use flip (:) :: [a] -> a -> [a] as fold function. It takes a tail [a] and a head a, and constructs a list with the head as first element and the tail as last element.

So what happens is:

   foldl (flip (:)) [] [1,4,2,5]
-> foldl (flip (:)) (1:[]) [4,2,5]
-> foldl (flip (:)) (4:1:[]) [2,5]
-> foldl (flip (:)) (2:4:1:[]) [5]
-> foldl (flip (:)) (5:2:4:1:[]) []
-> (5:2:4:1:[])
-> [5,2,4,1]
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • im always struggling with the difference foldl vs foldr, why use foldl here? would you mind a quick explanation? thanks! – Netwave Sep 02 '17 at 10:47
  • @DanielSanchez: `foldr` starts a the right end of the list (or more general the foldable). So if the list is `[a,b,c,d]`, it will calculate `f a (f b (f c (f d z)))`. Whereas `foldl` will calculate `f (f (f (f z a) b) c) d`. With `z` the initial element`. – Willem Van Onsem Sep 02 '17 at 10:54
  • Worked for me! Thanks for your advice. – YM.Zhou Sep 03 '17 at 05:17