Evaluation in Haskell

- 3 mins

In Real World Haskell, there is a section on folds that contains this implementation of foldl in terms of foldr:

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

As the book warns, this is not trivial to understand, and it inspired a lengthy stack overflow post explaining how the function operates.

But the most confusing part for me was a smaller part of the puzzle, and a similar part was confusing to the user who asked the question:

foldr’s prototype is foldr :: (a -> b -> b) -> b -> [a] -> b, and the first parameter is a function which need two parameters, but the step function in the myFoldl’s implementation uses 3 parameters, I’m complelely confused!

In my case, what confused me was that foldr, a function that takes three parameters, seems to be passed four in the above implementation.

I’m not sure I’ve correctly understood why this works, but I think it’s due to a mixture of currying and lazy evaluation.

Let’s inline step:

myFoldl :: (a -> b -> a) -> a -> [b] -> a    
myFoldl f v xs =
  foldr (\x g -> (\a -> g (f a x))) id xs v

I’ve also added nesting (\x g -> (\a instead of \x g a) to try and make it clearer what’s going on.

Now let’s walk through the function with some test data:

myFoldl (+) 0 [1, 2] 
  = foldr step id [1, 2] 0

It looks to me like what happens next is Haskell says

ok, foldr only takes 3 params, so I’m ignoring that 0 until foldr has finished evaluating.

I presume it has also said (slight spoiler alert)

I know foldr step id [1,2] evaluates to a function that can take 0 as a param, so I can definitely go ahead and run this.

Let’s ignore the 0 for now and look at the next steps (a reminder that step evaluates to \x g -> (\a -> g (f a x))):

foldr step id [1, 2]
  = step 1 (foldr step id [2])

foldr step id [2]
  = step 2 (foldr step id [])

foldr step id []
  = id

Once the array is empty, the function returns an id, and our recursive stack starts to unwrap, which is where things get interesting:

step 2 id = \a -> id ((+) acc 2)

step 1 (\a -> id ((+) acc 2)) 
  = \a -> (\b -> id ((+) b 2)) ((+) a 1)

So we have a function that takes a parameter:

\a -> (\b -> id ((+) b 2)) ((+) a 1) 0
  = \a -> id ((+) a 2) 1

Once it’s applied to our current accumulator, it unwraps a function that takes another parameter:

\a -> id ((+) a 2) 1 
  = 3

And we’ve arrived!

Something is happening here that I really like.

Each time a layer of the recursive function is ‘unwrapped’, the new accumulator value is left on the outside which is in turn passed as a parameter to the function in front of it that has also just been unwrapped.

I love that the way haskell evaluates allows for the integer on the right to ‘wait’ and change while the function to its left is evaluated.

I suspect this is due to Haskell’s lazy evaluation—it’s interesting that this aspect of its implementation allows us to write in such a mathsy manner.

Alex Chalk

Alex Chalk

Software Developer | Node/JS at Work | Haskell/TLA+ in Spare Time | Employed at Busbud

comments powered by Disqus
rss facebook twitter github gitlab youtube mail spotify lastfm instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora quora