[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?)
>
because we want to use fold which has a contract of
;fold: (X, Y -> Y) Y [listof X] -> Y
and if our desired result is [listof symbols] then we must instantiate Y
(the result of fold) to [listof symbols].
mysteryFunction corresponds corresponds to the (X Y -> Y) so unifying the
contract with the known value of Y
(X [listof symbol] -> [listof symbol])
Now it looks like setting X to symbol results from an educated guess
because I don't see anything that strictly binds X to symbol (X could be a
number and mystery function might be a function that returns a list of X
randomly selected symbols (from the input Y).
>
>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?
>
(define (mysteryfunction sym alos)
(cons sym (cons sym alos)))