markv@fourier.Princeton.EDU (Mark VandeWettering) (01/31/91)
In article <11739@darkstar.ucsc.edu> gforce@ucscb.UCSC.EDU (60766000) writes: > >Can one of you scheme hackers out there help me with a prog. problem ? >the version of scheme at my school doesn't have the function "reverse" >I am trying to write one but so far have only come up with one that is >recursive but needs to take in two arguments.. CAn someone show me a way >to do it with only one ?.. > >Thanx Sigh! Someone should work harder to understand what is going on. If you can't code reverse, then you can't code LOTS. But, in true spirit of a spoiler.... Try any one of the following (done off the top of my head): (define (reverse l) (if (null? l) '() (append (reverse (cdr l)) (car l)))) This is ugly because of the append. Appending does lots and lots of consing. It is also not tail recursive, so it consumes stack. First, let's deal with the tail recursion problem.... (define (reverse-tr l) (define (rloop l r) (if (null? l) r (rloop (cdr l) (cons (car l) r)))) (rloop l '())) By some strange coincidence, we also have gotten rid of the append problem. This will execute in all reasonable Scheme implementations with a constant amount of stack, since it is fully tail recursive. Mark VandeWettering markv@acm.princeton.edu
jar@altdorf.ai.mit.EDU (Jonathan A Rees) (02/01/91)
Date: 31 Jan 91 08:18:51 GMT
From: 60766000 <gforce@ucscb.ucsc.edu>
the version of scheme at my school doesn't have the function "reverse"
I am trying to write one but so far have only come up with one that is
recursive but needs to take in two arguments.. CAn someone show me a way
to do it with only one ?..
The following is from John Allen's book _Anatomy of Lisp_, if I recall
correctly (unlikely):
(define (reverse l)
(cond ((null? l) l)
((null? (cdr l)) l)
(else (cons (car (reverse (cdr l)))
(reverse (cons (car l)
(reverse (cdr (reverse (cdr l))))))))))
Somehow I don't think this is what you had in mind, but I'm sure that
other members of this forum will supply you with plenty of alternatives.bobg+@andrew.cmu.edu (Robert Steven Glickstein) (02/02/91)
Excerpts from netnews.comp.lang.scheme: 31-Jan-91 Scheme recursive procedures 60766000@ucscb.UCSC.EDU (321) > Can one of you scheme hackers out there help me with a prog. problem ? > the version of scheme at my school doesn't have the function "reverse" > I am trying to write one but so far have only come up with one that is > recursive but needs to take in two arguments.. CAn someone show me a way > to do it with only one ?.. Here's one implementation of reverse and reverse!. In general, if you want a one-parameter procedure but can't think of how to do it in less than two parameters, write a one-parameter *interface* to a "hidden" two-parameter procedure, like so: (define one-param (letrec ((two-param (lambda (a b) ...))) ; two-param is a ; private procedure ; taking 2 args (lambda (only-one) ; this is one-param (two-param only-one ; it calls two-param (some other expr))))) ; with some initial values ;;; Now for reverse and reverse! (define reverse (letrec ((reverse-aux (lambda (result remaining) (if (null? remaining) result (reverse-aux (cons (car remaining) result) (cdr remaining)))))) (lambda (l) (reverse-aux '() l)))) (define (reverse! l) (cond ((null? l) l) ((not (pair? (cdr l))) l) (else (let ((cl (cdr l))) (set-cdr! l '()) (let loop ((a l) (b cl)) (cond ((not (pair? b)) a) (else (let ((c (cdr b))) (set-cdr! b a) (loop b c))))))))) ______________ _____________________________ Bob Glickstein | Internet: bobg@andrew.cmu.edu Information Technology Center | Bitnet: bobg%andrew@cmuccvma.bitnet Carnegie Mellon University | UUCP: ...!harvard!andrew.cmu.edu!bobg Pittsburgh, PA 15213-3890 | (412) 268-6743 | Sinners can repent, but stupid is forever
maguire@sun.soe.clarkson.edu (Bill Maguire) (02/02/91)
>In article <11739@darkstar.ucsc.edu> gforce@ucscb.UCSC.EDU (60766000) writes: >> >>Can one of you scheme hackers out there help me with a prog. problem ? >>the version of scheme at my school doesn't have the function "reverse" >>I am trying to write one but so far have only come up with one that is >>recursive but needs to take in two arguments.. CAn someone show me a way >>to do it with only one ?.. >> >>Thanx In article <5834@idunno.Princeton.EDU> markv@fourier.Princeton.EDU (Mark VandeWettering) writes: >Sigh! Someone should work harder to understand what is going on. If you >can't code reverse, then you can't code LOTS. >But, in true spirit of a spoiler.... >Try any one of the following (done off the top of my head): > > (define (reverse l) > (if (null? l) '() > (append (reverse (cdr l)) (car l)))) > > (define (reverse-tr l) > (define (rloop l r) > (if (null? l) > r > (rloop (cdr l) (cons (car l) r)))) > (rloop l '())) > >By some strange coincidence, we also have gotten rid of the append problem. >This will execute in all reasonable Scheme implementations with a constant >amount of stack, since it is fully tail recursive. >Mark VandeWettering >markv@acm.princeton.edu If you really want to hack though, why not: (define reverse (lambda (l) (call-with-current-continuation (lambda (return) (let ((r nil) (loop 'any-value)) (call-with-current-continuation (lambda (c) (set! loop c))) (if (null? l) (return r)) (set! x (cons (car l) r)) (set! l (cdr l)) (loop 'any-value)))))) It also uses constant stack space... -Bill Maguire
markf@zurich.ai.mit.edu (Mark Friedman) (02/02/91)
In article <9102010942.aa25019@mc.lcs.mit.edu> jar@altdorf.ai.mit.EDU (Jonathan A Rees) writes:
The following is from John Allen's book _Anatomy of Lisp_, if I recall
correctly (unlikely):
(define (reverse l)
(cond ((null? l) l)
((null? (cdr l)) l)
(else (cons (car (reverse (cdr l)))
(reverse (cons (car l)
(reverse (cdr (reverse (cdr l))))))))))
Somehow I don't think this is what you had in mind, but I'm sure that
other members of this forum will supply you with plenty of alternatives.
You remembered correctly.
In defence of John Allen, the above definition was presented in his
book after the version with a helper function and after the append
version. He wanted to show that "it is possible to write a directly
recursive reversing funtion with no auxiliary fuctions, no functions
other than the primitives, and with not much clarity."
-Mark
--
Mark Friedman
MIT Artificial Intelligence Lab
545 Technology Sq.
Cambridge, Ma. 02139
markf@zurich.ai.mit.edu