(foldl proc init lst ...+) -Any (foldr proc init lst ...+) -Any
foldr both act as reducers on lists, using
proc to "fold" each item of the list in turn into the initial value
The signature of
proc is important. More specifically, the type signature of
foldr with one
lst argument is
(X Y -Y) Y [List-of-X] -Y
proc should take two arguments (if there is one
lst) like so:
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"
The most important difference between
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.
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))
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)))]))
These are typically the most confusing higher-order functions in EECS 111. Whereas previous examples such as
filter preserve the shape of the input
foldr flatten them completely using a vaguely arcane mechanism, which breaks with students' mental models for higher-order functions.
When first introducing
foldr, it can help to follow this order:
- Demonstrate usage of the "fold" mechanic, using just
foldland an associative procedure (e.g.
- 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
It is important to introduce both
* in Step 1, in order to demonstrate two different
(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
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
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
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.