スポンサーサイト

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

F#入門初級編第10回  CPS (Continuation Passing Style)(3)

今回は二分木を対象にCPSを考えます。
 
なお対象としては次のような二分木をtという名前で取り扱うことにします。
       3
      / \
     7   4
    /|  / \
   2   E   5   9
  /|   /|   / \  
 E E E    E    E   E 
 
type BTree<'a> = 
    |Empty 
    |Node of ('a * BTree<'a> * BTree<'a>) 
 
let t =
    Node(3,Node(7,Node(2,Empty,Empty),Empty),Node(4,Node(5,Empty,Empty),Node(9,Empty,Empty)))
 
 
さて、まずはこの二分木の各ノードの値の和を求める関数を定義したいと思います。
継続を使わない例では
let rec dispNode btree = 
    match btree with 
    |Empty 
        -> 0 
    |Node(v,leftBT,rightBT) 
        -> v + dispNode leftBT + dispNode rightBT 
とすればよいのでした。
次に継続で行うことにします。
 
let rec sumNodeCPS btree cont = 
    match btree with 
    |Empty 
        -> 0 |> cont  
    |Node(v,rightBT,leftBT) 
        ->sumNodeCPS leftBT (fun lx ->sumNodeCPS rightBT (fun rx -> lx + rx + v |> cont)) 
 
(実行例)
> sumNodeCPS t00 id;;
val it : int = 21
 
では解説を加えていきたいと思います。
(フィボナッチ数列の時と同じなので、分かる人はスキップしてください。)
 
もっと単純な木への適用を考えてみます。
  9
 / \  
E   E 
     
 
let t1 = Node (9,Empty,Empty);;
 
これでsumNodeCPS t1 idを調べると
sumNodeCPS t1 id 
= sumNodeCPS Empty (fun lx -> sumNodeCPS  Empty (fun rx -> lx + rx + 9 |>id)) 
= 0 |> (fun lx -> sumNodeCPS  Empty (fun rx -> lx + rx + 9 |>id))
= sumNodeCPS  Empty (fun rx -> 0 + rx + 9 |>id) 
= 0 |> (fun rx -> 0 + rx + 9 |>id)
= ( 0 + 0 + 9) |> id 
= 9となります。
 
     4
    / \
   E   9
      /  \  
     E     E 
 
let t2 = Node(4,Empty,t1)
 
これでsumNodeCPS t2 idを調べると
sumNodeCPS t2 id 
= sumNodeCPS Empty (fun lx2 -> sumNodeCPS  t1 (fun rx2 -> lx2 + rx2 + 4 |>id))
= 0 |> (fun lx2 -> sumNodeCPS  t1 (fun rx2 -> lx2 + rx2 + 4 |>id))) //lx2にはt2の左部分木の計算結果が代入される
= sumNodeCPS t1 (fun rx2 -> 0 + rx2 + 4 |> id)
= sumNodeCPS Empty (fun lx1 -> sumNodeCPS Empty (fun rx1 -> lx1 +rx1 + 9 |> (fun rx2 -> 0 + rx2 + 4 |> id))
= 0 |> (fun lx1 -> sumNodeCPS Empty (fun rx1 -> lx1 +rx1 + 9 |> (fun rx2 -> 0 + rx2 + 4 |> id))
 //lx1にはt1の左部分木の計算結果が代入される
=sumNodeCPS Empty (fun rx1 -> 0 +rx1 + 9 |> (fun rx2 -> 0 + rx2 + 4 |> id))
= 0 |>  (fun rx1 -> 0 +rx1 + 9 |> (fun rx2 -> 0 + rx2 + 4 |> id)
//rx1にはt1の右部分木の計算結果が代入される
= (0 + 0 + 9) |> (fun rx2 -> 0 + rx2 + 4 |> id)
//rx2にはt2の右部分木の計算結果である9が代入される
= (0 + 9 + 4) |> id
 
というように、実際に値に累積した関数を適用するときにはrxにノードに対して「右側の子供の木に対する関数の適用結果の値」、lxに「左側の子供の木に対する関数の適用結果の値」が代入されていきます。
(フィボナッチ数列と同様の考え方です。)
 
(練習)
ノードの保持する値全ての積をもとめる関数mulNodeCPSを上のスタイルで書いてください。
 
> let rec mulNodeCPS btree cont = 
    match btree with 
    |Empty 
        -> 1 |> cont  
    |Node(v,rightBT,leftBT) 
        ->mulNodeCPS leftBT (fun lx ->mulNodeCPS rightBT (fun rx -> lx * rx * v |> cont)) ;;
 
val mulNodeCPS : BTree<int> -> (int -> 'a) -> 'a
 
> mulNodeCPS t2 id;;
val it : int = 36
 
(練習)ノードの保持する値をリスト化する関数myTreeToListを定義してみてください。順番は任意です。
 
(解答例)
let rec myTreeToList btree cont = 
    match btree with 
    |Empty 
        -> [] |> cont  
    |Node(v,rightBT,leftBT) 
        ->myTreeToList leftBT (fun lx ->myTreeToList rightBT (fun rx -> lx @ [v] @ rx |> cont)) 
       3
      / \
     7   4
    /|  / \
   2   E   5   9
  /|   /|   / \  
 E E E    E    E   E 

 
(実行例)
> myTreeToList t id;;
val it : int list = [2; 7; 3; 5; 4; 9]
 
(fun rx -> lx @ [v] @ rx |> cont))を(fun rx -> v :: lx @ rx |> cont)とすると
 
> myTreeToList t id;;
val it : int list = [3; 7; 2; 4; 5; 9]
となり
 
(fun rx -> lx @ [v] @ rx |> cont))を(fun rx -> lx @ rx @ [v] |> cont)とすると
> myTreeToList t id;;
val it : int list = [2; 7; 5; 9; 4; 3]
となります。
 
さて次は、@はとても効率が悪いのでこれを使わずに済ませる方法を紹介します。
 
もう一度定義を再掲します。
let rec myTreeToList btree cont = 
    match btree with 
    |Empty 
        -> [] |> cont  
    |Node(v,leftBT,rightBT) 
        ->myTreeToList leftBT (fun lx ->myTreeToList rightBT (fun rx -> lx @ [v] @ rx |> cont))
 
という定義では実際に適用するときにはlxにはノードの左側をリスト化したもの、rxには右側をリスト化したものが代入されるのでしたが、これのかわりにlxの部分を「リストを引数として、ノードの左側をリスト化して付け加える関数」、rxをノードの右側に対して同様の作用をする関数にします。
lxをlML(left Make Listの略),rxをrMLという名前で書き直すと、次のようになります。
 
let rec myTreeToList2 btree cont = 
    match btree with 
    |Empty 
        -> id |> cont  //[]はidに変わってます、ここのidはlistを受け取ってlistを返します。
    |Node(v,leftBT,rightBT) 
        ->myTreeToList2 leftBT (fun lML ->myTreeToList2 rightBT (fun rML -> (fun acc -> lML ( v :: ( rML acc))) |> cont)) 
 
最後の (fun acc -> lML ( v :: ( rML acc)))|> cont の部分はこのような関数を累積していきなさいよという意味になってます。さて使ってみます。(accはlist<'a>型です)
 
> let toList = myTreeToList2 t id;;//ここのidはlist->listを受け取ってlist->listを返します
val toList : (int list -> int list)
 
もちろん返ってくるのは関数です。
種の[]を与えます。
 
> toList [];;
val it : int list = [2; 7; 5; 9; 4; 3]
 
なお(fun acc -> lML ( v :: ( rML acc))の部分を
(fun acc -> v :: lML ( rML acc))に変えると
 [3; 7; 2; 4; 5; 9]となり
 (fun acc ->lML ( rML (v ::acc)))に変えると
[2; 7; 5; 9; 4; 3]となります。

スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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