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
> 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 I think reduce can be explained very easily and intuitively, without saying
> one gives me a headache.
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
(+ spam-bill eggs-bill salad-bill monitor-bill cdrom-bill rent-bill water-bill))
(+ (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))
(sum (map (lambda (items)
(sum (map bill items))) (list food-items computer-items housing-items))))
(define compute-total-expenses (lambda (items-list)
(reduce-right (lambda (items total) (+ total (sum (map bill items)))) items-list))
(compute-total-expenses (list food-items computer-items housing-items))))
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.