¿Ayuda a explicar cómo funcionan los "contras" en Scheme?

Question

Esta es la función que elimina el último elemento de la lista. ..

(define (remove-last ll) 
    (if (null? (cdr ll)) 
     '() 
     (cons (car ll) (remove-last (cdr ll))))) 

Así que desde mi entendimiento si cons una lista (por ejemplo a b c con una lista vacía, es decir '(), deberíamos obtener a b c Sin embargo, las pruebas en las ventanas de interacción (DrScheme), el resultado fue:

Si (cons '()' (ABC))

(() a b c) 

Si (cons '(abc)'())

((a b c)) 

Soy como qué demonios :(! Luego volví a mi problema, eliminé todos los elementos que tienen un duplicado adyacente. Por ejemplo, (a b a a c c) sería (a b).

(define (remove-dup lst) 
    (cond ((null? lst) '()) 
     ((null? (cdr lst)) (car lst)) 
     ((equal? (car lst) (car (cdr lst))) (remove-dup (cdr (cdr lst)))) 
     (else (cons (car lst) (car (cdr lst)))) 
     ) 

) 

No era correcto, sin embargo me doy cuenta de la respuesta tener un . entre a b. ¿Cómo pudo pasar esto?

`(a . b)` 

sólo había una llamada a cons en mi código anterior, no pude ver qué parte podría generar este .. ¿Alguna idea?

Gracias,

Answer 1

cons pares de construcción, no listas. Los intérpretes de Lisp usan un 'punto' para separar visualmente los elementos del par. Por lo tanto, (cons 1 2) imprimirá (1 . 2). car y cdr respectivamente devuelven el primer y el segundo elemento de un par. Las listas se construyen sobre pares. Si el cdr de un par apunta a otro par, esa secuencia se trata como una lista. El cdr del último par apuntará a un objeto especial llamado null (representado por '()) y le indicará al intérprete que ha llegado al final de la lista. Por ejemplo, la lista '(a b c) se construye mediante la evaluación de la expresión siguiente:

> (cons 'a (cons 'b (cons 'c '()))) 
(a b c) 

El procedimiento list proporciona un acceso directo para las listas creando:

> (list 'a 'b c) 
(a b c) 

La expresión (cons '(a b c)()) crea un par cuyo primer elemento es una lista.

El procedimiento remove-dup está creando un par en la cláusula else. En su lugar, debe crear una lista llamando recursivamente al remove-dup y colocando el resultado como el segundo elemento del par. He limpiado el procedimiento un poco:

(define (remove-dup lst) 
    (if (>= (length lst) 2) 
     (if (eq? (car lst) (cadr lst)) 
      (cons (car lst) (remove-dup (cddr lst))) 
      (cons (car lst) (remove-dup (cdr lst)))) 
     lst)) 

Pruebas:

> (remove-dup '(a b c)) 
(a b c) 
> (remove-dup '(a a b c)) 
(a b c) 
> (remove-dup '(a a b b c c)) 
(a b c) 

véase también la sección 2.2 (datos jerárquicos y la propiedad de cierre) en SICP.

Para completar, aquí es una versión de remove-dup que elimina todos los elementos adyacentes idénticas:

(define (remove-dup lst) 
    (if (>= (length lst) 2) 
     (let loop ((f (car lst)) (r (cdr lst))) 
     (cond ((and (not (null? r))(eq? f (car r))) 
       (loop f (cdr r)))    
       (else 
       (cons (car lst) (remove-dup r))))) 
     lst)) 

Answer 2

Aquí en pseudocódigo:

clase Par { objeto la izquierda, la derecha Objeto}.

función cons (Objeto a la izquierda, Objeto derecho) {return new Pair (left, right)};

Así, 1. contras ('A', B) => Par ('A', B) 2. contras ('A, NIL) => Par (' A, NIL) 3. contras (NIL, 'A) => Par (NIL,' A) = 4. cons ('A, cons (' B, NIL)) => Par ('A, Par (' B, NIL)) 5. contras (contras ('A' B), NIL)) => Pair (Pair ('A,' B), NIL)

Veamos las izquierdas y los derechos en todos los casos: 1. 'A y' B son átomos , y todo el par no es una lista, entonces (const 'a' b) da (a. b) en el esquema 2. NIL es una lista vacía y 'A es un átomo, (cons' a '()) da una lista (a) 3. NIL y 'A como arriba, pero a la izquierda está la lista (!), (contra'() 'a) da par ((). a) 4. Caso fácil, tenemos la lista adecuada aquí (a b). 5. Lista adecuada, la cabeza es un par (a. B), la cola está vacía.

Espero, ya entendiste la idea.

En cuanto a su función. Estás trabajando en LIST pero construyes PARES. Las listas son pares (de pares), pero no todos los pares son listas. Para ser un par de listas, debe tener NIL como cola.

(a b) par & lista (a.b) pair no lista

A pesar de las desventajas, su función tiene errores, simplemente no funciona en '(a b a a c c d). Como esto no está relacionado con su pregunta, no voy a publicar una solución para esto aquí.