Aplanar una lista usando solo los formularios en "The Little Schemer"

Question

Estoy pasando por el pequeño esquema para aprender el esquema (como un antiguo programador de C) y como ejercicio intenté escribir un procedimiento para aplanar una lista usando solamente las formas en el pequeño esquema; Es decir, define, lambda, cond, car, cdr, and, or, etc., pero no append. Pensé que sería fácil, pero no he podido encontrar una solución. Cómo puedo hacer esto ?

Answer 1

Tengo una versión que usa solo operaciones de "primeros principios" y es eficiente (no requiere más de un paso a través de ninguna de las listas, a diferencia de append-riadas basadas). :-)

Hace esto definiendo dos bloques de construcción simples (fold y reverse), y luego definiendo flatten (y su ayudante, reverse-flatten-into) sobre aquellos (y notar cómo cada función tiene solo una o dos líneas de largo):

;; Similar to SRFI 1's fold
(define (fold1 kons knil lst)
  (if (null? lst)
      knil
      (fold1 kons (kons (car lst) knil) (cdr lst))))

;; Same as R5RS's reverse
(define (reverse lst)
  (fold1 cons '() lst))

;; Helper function
(define (reverse-flatten-into x lst)
  (if (pair? x)
      (fold1 reverse-flatten-into lst x)
      (cons x lst)))

(define (flatten . lst)
  (reverse (reverse-flatten-into lst '())))

Las únicas funciones externas utilizadas son: cons, car, cdr, null?, y pair?.

La información clave de esta función es que fold es un muy Potente operación, y debe formar parte de cualquier kit de herramientas de esquema. Y, como se ve en el código anterior, ¡es muy simple de construir desde los primeros principios!

Answer 2

No estoy familiarizado con las pequeñas primitivas del esquema, por lo que es posible que deba darle sabor a esto para adaptarse.

No estoy seguro de si esta es la respuesta que quieres, pero puedes escribir append Usando primitivas:

(define (append l1 l2)
  (cond
    ((null? l1) l2)
    (else (cons (car l1) (append (cdr l1) l2)))))

los flatten La función podría escribirse en términos de esto.

No estoy seguro si esto está fuera de las reglas o no :)

Answer 3

Aquí hay un intento. Se sale con la suya con los contras y evitando apagar, porque solo interrumpe el primer no par que puede llegar y considera que para aplanar de una cola nueva que ha construido. A veces reescribe la lista y luego solo llama a Flatten nuevamente. Definitivamente no es la forma más eficiente.

Código fijo:

(define (flatten x)
  (cond 
    ((null? x) x)
    ((and (pair? x) 
          (not (pair? (car x))))
     (cond 
       ((null? (car x)) (flatten (cdr x)))
       (else (cons (car x) (flatten (cdr x))))))
    ((and (pair? x)
          (pair? (car x)))
     (flatten (cons (caar x) 
                    (cons (cdar x) (cdr x)))))
    (else (cons x '()))))