# Evaluation in Haskell

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