reverse list - schemat

Question

próbuję odwrócić listę, oto mój kod:

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

więc jeśli wejdę (reverse „(1 2 3 4)), chcę wyjść jako (4 3 2 1), ale teraz nie daje mi tego. Co robię źle i jak mogę to naprawić?

Answer 1

Naturalny sposób powtarzania listy nie jest najlepszym sposobem rozwiązania tego problemu. Używanie append, jak sugeruje zaakceptowana odpowiedź wskazana przez @pathium, również nie jest dobrym pomysłem - i tak, jeśli uczysz się w Scheme, najlepiej, jeśli sam spróbujesz wdrożyć rozwiązanie, pokażę ci, zrobić, ale najpierw napiwek - nie używaj list jako nazwy parametru, to wbudowana procedura, którą nadpisałeś. Użyj innej nazwy, powiedzmy, lst.

jest prostsze do odwrócenia listy za pomocą procedury pomocniczych, które gromadzą się w wyniku consing każdy element w głowicy wyniku, będzie to miało wpływ odwrócenia List - zresztą procedura pomocnik ogon -recursive. Oto ogólny pomysł, wypełnić puste pola:

(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 

oczywiście w prawdziwym życiu nie byłoby wdrożyć reverse od podstaw, nie ma wbudowaną procedure do tego.

Answer 2

Oto rozwiązanie stosując procedurę build-list:

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

Jeszcze jedna odpowiedź podobna do Oscara. Właśnie rozpocząłem naukę schematu, więc przepraszam, jeśli napotkasz problemy :).

Answer 4

Ten działa, ale nie jest to ogon procedura rekurencyjna:

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

Answer 5

Jest rzeczywiście nie ma potrzeby dołączania lub wypełnienie ciała z grupą lambda.

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

Answer 6

Tail rekurencyjnej podejście za pomocą nazwie let:

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

To jest w zasadzie takie samo podejście jak posiadające funkcję pomocnika z argumentem akumulatorów jak w odpowiedzi Oscar, gdzie wiązania loop po let czyni wpuść do wewnętrznej funkcji, którą możesz wywołać.

Answer 7

myślę, że byłoby lepiej użyć append zamiast minusy

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

to kolejna wersja z ogonem rekursji

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

Answer 8

Oto rekurencyjny procedura, która opisuje proces iteracyjny (ogon rekurencyjnej) odwrócenia listy na Schemacie

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

Stosowanie modelu zastępczego dla (r everse (lista 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) 

Oto rekurencyjny Procedura opisująca rekurencyjnego procesu (nie ogon rekurencyjne) odwrócenia listę w schemacie

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

za pomocą modelu podstawienie dla (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)