`foldl`

and `foldr`

```
(foldl proc init lst ...+) -Any
(foldr proc init lst ...+) -Any
```

`foldl`

and `foldr`

both act as reducers on lists, using `proc`

to "fold" each item of the list in turn into the initial value `init`

.

The signature of `proc`

is important. More specifically, the type signature of `foldl`

/`foldr`

with one `lst`

argument is

`(X Y -Y) Y [List-of-X] -Y`

meaning that `proc`

should take two arguments (if there is one `lst`

) like so:

`item-from-lst accumulated-value`

## Usage

The canonical example of `foldl`

usage is taking the sum of a list of numbers:

```
(define numbers '(1 2 3 4 5 6))
; `proc` is the addition function, `+`
; `init` is 0
; `lst` is `numbers`
(foldl + 0 numbers)
21
; Using foldl to concatenate a list of strings
(define words '("madam" "im" "adam"))
(foldl string-append "" words)
"adamimmadam"
```

## Difference Between `foldl`

and `foldr`

The most important difference between `foldl`

and `foldr`

is that `foldl`

traverses the list from left-to-right, and `foldr`

from right-to-left. Continuing the above example,

```
(foldl string-append "" words)
"adamimmadam"
; foldr does things the other way around
(foldr string-append "" words)
"madamimadam"
```

How does this affect implementation? The difference is that `foldl`

is tail-recursive, whereas `foldr`

is not.

With `foldl`

(and accumulator patterns generally), `proc`

is applied to the current list value and the **accumulator**. That is, the recursive expression looks like this:

```
(my-foldl proc
(proc (first lst) init) ; proc applied here
(rest lst))
```

With `foldr`

and non-optimized patterns, `proc`

is applied to the current value and the **result of recursing on the rest of the list**. That is, evaluation cannot complete until the entire list has been traversed.

```
(proc (first lst) ; proc is all the way up here
(my-foldr proc
init ; init is unmodified
(rest lst)))
```

## Student Language Implementations

Student lang implementations of each function, demonstrating how the difference in order of application affects the structure and space efficiency of each function:

```
; foldl is constant space because it uses an accumulator
(define (my-foldl proc init lst)
(cond
; In the base case, return init
[(empty? lst) init]
[else
; Fold current list item into the accumulator
; and pass that to the next recursive call,
; as the new init
(my-foldl proc
(proc (first lst) init) ; new init
(rest lst))]))
(define (my-foldr proc init lst)
(cond
; In the base case, return init
[(empty? lst) init]
[else
; Since we are starting from the end of the list
; or innermost pair, we will use parenthetical order
; of operations to make sure the inner items get folded
; first.
(proc (first lst)
(my-foldr proc
init
(rest lst)))]))
```

## Teaching Notes

These are typically the most confusing higher-order functions in EECS 111. Whereas previous examples such as `map`

and `filter`

preserve the shape of the input `lst`

, `foldl`

and `foldr`

flatten them completely using a vaguely arcane mechanism, which breaks with students' mental models for higher-order functions.

When first introducing `foldl`

/`foldr`

, it can help to follow this order:

- Demonstrate usage of the "fold" mechanic, using just
`foldl`

and an associative procedure (e.g.`+`

and`*`

) - Introduce the difference between the two functions at a high level using a non-associative procedure (e.g.
`-`

) - Show how implementation varies between the two functions (with
`foldl`

being constant-space)

It is important to introduce both `+`

and `*`

in Step 1, in order to demonstrate two different `init`

values.

```
(foldl + 0 '(1 2 3 4)) ; the additive identity is 0
(foldl * 1 '(1 2 3 4)) ; the multiplicative identity is 1
```

**Make sure to guide students through Step 2 carefully.** It is easy to choose arguments without thinking, which result in identical output from `foldl`

and `foldr`

.

Namely, even if the student uses a non-associative function such as `-`

, passing a `lst`

with an odd number of elements or duplicate elements can sometimes cause `foldl`

and `foldr`

to produce the same value:

```
> (foldl - 0 '(1 2 3 4 5))
3
> (foldr - 0 '(1 2 3 4 5))
3
> (foldr - 0 '(1 2 3 2))
0
> (foldl - 0 '(1 2 3 2))
0
```

Take care to show `(foldl - ...)`

examples with an odd number of unique `lst`

elements.

Students also get extremely confused when tracing the execution of both functions in their student language implementations. Prepare for tutorials by tracing through a couple of examples until you are rock-solid on how they work.