Reduzieren Sie eine Liste, indem Sie nur die Formulare aus „The Little Planer“ verwenden.

Question

Ich lese „The LIttle Schemer“ durch, um Scheme zu lernen (als alter C-Programmierer), und als Übung habe ich versucht, eine Prozedur zu schreiben, mit der eine Liste reduziert werden kann nur die Formen in The Little Schemer;D.h., define, lambda, cond, car, cdr, and, or, usw., aber nicht append.Ich dachte, es wäre einfach, aber ich konnte keine Lösung finden.Wie kann ich das machen ?

Answer 1

Ich habe eine Version, die nur „First-Principles“-Operationen verwendet und effizient ist (im Gegensatz dazu ist nicht mehr als ein Durchlauf durch eine der Listen erforderlich append-basierte Lösungen).:-)

Dies geschieht durch die Definition zweier einfacher Bausteine ​​(fold Und reverse) und dann definieren flatten (und sein Helfer, reverse-flatten-into) darüber (und beachten Sie, dass jede Funktion nur eine oder zwei Zeilen lang ist):

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

Die einzigen verwendeten externen Funktionen sind: cons, car, cdr, null?, Und pair?.

Die wichtigste Erkenntnis aus dieser Funktion ist Folgendes fold ist ein sehr leistungsstarke Operation und sollte Teil jedes Schemer-Toolkits sein.Und wie im obigen Code zu sehen ist, ist es so einfach, nach den ersten Prinzipien zu bauen!

Answer 2

Ich bin nicht mit den Little Schemer Primitive vertraut, daher müssen Sie dies möglicherweise für den Anzug ansehen.

Ich bin mir nicht sicher, ob dies die Antwort ist, die Sie möchten, aber Sie können schreiben append Verwendung von Primitiven:

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

Das flatten Die Funktion könnte dann in Bezug darauf geschrieben werden.

Ich bin mir nicht sicher, ob dies außerhalb der Regeln liegt oder nicht :)

Answer 3

Hier ist ein Versuch. Es kommt durch die Verwendung von Nachteilen und das Vermeiden von Anhang davon, da es nur den ersten Nicht-Pair abfährt, zu dem es gelangen kann, und dies zu dem Abflachen eines neuen Schwanzes, den es aufgebaut hat, konzipiert. Manchmal schreibt es die Liste neu, dann ruft einfach wieder flach auf. Definitiv nicht der effizienteste Weg.

Behobener Code:

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