inverso lista - schema

Question

Sto cercando di invertire una lista, ecco il mio codice:

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

quindi se entro (reverse '(1 2 3 4)), lo voglio a venire fuori come (4 3 2 1), ma in questo momento non mi sta dando questo. Cosa sto facendo di sbagliato e come posso risolverlo?

Answer 1

Il modo naturale di ricorrere in un elenco non è il modo migliore per risolvere questo problema. Usare append, come suggerito nella risposta accettata indicata da @lancery, non è una buona idea neanche - e comunque se stai imparando la tua strada in Scheme è meglio se provi a implementare la soluzione da solo, ti mostrerò cosa fai, ma prima un consiglio: non usare list come nome parametro, è una procedura integrata e la sovrascriveresti. Usa un altro nome, per esempio, lst.

È semplice invertire una lista mediante una procedura di supporto che accumula il risultato di consing ciascun elemento in corrispondenza testa del risultato, ciò avrà l'effetto di invertire lista - incidentalmente, la procedura helper è coda -ricorsivo. Ecco l'idea generale, fill-negli spazi vuoti:

(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 

Naturalmente, nella vita reale non sarebbe implementare reverse da zero, c'è un built-in procedure per questo.

Answer 2

Ecco una soluzione che utilizza build-list procedura:

(define reverse 
    (lambda (l) 
    (let ((len (length l))) 
     (build-list len 
        (lambda (i) 
        (list-ref l (- len i 1))))))) 

Answer 3

(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)) 

più Una risposta simile a Oscar. Ho appena iniziato a studiare schema, quindi scusami se trovi problemi :).

Answer 4

Questo funziona ma non è una coda procedura ricorsiva:

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

Answer 5

realtà c'è alcuna necessità di aggiungere o riempire il corpo con un mazzo di lambda.

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

Answer 6

Tail approccio ricorsivo utilizzando un nome let:

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

Questo è fondamentalmente lo stesso approccio ad avere una funzione di supporto con un argomento di accumulo come nella risposta di Oscar, in cui legare il loop dopo let fa la entra in una funzione interiore che puoi chiamare.

Answer 7

ritengo che sarebbe meglio utilizzare accodare anziché contro

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

questa un'altra versione con coda ricorsione

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

Answer 8

Ecco una procedura ricorsiva che descrive un processo iterativo (coda ricorsiva) di invertire una lista in Schema

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

Utilizzo del modello di sostituzione per (r Everse (elenco 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) 

Ecco una procedura ricorsiva che descrive un processo ricorsivo (recursive non coda) di invertire un elenco nello Schema

(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)))) 

Uso modello di sostituzione per (REVERSE2 (lista 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)