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