8

私は、Scheme でのコレクター関数の使用法を理解するのに苦労しています。私は本「The Little Schemer」(Daniel P. Friedman と Matthias Felleisen 著) を使用しています。いくつかの説明を含む包括的な例は、私を大いに助けてくれます。コレクター関数を使用する関数の例は、次のスニペットです。

(define identity
  (lambda (l col)
    (cond
      ((null? l) (col '()))
      (else (identity
              (cdr l)
              (lambda (newl)
                (col (cons (car l) newl))))))))

...呼び出しの例を使用して(identity '(a b c) self)、 being とself-functionbeingを呼び出します(define self (lambda (x) x))。このidentity関数は指定された list を返すlため、指定された呼び出しの出力は になります(a b c)。使用されている正確な言語は、R5RS レガシー言語です。

4

2 に答える 2

5

これらの「コレクター」関数が定義でどのように定義されているかを考えるとidentity、呼び出し

(identity xs col)

任意のリストxsといくつかの「コレクター」関数colに対して、呼び出しと同等です

(col xs)

したがって、同じリストが「返され」ます。つまり、その引数「コレクター」/継続関数に渡されますcol。それはその名前を説明していますidentity、それでは。

比較のために、aは次のreverseようにコーディングできます。

(define reverse     ; to be called as e.g. (reverse l display)
  (lambda (l col)
    (cond
      ((null? l) (col '()))        ; a reversed empty list is empty
      (else (reverse (cdr l)       ; a reversed (cdr l) is newl --
                     (lambda (newl)    ; what shall I do with it when it's ready?
                       (col            ; append (car l) at its end and let col
                          (append newl                           ; deal with it!
                                  (list (car l))))))))))

このスタイルのプログラミングは、継続渡しスタイルとして知られています。各関数には、残りの計算の結果が渡されると想定される「継続」が渡されるため、元の継続/コレクター関数に最終結果が渡されます。最終的。各コレクターの引数は、それが受け取る将来の「結果」を表し、コレクター関数自体がそれをどのように処理するかを指定します。

用語に惑わされないでください: これらの関数は、関数によってキャプチャされた「継続」ではなくcall/cc、通常の Scheme 関数であり、「次に行われること」を表します。

定義は次のように読むことができます。

identity :
  to transform a list xs 
        with a collector function col,
    is 
    | to call (col xs)                              , if xs is empty, or
    | to transform (cdr xs)  
        with a new collector function col2  
        such that
              (col2 r)  =  (col (cons (car xs) r))  , otherwise.

(または、これを疑似コードで次のように記述できます)

(identity list col)  =
  | empty? list           ->  (col list)
  | match? list (x . xs)  ->  (identity xs col2)
                                where 
                                (col2 r)  =  (col (cons x r))

col2前の handler に r渡すことによって、その引数を処理します。この手段は に変換されますが、値として返される代わりに、さらに処理するために に渡されます。したがって、新しい値を前の「コレクター」に渡すことで、新しい値を「返します」。(cons x r)colr(cons x r)col(cons x r)

例としての呼び出しの例:

(identity (list 1 2 3) display)     

= (identity (list 2 3) k1)
      ; k1 =  (lambda (r1) (display (cons 1 r1)))           =  display ° {cons 1}

= (identity (list 3)  k2)
      ; k2 =  (lambda (r2) (k1 (cons 2 r2)))                     =  k1 ° {cons 2} 

= (identity (list )  k3)
      ; k3 =  (lambda (r3) (k2 (cons 3 r3)))                     =  k2 ° {cons 3} 

= (k3 '())                        ; (((display ° {cons 1}) ° {cons 2}) ° {cons 3}) []

= (k2 (cons 3 '()))                    ; ((display ° {cons 1}) ° {cons 2}) [3]

= (k1 (cons 2 (list 3)))                    ; (display ° {cons 1}) [2,3]

= (display (cons 1 (list 2 3)))                  ; display [1,2,3]

= (display (list 1 2 3))

更新:最近私が好んで使用しているパターン マッチングの疑似コードでは、次のように記述できます。

identity []        col  =  col []
identity [a, ...d] col  =  identity d ( newl =>  col [a, ...newl] )

と

reverse  []        col  =  col []
reverse  [a, ...d] col  =  reverse  d ( newl =>  col [...newl, a] )

うまくいけば、視覚的に非常に明白であり、ほとんど説明する必要はありません!

于 2016-11-26T18:23:49.513 に答える
2

（「承認済み」マークがないことが示すように）残っている疑問がある場合に備えて、残りの疑問を明確にすることができることを期待して、2番目の回答を追加します。

Gerald J. Sussman の声で、SICP の講義で聞いたり見たりしたように、ビデオがインターネット チューブのあちこちで利用できるので、書いているときに読むことができます。

(define identity

「アイデンティティ」は次のように定義されています。

  (lambda

その関数は、与えられたときに

           (l col)

2 つの引数、lおよびcol

    (cond
      ((null? l)

-- (null? l)true の場合 --

  • OK、これはlリストであることを意味します、NB 

                   (col '()))

式の値を返す (col '())

  • OK、これcolは関数であり、1 つの引数を期待していることを意味し、1 つの可能性として空のリスト、
      (else (identity (cdr l)

そうでなければ、更新された値で末尾再帰呼び出しを行います(cdr l)。

                      (lambda (newl)
                        (col (cons (car l) newl)))))))

もう 1 つは新しく構築された関数で、その引数(期待どおりのリスト-- 同じロールに表示されるため、同じ規則に従う必要があります) を指定して呼び出されると、次に、 listの前に付けた結果の空でないリストを持つ関数。newlcolcol(car l)newl

したがって、この関数 はidentity次の方程式に従います。

( identity   (cons (car l) (cdr l))           col                        )
==
( identity       (cdr l)     (lambda (newl)  (col  (cons (car l) newl))) )

と

( identity   '()   col )
==
( col        '()       )

関数呼び出しを回す反復プロセスを記述する

(identity [a,      b,      c, ...,    n]    col      )

通話に

(col
     (cons a (cons b (cons c ... (cons n '()) ... ))))

提供された関数に引数として渡す前に、まったく同じリストを新たに再作成colします。

于 2018-09-08T13:52:27.697 に答える