1

これは元の形式です:

(define (split-by l p k)
  (let loop ((low '())
             (high '())
             (l l))
    (cond ((null? l)
           (k low high))
          ((p (car l))
           (loop low (cons (car l) high) (cdr l)))
          (else
           (loop (cons (car l) low) high (cdr l))))))
 

そして私はletを変換しようとしています、これは私が試したことです:

(define (split-by l p k)
  (lambda (loop)     
    (cond ((null? l) (k low high))
          ((p (car l)) 
           (loop low (cons (car l) high) (cdr l)))
          (else
           (loop (cons (car l) low) high (cdr l))
           ((low '()) (high '()) (l l))))))

これを修正する方法がわからないので、誰かが私が間違っていることを助けることができれば、大きな助けになるでしょう.

4

2 に答える 2

3

あなたがしていることを正しく理解していればp、述語であり、lこれに従ってリストを分割し、結果の2つのリストを集計関数で集計しますk。疑似コードで：

(split-by l p k) => (k {x in l | !p(x)} {x in l | p(x)})

your を置き換える際の問題letは、loop関数が再帰的に定義されていることです。形式は次のとおりです。

(define (loop low high lst)
    (cond
        ((null? lst) <some value>)
        (<some predicate> (loop (cons (car lst) low) high (cdr lst)))
        (else (loop low (cons (car lst) high) (cdr lst)))))

lambdaこれを関数で直接使用して、「内部」再帰部分を定義することは絶対にできますが、これは simple withoutを使用して作成することはできませんlet: 関数はそれ自体を参照する必要があり (再帰的であるため)、それを割り当てることによってのみそれを行うことができます名前。defineそれをしletます、あなたにそれをさせますが、どのように変えても、その自己言及が必要です。あなたが賢く、継続を渡す場合：

(lambda (low high lst cont)
    (cond
        ((null? lst) (agg high lst))
        ((pred? (car lst)) (cont low (cons (car lst) high) (cdr lst) cont))
        (else (cont (cons (car lst) low) high (cdr lst) cont))))

明示的にすることでその自己参照を削除しましたが、何として渡しますcontか? let を介してそれを割り当てた場合、それを参照するシンボルがあります。

(define (split-by2 lst pred? agg)
    (let ((f (lambda (low high lst cont)
                (cond
                    ((null? lst) (agg low high))
                    ((pred? (car lst)) (cont low (cons (car lst) high) (cdr lst) cont))
                    (else (cont (cons (car lst) low) high (cdr lst) cont))))))
        (f '() '() lst f)))

または、より簡潔に adefineを使用すると、まったく同じことが行われます (継続を渡す必要はありません)。

(define (split-by3 lst pred? agg)
    (define (f low high lst)
        (cond
            ((null? lst) (agg low high))
            ((pred? (car lst)) (f low (cons (car lst) high) (cdr lst)))
            (else (f (cons (car lst) low) high (cdr lst)))))
    (f '() '() lst))

それらはすべて同様に動作します。

(split-by '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))   
(split-by2 '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))   
(split-by3 '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))

しかし、再帰関数のシンボルを定義することから逃れることはできません*。

あなたの例がうまくいかなかった理由については、functionを作成し、引数として関数(上記で呼び出しました) を取り、その function を指定contしてロジックを適用することを除いて、完全に正常に動作しています。それを渡すための「ループ」がないため（バインドしていないため）、その関数を返し、何もしません（さらに、返されたでは定義されていません）。looplambdalowhigh

*ラムダでコンビネータを使用して実行できるため、これは完全に正しいわけではありませんが、本来よりもはるかに複雑になります。

(define Y
  (lambda (h)
    ((lambda (x) (x x))
     (lambda (g)
       (h (lambda args (apply (g g) args)))))))

(define (split-ycomb lst pred? agg)
    ((Y 
        (lambda(f)
            (lambda (low high l)
                (cond
                    ((null? l) (agg low high))
                    ((pred? (car l)) (f low (cons (car l) high) (cdr l)))
                    (else (f (cons (car l) low) high (cdr l)))))))
    '() '() lst))

または、インラインコンビネータを使用した、さらに醜い純粋なバージョンの場合:

(define (split-ycomb2 lst pred? agg)
    (((lambda (h)
        ((lambda (x) (x x))
            (lambda (g)
                (h (lambda args (apply (g g) args)))))) 
        (lambda(f)
            (lambda (low high l)
                (cond
                    ((null? l) (agg low high))
                    ((pred? (car l)) (f low (cons (car l) high) (cdr l)))
                    (else (f (cons (car l) low) high (cdr l)))))))
    '() '() lst))

期待どおりに動作するもの (ラムダのレイヤーのおかげ):

(split-ycomb '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))
(split-ycomb2 '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))
于 2016-02-23T09:48:22.690 に答える
1

あなたは書いてみることができます

(define (split-by l p k)  
  (let ((loop 
          (lambda (low high l)
             (cond 
               ((null? l)
                  (k low high))
               ((p (car l))
                  (loop low (cons (car l) high) (cdr l)))
               (else
                  (loop (cons (car l) low) high (cdr l)))))))
    (loop '() '() l)))

しかし、問題は、lambdaの本体が定義されているためloop、まだ名前を参照できないことです ( に置き換えるだけで機能しますが、ここで求めているのはそれではありません)。letletrec

loopによって定義されている名前は、それの init 式内のスコープlet内にありません。それが非再帰的であることの意味です。その再帰的なバリアントである は、定義されている名前をinit-expression 内の範囲内にすることを提供します (init-value が計算されるときにその値を照会することは許可されていません)。letletrec

ただし、単純なトリック (貧乏人のY コンビネーターのようなもの) があります。これは、レプリケーションを通じて真の自己参照をエミュレートします。これは、次のようにself-applicationによって実現されます。

(define (split-by l p k)  
  (let ((foo 
          (lambda (loop low high l)
             (cond 
               ((null? l)
                  (k low high))
               ((p (car l))
                  (loop loop low (cons (car l) high) (cdr l)))
               (else
                  (loop loop (cons (car l) low) high (cdr l)))))))
    (foo foo '() '() l)))

太陽の下で再び大丈夫です。つまり、非再帰的です。ラムダ本体内で参照されている名前は、ラムダパラメータにすぎないためlet、スコープ内にあります。loop

そして、はプレーンで非再帰的であるため、単純なアプリケーションでletこれを簡単に書き直すことができます。lambda

(define (split-by l p k)  
  ((lambda (foo) (foo foo '() '() l))   ; (lambda (loop ...
   (lambda (loop low high l)            ;   is duplicated into the two foos
             (cond 
               ((null? l)
                  (k low high))
               ((p (car l))
                  (loop loop low (cons (car l) high) (cdr l)))
               (else
                  (loop loop (cons (car l) low) high (cdr l)))))))
于 2016-02-23T15:07:02.667 に答える