Aplatir une liste en utilisant uniquement les formes dans « The Little Schemer »

Question

Je vais par la petite Schemer d'apprendre le schéma (comme un ancien programmeur C) et comme un exercice que j'essayé d'écrire une procédure pour aplatir une liste à l'aide uniquement les formes dans The Little Schemer ; À savoir, define, lambda, cond, car, cdr, and, or, etc., mais pas append. Je pensais que ce serait facile, mais je ne l'ai pas été en mesure de trouver une solution. Comment puis-je faire?

Answer 1

J'ai une version qui utilise uniquement les opérations « premiers principes » et est efficace (ne pas exiger plus d'un laissez-passer par l'une des listes, à la différence des solutions basées sur append-). : -)

Il le fait en définissant deux blocs simples de construction (fold et reverse), puis définir flatten (et son aide, reverse-flatten-into) au-dessus ceux (et remarquez comment chaque fonction est juste une ou deux longues lignes):

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

Les fonctions externes ne sont utilisées:. cons, car, cdr, null? et pair?

L'idée clé de cette fonction est que fold est très opération puissante et devrait faire partie de la boîte à outils de tout Schemer. Et, comme on le voit dans le code ci-dessus, il est si simple de construire à partir des premiers principes!

Answer 2

Je ne suis pas familier avec les primitives peu Schemer, de sorte que vous devrez peut-être ce goût de costume.

Je ne suis pas sûr que ce soit la réponse que vous voulez, mais vous pouvez écrire à l'aide append primitives:

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

La fonction flatten pourrait alors être écrit en termes de cela.

Je ne sais pas si cela est en dehors des règles ou non:)

Answer 3

Voici une tentative. Il se contenter d'utiliser et d'éviter les inconvénients append, car il ne ébrèche la première paire non, il peut aller et conses que la Aplatir d'une nouvelle queue, il a construit. Parfois, il réécrit la liste puis appelle simplement à nouveau plaquer. Def pas la façon la plus efficace.

Code fixe:

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