Problem: Given two lists of elements, both monotonically nondecreasing
according to some ordering predicate (optionally also given, but defaulting
<), construct a monotonically nondecreasing list
containing all the elements of both source lists.
The algorithm implemented here is a tail recursion in which three values
are passed from each call to the next: the parts of the two source lists
that have not yet been transferred to the result and the part of the result
that has been constructed so far (in reverse order, so that additions can
be made at the front). In each call, the two source lists are checked to
see whether either is yet exhausted; if so, the part of the result that has
been constructed so far is reversed and prepended to the rest of the other
source (using the
reverse-it procedure shown below).
Otherwise, the first elements of the respective source lists are compared;
whichever takes precedence is transferred to the result for the next
The(define merge (lambda (list-1 list-2 . opt) (let ((precedes? (if (null? opt) < (car opt)))) (let loop ((source-1 list-1) (source-2 list-2) (so-far '())) (cond ((null? source-1) (reverse-it so-far source-2)) ((null? source-2) (reverse-it so-far source-1)) (else (let ((car-1 (car source-1)) (car-2 (car source-2))) (if (precedes? car-2 car-1) (loop source-1 (cdr source-2) (cons car-2 so-far)) (loop (cdr source-1) source-2 (cons car-1 so-far))))))))))
reverse-itprocedure prepends the elements of one list (
ls) to a second list (
acc) in reverse order. This version is Program 4.25 of Scheme and the art of programming, by George Springer and Daniel P. Friedman (Cambridge, Massachusetts: MIT Press, 1989), p. 127.
(define reverse-it (lambda (ls acc) (if (null? ls) acc (reverse-it (cdr ls) (cons (car ls) acc)))))
This document is available on the World Wide Web as
John David Stone (email@example.com)