スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#入門初級編 第9回  CPS (Continuation Passing Style)(2)

今回は少し複雑なCPSを紹介します。 
まずはフィボナッチ数列の例です。
フィボナッチ数列とはa(n) = a(n-1) + a(n-2)という漸化式で決定される数列です。まずはa(0)=1,a(1) = 2の場合を考えます。
 
次の関数でフィボナッチ数列の第n項を求めることができます。
let rec fibo n cont =
    if n = 0  then 
        1 |> cont
    elif n = 1 then
        2 |> cont
    else
        fibo (n - 1) (fun x -> fibo (n - 2) (fun y -> (x + y) |> cont ))
 
fibo (n - 1) (fun x -> fibo (n - 2) (fun y -> (x + y) |> cont )) の部分は 
fibo (n - 1) (fun x -> fibo (n - 2) (fun y -> cont (x + y) ))とも
fibo (n - 1) (fun x  -> fibo (n - 2) (((+) x) >> cont)) とも書けます。
 
それではどのようになっているのか調べてみます。
 
まずは定義を再掲します。
let rec fibo n cont =
    if n = 0  then 
        a(0) |> cont
    elif n = 1 then
        a(1) |> cont
    else
          fibo (n - 1) (fun x -> fibo (n - 2) (fun y -> (x + y) |> cont ))
 
 n=2,3の時を具体的に調べてみます。         
 
fibo 2 cont =
    fibo 1 (fun x -> fibo 0 (fun y -> (x + y) |> cont ))
    = a(1) |> (fun x -> fibo 0 (fun y -> (x + y) |> cont ))
    = fibo 0 (fun y -> (a(1) + y) |> cont) //xがa(1)となる
    = a(0) |> (fun y -> (a(1) + y) |> cont)
    = (a(1) + a(0)) |> cont //yがa(0)となる
    = a(2) |> cont //#1
 
fibo 3 cont =
    fibo 2 (fun x -> fibo 1 (fun y -> (x + y) |> cont ))
    //#1でcont を(fun x -> fibo 1 (fun y -> (x + y) |> cont ))に置き換えて
  = a(2) |> (fun x -> fibo 1 (fun y -> (x + y) |> cont ))
  = fibo 1 (fun y -> (a(2) + y) |> cont)) //xがa(2)となる
  = a(1) |> (fun y -> (a(2) + y) |> cont)) 
  = (a(2) + a(1)) |> cont //yがa(1)となる
  = a(3) |> cont //#2
  
  ......
  
fibo (n -1) (fun x -> ??? |>cont)の???の部分はnより後の継続の適用結果(この場合はxをa(n-1)として考える)をxとしてnの段階で、その値にどのような作用を加えるかを表したものとなります。a(n)=a(n-1)+a(n-2)より、このxに更にa(n-2)の値を加えるという作用を???の部分に書けばよいことになります。
a(n-2)の値は実際に関数が適応されていく時にfibo(n-2) (fun y -> ....)のyの部分に渡されるので、
(fun x -> fibo (n - 2) (fun y -> (x + y) |> cont ))としてやれば、実際にx,yに値が渡される時には
xにa(n-1)、yにa(n-2)が渡されて、
a(n-1) |> (fun x -> fibo (n - 2) (fun y -> (x + y) |> cont ))
= fibo (n-2) (fun y -> (a(n-1) + y) |> cont))
= a(n-2) |> (fun y -> (a(n-1) + y) |> cont))
= a(n-1) + a(n-2) |> cont
= a(n) |> cont となります。
 
実行例
> fibo 2 id;;
val it : int = 3
> fibo 3 id;;
val it : int = 5
> fibo 4 id;;
val it : int = 8
 
(練習)
a(n) = a(n-1) +2* a(n-2)+1,a(0)=1,a(1)=2の場合で、上と同様に
let rec fibo n cont =
    .....
と定義してください。
(解答例)
 
let rec fibo n cont =
    if n = 0  then 
        1 |> cont
    elif n = 1 then
        2 |> cont
    else
        fibo (n - 1) (fun x -> fibo (n - 2) (fun y -> (x + 2*y + 1) |> cont ))
(実行例)
> fibo 2 id;;
val it : int = 5
> fibo 3 id;;
val it : int = 10
> fibo 4 id;;
val it : int = 21
 
(練習)
a(n) = a(n-1) + a(n-2)+ a(n-3) ,a(0)=1,a(1) = 2,a(2) = 3の場合で、上と同様に
let rec fibo n cont =
    .....
と定義してください。
(解答例)
 let rec fibo n cont =
    if n = 0  then 
        1 |> cont
    elif n = 1 then
        2 |> cont
    elif n = 2 then
        3 |> cont
    else
        fibo (n - 1) (fun x -> fibo (n - 2) (fun y -> fibo (n - 3) (fun z ->  (x + y + z) |> cont )))
 
(実行例)
> fibo 3 id;;
val it : int = 6
> fibo 4 id;;
val it : int = 11
> fibo 5 id;;
val it : int = 20
 
(備考)この手法により末尾再帰でフィボナッチ数列の項を求めることができるのですが、決して効率の良い方法とはなっていません。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。