Cómo revertir una lista?

Question

¿Cuál es la función de una lista en Scheme? Necesita ser capaz de manejar listas anidadas.

De modo que si haces algo como (reverse '(a (b c d) e)) obtendrás (e (b c d) a) como salida.

¿Cómo debo abordar este problema? No solo estoy buscando una respuesta, sino algo que me ayudará a aprender.

Answer 1

(define (reverse1 l) 
    (if (null? l) 
    nil 
    (append (reverse1 (cdr l)) (list (car l))) 
) 
) 

Explicación:

Reglas:
1. Si la lista está vacía, y luego invertir lista también está vacío
2. más detrás de la cola de la lista inversa añadir primer elemento de la lista

Mire este código de esta manera:

reverse1 es el nombre de la función, l es el parámetro
si la lista está vacía t gallina inverso es también vacía función de otra llamada reverse1 con (CDR l), que es la cola de la lista y añadir que a primera alement (coche l) que realice como una lista

en su ejemplo (pseudo bacalao):

1st iteration 
l=>(a (bcd)e) 
car l => a 
cdr l => (bcd)e 
list(car l) =>(a) 
------------------ 
reverse(cdr l)"+"(a) 
------------------ 
2nd iteration 
l=>((bcd)e) 
car l => (bcd) 
cdr l =>e 
list(car l)=>(bcd) 
-------------------- 
reverse(cdr l)"+"((bcd))+(a) 
----------------------- 
3rd iteration 
l=>e 
car l=> e 
cdr l => nil 
list (car l) =>(e) 
------------------------- 
(e (bcd)a) 

Answer 2

(define (my-reverse ls) 
    (define (my-reverse-2 ls acc) 
    (if (null? ls) 
     acc 
     (my-reverse-2 (cdr ls) (cons (car ls)) acc))) 
    (my-reverse-2 ls '())) 

Este utiliza una variable acumulador para revertir la lista, teniendo el primer elemento de la lista de entrada y Consing a la parte delantera del acumulador. Oculta la función de toma del acumulador y solo expone la función que toma una lista, por lo que la persona que llama no tiene que pasar la lista vacía. Es por eso que tengo my-reverse-2.

(my-reverse-2 '(a (b c d) e) '()); will call 
(my-reverse-2 '((b c d) e) '(a)); which will call 
(my-reverse-2 '(e) '((b c d) a)); which will call 
(my-reverse-2 '() '(e (b c d) a)); which will return 
'(e (b c d) a) 

Debido a que la última llamada a la función en my-reverse-2 es una llamada a my-reverse-2, y el valor de retorno se pasó a través de (el valor de retorno de la primera llamada es el valor de retorno de la segunda llamada, etc.) my-reverse-2 es cola optimizada, lo que significa que no se quedará sin espacio en la pila. Por lo tanto, es seguro llamar a esto con una lista todo el tiempo que desee.

Si desea que se aplique a las listas anidadas usar algo como esto:

(define (deep-reverse ls) 
    (define (deep-reverse-2 ls acc) 
    (if (null? ls) 
     acc 
     (if (list? (car ls)) 
      (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc)) 
      (deep-reverse-2 (cdr ls) (cons (car ls) acc))))) 
    (deep-reverse-2 ls '())) 

Esto comprueba si el elemento es una lista antes de añadir a la lista, y si lo es, se invierte por primera vez . Como se llama a sí mismo para invertir la lista interna, puede manejar la anidación arbitraria.

(deep-reverse '(a (b c d) e)) ->'(e (d c b) a) que está en orden alfabético inverso, a pesar de que hay una lista anidada. evalúa como tal:

(deep-reverse-2 '(a (b c d) e) '()); Which calls 
(deep-reverse-2 '((b c d) e) '(a)) 
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a))) 
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d) '(b)) '(a))) 
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d) '(c b)) '(a))) 
(deep-reverse-2 '(e) (cons '(d c b) '(a))) 
(deep-reverse-2 '(e) '((d c b) a)) 
(deep-reverse-2 '() '(e (d c b) a)) 
'(e (d c b) a) 

Answer 3

Esta es una manera que usted puede hacer una función inversa que se aplica a las listas anidadas:

(define (reverse-deep l) 
    (map (lambda (x) (if (list? x) (reverse-deep x) x)) (reverse l))) 

Explicación de pseudo-código:
de inicio mediante la inversión de la lista como se haría normalmente
Luego, para cada elemento de la lista invertido:
- Si el elemento es una lista en sí: Aplicar el procedimiento de forma recursiva
- Else: No toque el elemento

Answer 4

que utiliza un código similar al inserto tipo

(define deep-rev-list 
    (lambda (l) 
    (cond ((null? l) (quote())) 
      ((atom? (car l)) 
      (swap-till-end (carl) (deep-rev-list (cdr l)))) 
      (else 
      (swap-till-end (deep-rev-list (car l)) (deep-rev-list (cdr l))))))) 


(define swap-till-end 
    (lambda (elm lst) 
     (cond ((null? lst) (cons elm '())) 
      (else 
       (cons (car lst) (swap-till-end elm (cdr lst))))))) 

(define atom? 
    (lambda (x) 
    (and (not (null? x)) (not (pair? x))))) 

reproduzco de memoria. Puede haber algunos errores. Corregirá el código si ese es el caso. Pero la técnica utilizada es similar a los mandamientos para listas anidadas que se dan en el Pequeño Schemer :). He comprobado en DrRacket

(deep-rev-list '((1 2) (3) ((4 5)))) vuelve (((5 4)) (3) (2 1))

Answer 5

simplemente podría revertir los elementos de una lista usando foldr:

(foldr (lambda (a r) (append r (list a))) empty lst) 

Answer 6

Ésta es una función inversa de la raqueta, que me gusta mucho mejor que el esquema. Utiliza solo la función de coincidencia de patrones de coincidencia.

(define/match (rev l) 
    [('()) '()] 
    [((list a ... b)) (cons b (rev a))]) 

> (rev '(a (b c d) e)) 
'(e (b c d) a) 

Answer 7

Mi solución:

(define (rvrs ls) 
    (if (null? ls) 
    empty 
    (append (rvrs (cdr ls)) (cons (car ls) empty))))