Hello all-
I am working on a problem in which I have to rotate a list such as...
(a b c d) to (d a b c)
The code I have generated (using recursion) is not working and I was
wondering if someone could give me a tip as to what I was doing wrong and
point me in the right direection.
(define rotate (lambda (los)
(let ((last (list (car (reverse los)))))
(let loop ((los los))
(cond
((null? los) '())
((not (eq? last los)) (cons (car los) (loop (cdr los))))
(else (cons (car los) (loop (cdr los)))))))))
Thanks for any help...
Ken
In article <··········@chaos.dac.neu.edu>,
Kenneth R. Griffiths <········@lynx.neu.edu> wrote:
>(define rotate (lambda (los)
> (let ((last (list (car (reverse los)))))
> (let loop ((los los))
> (cond
> ((null? los) '())
> ((not (eq? last los)) (cons (car los) (loop (cdr los))))
> (else (cons (car los) (loop (cdr los)))))))))
The second clause of your COND will always be true. This is because you
set LAST to a brand new list, which can never be eq? to an old list.
To implement this using your recursive algorithm, you need to set LAST to
the last pair in the original list, not to a new pair. Common Lisp has the
function LAST that returns this pair; I don't have any Scheme documentation
handy so I don't know if it has an equivalent function, but it should be
simple to write a recursive function that does it.
Also, you're never consing the original last element onto the front of the
result!
Here's a tail-recursive version that builds the result as it searches for
that last pair:
(define rotate (lambda (los)
(let loop ((result '())
(los los))
(cond ((null? los) '())
((null? (cdr los)) (cons (car los) result))
(#t (recurse (append! result (list (car los)))
(cdr los)))))))
It's inefficient, due to its use of append! during the recursion; it would
be possible to recode it so that it keeps a pointer to the last pair in the
result and uses set-cdr!, but I that complicates the function (see the "bad
idiom" thread for my comments about CL's LOOP macro -- its COLLECTING
clause does this automatically for you).
Of course, there's a much simpler and more efficient way to do it, that
takes advantage of the fact that you're reversing the list in order to get
the last element.
(define rotate (lambda (los)
(cond ((null? los) '())
(#t (let ((rev (reverse los)))
(cons (car rev) (reverse! (cdr rev))))))))
--
Barry Margolin
BBN Planet, Cambridge, MA
······@bbnplanet.com - Phone (617) 873-3126 - Fax (617) 873-5508
(BBN customers, please call (800) 632-7638 option 1 for support)