Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Scheme Programming Language

Question about a map-definition


Hi,

I'm sitting on a scheme-course, preparing for an exam, and I'm not
shure, whether the following definition (from that course) is correct
(if so, I don't understand it) or faulty:

(define (map f s)
   (right-reduce (lambda (x r) (cons-stream (f x) r))
   the-empty-stream
   s))

The definition is used for example in this definition for the sum of
squares:

(define (sum-squares n) (sum (map square (interval 1 n))))

f is of course a function instantiated with "square" and s is a stream,
instantiated with the integer-interval from one to n.

I don't understand, what's the use for the _r_ in that lambda. Is it
simply a printing-fault, should it be _s_ or if not, where could any
instantiation for that _r_ come from? Or may there be a line missing,
declaring that _r_ as (tail s)?

Thanks in advance for any clue.
Michael Kutscher

Michael Kutscher <spam.ign@pc-coach.de> writes:
> Hi,

> I'm sitting on a scheme-course, preparing for an exam, and I'm not shure,
> whether the following definition (from that course) is correct (if so, I don't
> understand it) or faulty:

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

'as

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.

Maybe I still think too "procedural", but I've found other definitions
for map, that I do understand, only this one gives me a headache.

Best regards
Michael Kutscher

Michael Kutscher skrev:

Here is right-reduce for normal lists:

  (define (right-reduce combine initial s)
    (if (null? s)
        initial
        (combine (car s)
                 (right-reduce combine initial (cdr s)))))

Let's try some examples:

    (right-reduce + 0 '))
  = 0

    (right-reduce + 0 '(1)
  = (+ 1 (right-reduce + 0 '())
  = (+ 1 0)
  = 1

    (right-reduce + 0 '(1 2))
  = (+ 1 (right-reduce + 0 '(2))
  = (+ 1 (+ 2 (right-reduce + 0 '))))
  = (+ 1 (+ 2 0)))
  = 3

That is

   (cons 1 (cons 2 '())

becomes
   (+    1 (+    2 0))

so right-reduce "substitutes"
        cons with combine
  and  '()  with initial .

--
Jens Axel Sgaard

Hi,

> so right-reduce "substitutes"
>        cons with combine
>  and  '()  with initial .

'Click'

Thats it.

Thanks to Alexander and Jens Axel

Michael Kutscher

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,

'as

Hi,

Alexander Schmolck schrieb:
a perfectly clear explanation!

Thanks a lot

Michael Kutscher

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc