4

私は（古いCプログラマーとして）Schemeを学ぶためにThe LIttle Schemerを経験しており、演習として、TheLittleSchemerのフォームのみを使用してリストをフラット化する手順を書こうとしました。つまり、、、、、、、、などですが、defineでlambdaはありません。簡単だと思いましたが、解決策が思いつきませんでした。これどうやってするの ？condcarcdrandor append

4

3 に答える 3

12

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です。carcdrnull?pair?

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

于 2011-09-06T18:33:53.120 に答える
2

これが試みです。コンスを使用して追加を回避することで回避できます。これは、到達できる最初の非ペアのみを削り取り、構築した新しいテールのフラット化にコンスするためです。場合によっては、リストを書き換えてから再度 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 '()))))
于 2011-09-06T01:55:41.087 に答える
2

私は Little Schemer のプリミティブに慣れていないので、それに合わせて味付けする必要があるかもしれません。

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

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

関数は、これflattenを使って書くことができます。

これがルール外かどうかはわかりません:)

于 2011-09-06T00:16:10.373 に答える