[plt-scheme] HTDP 21.1.2
>> > fold is a reducing function - produces a consolidated value from
>> > multiple inputs (eg list).
Hi Wooks,
Yes, folding acts like a loop with an accumulator. The key thing to see
is that the accumulation value doesn't necessarily have to be "simpler"
than the list we're iterating over. In fact, it can be even bigger.
For example, let's say that we wanted to double up every element in a
list. That is:
(double-up '(hello world))
should give us:
(double-up '(hello hello world world))
We could imagine doing this with explicit recursion, but let's see how
this might work with a fold. Oh, before we begin, let's say that our fold
function looks like:
;; fold: (X Y -> Y) Y (listof X) -> Y
(define (fold f acc lst)
(cond
[(empty? lst) acc]
[else
(f (first lst) (fold f acc (rest lst)))]))
where we take the processing function as the first argument and the
accumulation value as the second.
We'll start with the assumption that doubling-up will be a simple fold.
That assumption may be a silly one, but let's see how far we can go with
it. Let's start with a template:
;; double-up: (listof symbol) -> (listof symbol)
;; Doubles up all the symbols in lst.
(define (double-up lst)
(fold ... ... lst))
We leave '... where it's not clear what's the right thing to do yet. But
actually, we know a little bit more than this, because we'd like:
(double-up empty) ---> empty
That is, we know what to expect from the simplest base case input. So at
least we have:
(define (double-up lst)
(fold ... empty lst))
Now to attack the other ..., the mystery-function that we don't know yet.
We know it's going to have the form:
... == (lambda (x acc) ... x ... acc)
because that's what fold's contract forces things to be. And we know even
more: "x" in this context has to be a symbol, and "acc" has to be a list
of symbols.
(Do you know why?)
Now things look like:
;; mystery-function symbol (listof symbol) -> (listof symbol)
(define (mystery-function x acc)
... x ... acc))
;; double-up: (listof symbol) -> (listof symbol)
(define (double-up lst)
(fold mystery-function empty lst))
(I'm breaking out the mystery-function as a separate definition just for
cosmetics.)
When we look at mystery-function, we can ask ourselves: what's the meaning
of its arguments? "x" is going to be an element in the lst that double-up
is processing. But what is "acc"? Looking back at the definition of
fold:
;; fold: (X Y -> Y) Y (listof X) -> Y
(define (fold f acc lst)
(cond
[(empty? lst) acc]
[else
(f (first lst) (fold f acc (rest lst)))]))
^^^^^^^^^^^^^^^^^^^^^^^
we see that it's going to be the accumulated result of folding the
function across the rest of the list. But one thing to notice is that
this means that value is (double-up (rest lst))!
That is, if we're going through a sample evaluation:
(double-up '(a b c))
at some point, our mystery-function:
(define (mystery-function x acc)
... x ... acc))
is going to be fed with;
(mystery-function 'a '(b b c c))
and we know we want to get back:
(mystery-function 'a '(b b c c))
==> '(a a b b c c)
So the mystery-function here is going to have a very simple definition.
Would you be able to fill that definition in?
So this is a very concrete (but incomplete! *grin*) sketch of a fold
application that returns a result that's just as complex as the input we
give it. Try filling in the details, and then compare the process of the
fold vs. using the explicit recursive definition.
Good luck!