[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!