Home > Archive > Scheme > January 2006 > how does merge work?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
how does merge work?
|
|
| ManegraM@gmail.com 2006-01-17, 8:01 am |
| (define merge
(lambda (la lb)
(cond
((null? la) lb)
((null? lb) la)
((< (car la) (car lb)) (cons (car la) (merge (cdr la) lb)))
(else (cons (car lb) (merge la (cdr lb)))))))
(define odds
(lambda (l)
(cond
((null? l) l)
(else (evens (cdr l))))))
(define evens
(lambda (l)
(cond
((null? l) l)
(else (cons (car l) (odds (cdr l)))))))
(define m-sort
(lambda (l)
(cond
((or (null? l) (null? (cdr l))) l)
(else (merge (m-sort (evens l)) (m-sort (odds l)))))))
Merge looks like it should sort given two lists but it does not.
However m-sort works. How?
| |
| Ulrich Hobelmann 2006-01-17, 8:01 am |
| ManegraM@gmail.com wrote:
> (define merge
> (lambda (la lb)
> (cond
> ((null? la) lb)
> ((null? lb) la)
> ((< (car la) (car lb)) (cons (car la) (merge (cdr la) lb)))
> (else (cons (car lb) (merge la (cdr lb)))))))
>
> (define odds
> (lambda (l)
> (cond
> ((null? l) l)
> (else (evens (cdr l))))))
> (define evens
> (lambda (l)
> (cond
> ((null? l) l)
> (else (cons (car l) (odds (cdr l)))))))
>
> (define m-sort
> (lambda (l)
> (cond
> ((or (null? l) (null? (cdr l))) l)
> (else (merge (m-sort (evens l)) (m-sort (odds l)))))))
>
>
>
>
>
> Merge looks like it should sort given two lists but it does not.
Merge doesn't sort. As you can see in its last two lines it merely
chooses the smaller element for *the beginning* of both lists and makes
that the beginning of the new list. It doesn't pick the *smallest*
element from either list.
It merges two lists; it doesn't sort.
> However m-sort works. How?
Recursively. ;)
No really. Read the code. Try a small list of your choice (maybe five
numbers) and simulate the scheme program by hand to see what it does.
--
The problems of the real world are primarily those you are left with
when you refuse to apply their effective solutions.
Edsger W. Dijkstra
| |
| Max Hailperin 2006-01-17, 7:06 pm |
| If (as I suspect) your confusion is with the underlying concepts of
merging and merge sorting, rather than with the list-processing code
per se, you might find helpful the explanation in Chapter 4 of
Concrete Abstractions (available free at
http://www.gustavus.edu/+max/concre...s-pdfs/list.cfm ).
This explanation is framed in terms of sorting numbered cards into
order, which I find to be a valuable exercise. If you are unwilling
to make actual numbered cards, you can use our "virtual manipulative"
applet, http://www.gustavus.edu/+max/concabs/applets/sort/
-max
|
|
|
|
|