4

を使用せずに、純粋に機能的な方法でこの問題を解決しようとしていset!ます。

フィボナッチ数列の各数値に対して特定のラムダを永久に呼び出す関数を作成しました。

(define (each-fib fn)
  (letrec
    ((next (lambda (a b)
             (fn a)
             (next b (+ a b)))))
    (next 0 1)))

これは可能な限り簡潔だと思いますが、これを短くすることができれば、私に教えてください:)

上記のような定義を使用するnと、フィボナッチ数列から最初の数値を取得してリストを返す別の関数を作成できますが、変数の突然変異を使用して状態を追跡することはできません (これは実際には機能しないと理解しています) 。

関数のシグネチャは、次と同じである必要はありません...使用each-fibせずに利用するアプローチは問題ありませんset!。

(take-n-fibs 7) ; (0 1 1 2 3 5 8)

私が使用できるある種の継続 + カリー化のトリックがあると推測していますが、使用したいという気持ちに戻り続けていset!ます。

4

4 に答える 4

3

遅延評価による遅延コードを使用して実装された、これを試してください。

(define (each-fib fn)
  (letrec
      ((next (lambda (a b)
               (fn a)
               (delay (next b (+ a b))))))
    (next 0 1)))

(define (take-n-fibs n fn)
  (let loop ((i n)
             (promise (each-fib fn)))
    (when (positive? i)
      (loop (sub1 i) (force promise)))))

前述したように、名前付きeach-fibを使用してさらに単純化できます:let

(define (each-fib fn)
  (let next ((a 0) (b 1))
    (fn a)
    (delay (next b (+ a b)))))

いずれにせよ、promise を作成するプリミティブeach-fibを使用するには、少し変更する必要がありました。delay

promiseは、 を介してオンデマンドで評価される式をカプセル化しますforce。promise がforced になった後は、promise の以降のすべての force が同じ結果を生成します。

元の (変更されていない) 手順が無期限に繰り返されるのを止める方法は思いつきません。しかし、上記の変更により、take-n-fibs必要な数の値の遅延評価を強制し続けることができます。

また、take-n-fibs各値を順番に印刷または処理するための関数を受け取るようになりました。次のように使用します。

(take-n-fibs 10 (lambda (n) (printf "~a " n)))
> 0 1 1 2 3 5 8 13 21 34 55
于 2012-06-24T16:44:25.847 に答える
1

私はいくつかの変種を書きました。最初にあなたは

(define (each-fib fn)
  (letrec
    ((next (lambda (a b)
             (fn a)
             (next b (+ a b)))))
    (next 0 1)))

短く書くことができます。このパターンは頻繁に使用されるため、と呼ばれる特別な構文named letが導入されています。名前付きletを使用すると、関数は次のようになります。

(define (each-fib fn)
  (let next ([a 0] [b 1])
    (fn a)
    (next b (+ a b))))

ある関数から別の関数に制御を流すために、TCOをサポートする言語では継続渡しスタイルを使用できます。各関数は、しばしばk（継続用）と呼ばれる追加の引数を取得します。関数kは、次に何をするかを表します。

このスタイルを使用すると、次のようにプログラムを作成できます。

(define (generate-fibs k)
  (let next ([a 0] [b 1] [k k])
    (k a (lambda (k1) 
           (next b (+ a b) k1)))))

(define (count-down n k)
  (let loop ([n n] [fibs '()] [next generate-fibs])
    (if (zero? n)
        (k fibs)
        (next (λ (a next)
                (loop (- n 1) (cons a fibs) next))))))

(count-down 5 values)

手動でスタイルを書くのは少し面倒なので、コルーチンを導入すると便利かもしれません。使用しないというあなたのルールを破る私は、新しいフィボナッチ数を繰り返し消費するset!共有変数を使用することを選択しました。カウントダウンが終了すると、ルーチンは単に値を読み取ります。fibsgenerate-fibscount-down

(define (make-coroutine co-body)
  (letrec ([state (lambda () (co-body resume))]
           [resume (lambda (other)
                     (call/cc (lambda (here)
                                (set! state here)
                                (other))))])
    (lambda ()
      (state))))

(define fibs '())

(define generate-fib
  (make-coroutine 
   (lambda (resume)
     (let next ([a 0] [b 1])
       (set! fibs (cons a fibs))
       (resume count-down)
       (next b (+ a b))))))

(define count-down
  (make-coroutine   
   (lambda (resume)
     (let loop ([n 10])
       (if (zero? n)
           fibs
           (begin
             (resume generate-fib)
             (loop (- n 1))))))))

(count-down)

そして、あなたが通信スレッドを備えたバージョンを手に入れるボーナス：

#lang racket
(letrec ([result #f]
         [count-down 
          (thread 
           (λ ()
             (let loop ([n 10] [fibs '()])
               (if (zero? n)
                   (set! result fibs)
                   (loop (- n 1) (cons (thread-receive) fibs))))))] 

         [produce-fibs
          (thread
           (λ ()
             (let next ([a 0] [b 1])
               (when (thread-running? count-down)
                 (thread-send count-down a)
                 (next b (+ a b))))))])
  (thread-wait count-down)
  result)

スレッドバージョンはRacket固有であり、他のバージョンはどこでも実行する必要があります。

于 2012-06-24T16:20:57.660 に答える
1

フィボナッチ要素に対して反復関数を提供します。各要素を繰り返し処理する代わりに、結果を蓄積foldしたい場合は、 ではなく(or reduce)になる別のプリミティブを使用する必要がありますiter。
(継続を使用して anを に変換することは可能かもしれませんが、それはおそらく aまたはミューテーションを使用した直接的な解決策よりも読みにくく、効率的ではありません。)iterfoldfold

ただし、何をしているのかを理解している限り、突然変異によって更新されたアキュムレータを使用することも問題ないことに注意してください: 便宜上、ローカルで可変状態を使用していますが、関数take-n-fibsは外部から見ると観測的に純粋であるため、「プログラム全体を副作用で汚染します。

fold-fib独自のコードから適用された の簡単なプロトタイプ。「いつフォールディングを停止するか」に関して、私は任意の選択をしました。関数がnullを返した場合、フォールディングを続行する代わりに、現在のアキュムレータを返します。

(define (fold-fib init fn) (letrec ([next (lambda (acc a b)
      (let ([acc2 (fn acc a)])
        (if (null? acc2) acc
            (next acc2 b (+ a b)))))])
      (next init 0 1)))

(reverse (fold-fib '() (lambda (acc n) (if (> n 10) null (cons n acc)))))

折りたたみを終了するためのより堅牢な規則を用意することをお勧めします。

于 2012-06-24T14:51:01.827 に答える
0

リストを作成するのは難しいでしょう。ただし、結果の表示は引き続き実行できます (非常に悪い方法で)。

#lang racket

(define (each-fib fn)
  (letrec
    ((next (lambda (a b)
             (fn a)
             (next b (+ a b)))))
    (next 0 1)))



(define (take-n-fibs n fn)
  (let/cc k
        (begin
          (each-fib (lambda (x) 
                      (if (= x (fib (+ n 1)))
                          (k (void))
                          (begin
                            (display (fn x))
                            (newline))))))))


(define fib
  (lambda (n)
    (letrec ((f
              (lambda (i a b)
                (if (<= n i)
                    a
                    (f (+ i 1) b (+ a b))))))
      (f 1 0 1))))

通常のフィボナッチ関数をエスケープとして使用していることに注意してください (非常に悪い方法で言ったように)。このようなプログラミングを推奨する人はいないと思います。

ともかく

(take-n-fibs 7 (lambda (x) (* x x))) 
0
1
1
4
9
25
64
于 2012-06-24T18:40:28.497 に答える