「The Little Schemer」のフォームのみを使用してリストを平らにします

Question

（古いCプログラマーとして）スキームを学ぶために小さなスキーマーを調べています。 それだけ リトルスキーマーのフォーム。つまり、 define, lambda, cond, car, cdr, and, or, 、など いいえ append. 。私はそれが簡単だと思ったが、私は解決策を考え出すことができなかった。これどうやってするの ？

Answer 1

「ファースト原理」操作のみを使用し、効率的なバージョンがあります（リストを1つ以上パスする必要はありません。 append- ベースのソリューション）。 :-)

2つの単純なビルディングブロックを定義することでこれを行います（fold と reverse）、そして定義します flatten （そしてそのヘルパー、 reverse-flatten-into）それらの上に（そして、各機能が1行または2行の長さであることに注意してください）：

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

使用される唯一の外部関数は次のとおりです。 cons, car, cdr, null?, 、 と pair?.

この関数からの重要な洞察はそれです fold aです とても 強力な操作であり、スキーマーのツールキットの一部である必要があります。そして、上記のコードに見られるように、最初の原則から構築するのはとても簡単です！

Answer 2

私はリトルスキーマープリミティブに精通していないので、これに合わせてこれを味わう必要があるかもしれません。

これがあなたが望む答えであるかどうかはわかりませんが、あなたは書くことができます append プリミティブの使用：

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

flatten この点で機能を記述できます。

これがルールの外側にあるかどうかはわかりません:)

Answer 3

これが試みです。短所を使用して避けることで逃げます。なぜなら、それは到達できる最初のペアを削り取るだけで、それが構築した新しい尾の平坦化に合意するからです。リストを書き換えてから、再びFlattenを呼び出します。最も効率的な方法ではありません。

修正コード：

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