スポンサーサイト

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

F#入門初級編第11回 CPS (Continuation Passing Style)(4) Catamorphisms(1)

今回はList.foldBackをCPSで考えてみたいと思います。
 
以前リスト内のすべての要素を加えた和を返す関数myListSumをCPSスタイルで
 
let rec myListSum lst cont =
    match lst with
    | [] ->
       0 |>  cont //もしくはcont 0
    | hd :: tl ->
        myListSum tl (((+) hd) >> cont) 
        //myListSum tl (fun x -> cont(hd + x))
        //myListSum tl (fun x -> x + hd |> cont)
        
のように書いたのですが、これを少し書き直してみます。
 
let rec myListSum2 cont lst =
    match lst with 
    |hd :: t -> myListSum2 (fun acc -> ( hd + acc) |> cont ) t 
    | [] -> 0 |> cont
 
これは変数の並びを変えて、fun x のxをaccで置き換えたにすぎません。
これは最終的に種の0に、関数の蓄積(合成)を施こして値を求めているということは、以前説明しました。
myListSum2では各要素を加えていっているのですが、この作用も引数にして与えたいと思います。
この関数(作用)の名前は通例combineという名前で定義するようなので、それを使用します。
myListSum2もmyFoldBackSubと改名します。contの初期値としては、idを渡します。すると次のようになります。
 
let myFoldBack combine lst =
    let rec myFoldBackSub cont lst =
        match lst with
        |hd :: t -> myFoldBackSub (fun acc -> (combine acc hd) |> cont ) t     
        | [] -> 0 |> cont
    myFoldBackSub id lst  // idは(fun x -> x)
    
(実行例)
> myFoldBack (fun acc e -> acc + e) [1;2;3] ;;
val it : int = 6
 
仕上げに種も0に固定ではなく指定できるようにします。
 
> let myFoldBack combine lst seed =
    let rec myFoldBackSub cont lst =
        match lst with
        |hd :: t -> myFoldBackSub (fun acc -> (combine acc hd) |> cont ) t     
        | [] -> seed |> cont
    myFoldBackSub id lst ;;
 
val myFoldBack : ('a -> 'b -> 'a) -> 'b list -> 'a -> 'a
 
では使ってみます。
 
> myFoldBack (fun acc e -> acc + e) [1;2;3] 0 ;;
val it : int = 6
 
> myFoldBack (fun acc e -> acc * e) [1;2;3;4] 1 ;;
val it : int = 24
 
> myFoldBack (fun acc e -> e :: acc) [1;2;3;4] [] ;;
val it : int list = [1; 2; 3; 4]
 
> myFoldBack (fun _ e -> printfn "%d " e) [1;2;3;4] () ;;




val it : unit = ()
 
myFoldBackは再帰をパターン化した高階関数であることに留意してください。
 
一般にリストや二分木などの、構造物から値を作り上げることをCatamorphismsといいます。(一般化されたfoldです。)
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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