2013-02-25 1 views
5

Ich versuche, eine Liste rückgängig zu machen, hier ist mein Code:Reverse-Liste - Schema

(define (reverse list) 
    (if (null? list) 
    list 
     (list (reverse (cdr list)) (car list)))) 

so, wenn ich eingeben (Reverse ‚(1 2 3 4)), ich will es so kommen (4 3 2 1), aber im Moment gibt es mir das nicht. Was mache ich falsch und wie kann ich es beheben?

+0

Erwarten Sie, dass Ihr Code mit zirkulierenden Listen und/oder unsauberen Listen funktioniert? – GoZoner

Antwort

12

Der natürliche Weg, um über eine Liste zu wiederholen, ist nicht der beste Weg, um dieses Problem zu lösen. Die Verwendung von append, wie in der akzeptierten Antwort von @lancery vorgeschlagen, ist auch keine gute Idee - und wenn Sie Ihren Weg in Schema lernen, ist es am besten, wenn Sie versuchen, die Lösung selbst zu implementieren, werde ich Ihnen zeigen, was zu tun ist tun, aber zuerst ein Tipp - verwenden Sie nicht list als Parametername, das ist eine integrierte Prozedur und Sie würden es überschreiben. Verwenden Sie einen anderen Namen, sagen Sie lst.

Es ist einfacher, eine Liste mit Hilfe eines Helfer Prozedur zu umkehren, die das Ergebnis von consing am Kopf jedes Element ansammelt des Ergebnisses, wird dies die Wirkung der Umkehrung die Liste hat - übrigens die Helfer Verfahren Schwanz -rekursiv. Hier ist die allgemeine Idee, füllen die Lücken:

(define (reverse lst) 
    (<???> lst '()))      ; call the helper procedure 

(define (reverse-aux lst acc) 
    (if <???>        ; if the list is empty 
     <???>        ; return the accumulator 
     (reverse-aux <???>     ; advance the recursion over the list 
        (cons <???> <???>)))) ; cons current element with accumulator 

natürlich im wirklichen Leben nicht reverse von Grund auf neu implementieren würde, gibt es eine eingebaute in procedure dafür.

+0

Ich würde nicht davon abraten, 'Liste' als Parameternamen zu verwenden - das lexikalische Scoping von Scheme ist Teil seiner Schönheit. Ich würde empfehlen, einen Parameter nicht mit einer 'globalen' Funktion zu verbinden; einer der Fehler im Poser-Code. – GoZoner

0

Hier ist eine Lösung mit build-list Verfahren:

(define reverse 
    (lambda (l) 
    (let ((len (length l))) 
     (build-list len 
        (lambda (i) 
        (list-ref l (- len i 1))))))) 
-1
(define reverse? 
    (lambda (l) 
    (define reverse-aux? 
     (lambda (l col) 
     (cond 
      ((null? l) (col)) 
      (else 
      (reverse-aux? (cdr l) 
          (lambda() 
          (cons (car l) (col)))))))) 
    (reverse-aux? l (lambda() (quote()))))) 
(reverse? '(1 2 3 4)) 

Noch eine Antwort ähnlich wie Oscar. Ich habe gerade angefangen, Schema zu lernen, also entschuldige mich, falls du Probleme findest :).

0

Dies funktioniert, aber es ist kein Schwanz rekursive Prozedur:

(define (rev lst) 
(if (null? lst) 
    '() 
     (append (rev (cdr lst)) (car lst)))) 
-1

Es gibt eigentlich keine Notwendigkeit zum Anhang oder den Körper mit einem Bündel von lambdas füllen.

(define (reverse items) 
    (if (null? items) 
     '() 
     (cons (reverse (cdr items)) (car items)))) 
+2

Ich glaube, du meintest "append" statt "cons". Running '(reverse '(1 2 3))' ergibt '' ((((.). 3). 2). 1)' – Jack

+0

yep, du hast recht! @Salvatore Rapisarda hat es richtig gemacht –

1

Schwanz rekursive Ansatz ein let genannt:

(define (reverse lst) 
    (let loop ([lst lst] [lst-reversed '()]) 
    (if (empty? lst) 
     lst-reversed 
     (loop (rest lst) (cons (first lst) lst-reversed))))) 

Dies ist im Grunde der gleiche Ansatz eine Hilfsfunktion mit einem Akkumulator Argument wie in Oscar Antwort haben, wo die loop Bindung nach let das macht lass dich in eine innere Funktion ein, die du anrufen kannst.

0

ich denke, es wäre besser, zu verwenden hängen statt Nachteile

(define (myrev l) 
    (if (null? l) 
     '() 
     (append (myrev (cdr l)) (list (car l))) 
) 
) 

diese eine andere Version mit Endrekursion

(define (myrev2 l) 
    (define (loop l acc) 
    (if (null? l) 
     acc 
     (loop (cdr l) (append (list (car l)) acc)) 
    ) 
) 
    (loop l '()) 
) 
1

Hier ist eine rekursive Prozedur, die einen iterativen Prozess (Schwanz rekursiv) beschreibt zum Umkehren einer Liste in Schema

(define (reverse lst) 
    (define (go lst tail) 
    (if (null? lst) tail 
     (go (cdr lst) (cons (car lst) tail)))) 
    (go lst()))) 

Verwenden des Substitutionsmodells für (r Everse (Liste 1 2 3 4))

;; (reverse (list 1 2 3 4))                               
;; (go (list 1 2 3 4)())                                
;; (go (list 2 3 4) (list 1))                               
;; (go (list 3 4) (list 2 1))                               
;; (go (list 4) (list 3 2 1))                               
;; (go() (list 4 3 2 1))                                
;; (list 4 3 2 1) 

Hier ist eine rekursive Prozedur, die einen rekursiven Prozess beschreibt (nicht tail rekursiv) von einer Liste in Schema Umkehren

(define (reverse2 lst) 
    (if (null? lst)() 
    (append (reverse2 (cdr lst)) (list (car lst))))) 

(define (append l1 l2) 
    (if (null? l1) l2 
     (cons (car l1) (append (cdr l1) l2)))) 

Mit Substitutionsmodell für (reverse2 (Liste 1 2 3 4))

;; (reverse2 (list 1 2 3 4))                               
;; (append (reverse2 (list 2 3 4)) (list 1))                           
;; (append (append (reverse2 (list 3 4)) (list 2)) (list 1))                       
;; (append (append (append (reverse2 (list 4)) (list 3)) (list 2)) (list 1))                   
;; (append (append (append (append (reverse2()) (list 4)) (list 3)) (list 2)) (list 1))                
;; (append (append (append (append() (list 4)) (list 3)) (list 2)) (list 1))                   
;; (append (append (append (list 4) (list 3)) (list 2)) (list 1))                      
;; (append (append (list 4 3) (list 2)) (list 1))                          
;; (append (list 4 3 2) (list 1))                              
;; (list 4 3 2 1)