5

I am learning haskell and I tried to write my own reverse function without using recursion.

The solution is this function:

myreverse = foldl (flip (:)) []

I'm trying to understand what happens during the evaluation of, say:

myreverse [1..5]

I can't understand what flip does here. Can somebody write down what happens here with a step-by-step explanation?

tomferon
  • 4,993
  • 1
  • 23
  • 44
basti12354
  • 2,490
  • 4
  • 24
  • 43
  • 3
    *I can't understand what `flip` does here.* You might benefit from writing `(:)` as a lambda: `\x xs -> x : xs`. If you apply `flip` to this lambda, the resulting function is `\xs x -> x : xs`. – jub0bs May 21 '15 at 09:44
  • 1
    protip: use `foldl'` from the List module instead of `foldl`. Plain `foldl` is never the best choice (unless you are solving some [crazy made up problem](http://stackoverflow.com/questions/8235797)) – hugomg May 21 '15 at 14:10
  • 1
    @hugomg, I think it should probably be perfectly fine in this case. `flip (:)` doesn't do any actual computation, so I'd expect GHC to treat it pretty much like a constructor. You'd have to test to be sure though. – dfeuer May 21 '15 at 16:36

2 Answers2

7

flip is rather easy:

if you have a function f :: a -> b -> c then flip f is a function :: b -> a -> c so it gives you back a new function and flips the order of arguments you have to pass.

(:) :: a -> [a] -> [a] is a function of this pattern and so flip (:) will now be a function that first takes the soon-to-be tail and then the new head and returns you a new list with those:

(flip (:)) [2..4] 1
= (:) 1 [2..4]
= 1 : [2..4]
= [1,2,3,4]

now you need this here because foldl is defined this way:

foldl :: (b -> a -> b) -> b -> [a] -> b

you see - the function you have to pass will here be one that first takes a list and then an element and returns a new list

this will now fold all into something like this:

myreverse [1..5]
= foldl (flip (:)) [] [1,2,3,4,5]
= foldl (flip (:)) (((flip (:)) [] 1)) [2,3,4,5]
= foldl (flip (:)) (1:[]) [2,3,4,5]
= foldl (flip (:)) (((flip (:)) [1] 2)) [3,4,5]
= foldl (flip (:)) (2:[1]) [3,4,5]
= ...
= [5,4,3,2,1]
Random Dev
  • 51,810
  • 9
  • 92
  • 119
  • 1
    Minor objection: `foldl` doesn't cause the range to fully evaluate from the beginning. – jub0bs May 21 '15 at 09:50
  • yeah of course - but I think if I write down the sequence and look out for all the lazy parts this will get very cluttered and almost unreadable - I was hoping the indent and the way `flip` `(:)` and `foldl` are working here would be more obvious this way – Random Dev May 21 '15 at 09:54
  • Yes, yes, no problem. You wrote "something like this", after all. – jub0bs May 21 '15 at 09:56
3

You might try in ghci what flip does:

:t (:)
(:) 1 [2..4]

[1,2,3,4]

:t flip (:)
(flip (:)) [2..4] 1

[1,2,3,4]

daniel.kahlenberg
  • 307
  • 2
  • 12