Michael Kutscher <spam.ign

@pc-coach.de> writes:

> Hi,

>> Looks right to me. What do you think right-reduce does? (This is not a

>> rhetorical question).

> Thanks for answering.

> the right-reduce is declared as following:

> (define (right-reduce combine initial s)

> (if empty-stream? s)

> initial

> (combine (head s)

> (right-reduce combine initial (tail s)))))

> So that right-reduce takes a function combine (that lambda), an initial

> (the-empty-stream) and a stream a. It should apply the function to all

> elements and return a single value.

This is true, but if you look at the code above you see that (I'm jusing CAPS

for code) COMBINE is called with two arguments, which means the lambda you

pass as COMBINE has to have two arguments, too, right? So it's not quite clear

to me why you thought the R argument was a typo, because even if one doesn't

understand how exactly the reduce expression works, it seems obvious to me

that, purely syntactically, you need to pass in a two-argument function. So I

was wondering whether there's maybe some deeper misunderstanding that might

need to be cleared up before trying to explain REDUCE and implementing MAP

with it.

> Maybe I still think too "procedural",

Possibly -- another way to see that the function must take two elements is to

consider that the current state of the operation needs to be passed around

manually if no mutation takes place.

> but I've found other definitions for map, that I do understand, only this

> one gives me a headache.

I think reduce can be explained very easily and intuitively, without saying

anything about recursion etc: in terms of normal math notation, reduce just

*inserts* an operator beweeen list elements:

(reduce + '(1 2 3 4)) ; 1+2+3+4

In more gruesome detail:

Now I was a bit cavlier about something (and I've omitted INITIAL for the time

being, I'll come back to it later; I'll also use normal lists instead of

streams), in math notation operators can bracket to the right or to the left

-- for addition it doesn't make a difference because it is associative, i.e.

;bracket to left ; bracket to right

(((1+2)+3)+4 = (1+(2+(3+4)))

But for division, exponentiation etc. it obviously makes a difference:

(1/2)/3 != (1/(2/3)).

This is why there is a left and a right variant of reduce -- one inserts an

operator bracketing to the left and one bracketing to the right.

But of course an operator in math notation is just a funny way to write a

function -- if we borrow haskell haskell notation to write functions as infix

using backticks we can alternatively write "g(a,b)" as "a `g` b".

Than we can write

(right-reduce g '(1 2 3 4)) ; (1 `g` (2 `g` (3 `g` 4)))

In you case `g` is (lambda (a b) (cons (f) r)) or, if we write ":" for cons:

a `g` b == f(a):b.

Try writing out the above reduce call like that and in prefix notation.

Back to INITIAL:

Well, in my explanation above I omitted what happens if you use an empty list:

(reduce + '()) ; ???

It could just throw an error, however there is a more elegant solution

(reduce + '()) == 0 ; 0 is the neutral element of addition, i.e. adding 0

; doesn't do anything

this solution is superior because it preservs a useful invariant:

you can *always* rewrite

a+b+c+...d ; (e.g. '...' = 'x+y+z+')

as (mixing scheme and math)

a+b+c+(reduce + (list ...))+d ; (e.g. '...' = (list x y z))

even if '...' has zero rather than, 3 (as above), 2 or 1 terms. As a concrete

if artifical example, assume you want to sum your monthly expenses, rather

than writing

(define monthly-expenses

(+ spam-bill eggs-bill salad-bill monitor-bill cdrom-bill rent-bill water-bill))

(define monthly-expenses

(+ (reduce + food-bills) + (reduce + computer-bills) (reduce + housing-bills)))

and this will still work if one of the expenses-lists is empty (you didn't buy

any computer stuff this month) -- and it also allows further abstraction, e.g.

(define sum (lambda (l)) (reduce + l))

(define monthly-expenses

(sum (map (lambda (items)

(sum (map bill items))) (list food-items computer-items housing-items))))

or

(define compute-total-expenses (lambda (items-list)

(reduce-right (lambda (items total) (+ total (sum (map bill items)))) items-list))

(define monthly-expenses

(compute-total-expenses (list food-items computer-items housing-items))))

etc.

However, scheme and most other languages don't allow an elegant way to

associate a neutral element with a function and not all functions have a

left/right neutral element, so INITIAL-ELEMENT is basically like making sure

the list always has at least one element, and most often one supplies the

neutral element of the operation (0 for +). Thus:

(actual-left-reduce f INITIAL-ELEMENT list) = (left-reduce f (cons INITIAL-ELEMENT list))

(Excercise: what does actual-right-reduce look like in terms of real-right-reduce)

One line Summary:

(right-)reduce == insert-operator-between-elements-of-list(-bracketing-to-right),

for empty list chooise neutral element of operator

Hope this makes some sense? Try writing REVERSE and APPEND with reduce to see

if you've got it.

cheers,