スポンサーサイト

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

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

今回は二分木対象のfoldを取り上げます。
以前やったように、二分木に対し各ノードの和を求める関数は
 
let rec sumNodeCPS btree cont = 
    match btree with 
    |Empty 
        -> 0 |> cont  
    |Node(v,leftBT,rightBT) 
        ->sumNodeCPS leftBT (fun lx ->sumNodeCPS rightBT (fun rx -> lx + rx + v |> cont)) 
 
となるのでした。
これを一般化して(fun rx -> lx + rx + v |> cont)の lx + rx + vの部分と 0 |> cont の部分の0を引数として与えられるようにします。
関数部分をcombine、Empty部分で与える値をempValueとして定義し、rxの代わりにracc,lxの代わりにlaccを使うと
 
let myFold combine empValue tree =
    let rec myFoldSub t cont =
        match t with
        | Empty
            -> empValue |> cont
        | Node(v,leftBT,rightBT)
            -> myFoldSub leftBT ( fun lacc -> myFoldSub rightBT (fun racc -> ((combine v lacc racc) |> cont)))
    myFoldSub tree id
 
となります。
次のような二分木で試してみます。
 
       3 
      / \ 
     7   4 
    /|  / \ 
   2   E   5   9 
  /|   /|   / \   
 E E E    E    E   E  
 
let t =
    Node(3,Node(7,Node(2,Empty,Empty),Empty),Node(4,Node(5,Empty,Empty),Node(9,Empty,Empty)))
 
まずは和を求めてみます。
 
> myFoldTree (fun v lacc racc -> v + lacc + racc) 0 t;;
val it : int = 30
 
積を求めてみます。
> myFoldTree (fun v lacc racc -> v * lacc * racc) 1 t;;
val it : int = 7560
 
(練習)最大値を求めてください。(leafValueとしてはSystem.Int32.MinValueを渡します)
(解答例)
> myFoldTree (fun v lacc racc -> max v (max lacc racc)) System.Int32.MinValue t;;
val it : int = 9
 
なお二分木の高さを計るには次のようにします。
> myFoldTree (fun _ lacc racc -> 1 + max lacc racc) 0 t;;
val it : int = 3
 
さてリスト化に移ります。
以前やった効率の悪い方の方法では次のようになります。
 
> myFoldTree (fun v lacc racc ->lacc @ [v] @ racc) [] t;;
val it : int list = [2; 7; 3; 5; 4; 9]
 
効率のいい方のやり方では、コードは次のようになるのでした。
let rec myTreeToList2 btree cont = 
    match btree with 
    |Empty 
        -> id |> cont  
    |Node(v,leftBT,rightBT) 
        ->myTreeToList2 leftBT (fun lML ->myTreeToList2 rightBT (fun rML -> (fun acc -> lML ( v :: ( rML acc))) |> cont)) 
 
myFoldTreeをつかってこの形を表現できないでしょうか。
実はこれは
myFoldTree (fun v lacc racc acc -> lacc (v :: (racc acc))) id tとすることで表現できます。
関数が4変数になっていることに留意ください。
実際に実行する際にはv,lacc,raccが部分適用されて(fun acc -> accの式)という引数が一つの関数が残るという仕組みになっています。
 
> let makeInOrder = myFoldTree (fun v lacc racc acc -> lacc (v :: (racc acc))) id t;;
val makeInOrder : (int list -> int list)
 
> makeInOrder [];;
val it : int list = [2; 7; 3; 5; 4; 9]
 
追加順位をかえてみます。
 
> let makePreOrder = myFoldTree (fun v lacc racc acc -> v :: lacc (racc acc)) id t;;
val makePreOrder : (int list -> int list)
 
> makePreOrder [];;
val it : int list =[3; 7; 2; 4; 5; 9]
 
> let makePostOrder = myFoldTree (fun v lacc racc acc -> lacc (racc (v ::acc))) id t;;
val makePostOrder : (int list -> int list)
 
> makePostOrder [];;
val it : int list = [2; 7; 5; 9; 4; 3]
 
        3 
      / \ 
     7   4 
    /|  / \ 
   2   E   5   9 
  /|   /|   / \   
 E E E    E    E   E  
 
それぞれの訪問順には名前が付いていて
InOder[2; 7; 3; 5; 4; 9]は「通りがけ順」で、まず左の部分木から始めて、右の木に行く前に、その親ノードを取り上げます。
PreOrder[3; 7; 2; 4; 5; 9]は「行きがけ順」で、訪れたノードをまず取り上げてから、左の部分木、右の部分木の順で列挙します。
PostOrder[2; 7; 5; 9; 4; 3]は「帰りがけ順」で、部分木の要素を列挙してから、最後に親ノードを取り上げます。
 
仕上げにmyFoldTreeの変数名を変えておきます。
combineはノードでの作用を表すのでnodeF,leafValueはEmptyの作用を表すのでempFとします。
完成したmyFoldTreeは
 
let myFoldTree nodeF empF tree =
    let rec myFoldSub t cont =
        match t with
        | Empty
            -> empF |> cont
        | Node(v,leftBT,rightBT)
            -> myFoldSub leftBT ( fun lx -> myFoldSub rightBT (fun rx -> ((nodeF  v lx rx) |> cont)))
    myFoldSub tree id
    
となりnodeFとempFを切り替えることで、さまざまなfoldが実行できます。
 
参考リンク(特に3番目は発展的内容になっているので、お勧めです。)
http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!170.entry
http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!171.entry
http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!174.entry
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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