F＃続きFoldBackを渡す

Question

私はCPSでフォールドバックを理解するのに苦労しています。その後、

let listFoldBack combine acc l = 
    let rec Loop l cont = 
    match l with 
    | h :: t -> Loop t (fun racc -> cont (combine h racc)) 
    | [] -> cont acc 
    Loop l id  

listFoldBack (fun x a -> (2*x::a)) [] [1;2;3] 

// call sequence 
[1;2;3] id 
Loop [2;3] (fun a -> (combine 1 a)) 
Loop [3] (fun a -> (combine 1 (combine 2 a))) 
Loop [] (fun a -> (combine 1 (combine 2 (combine 3 a)))) 
      (fun a -> (combine 1 (combine 2 (combine 3 a)))) [] 
      2::(4::(6::[])) 

---

：しかし 私は理解することができます。この1

let fib n = 
    let rec fibc a cont = 
    if a <= 2 then cont 1 
    else  
     fibc (a - 2) (fun x -> fibc (a - 1) (fun y -> cont(x + y)))  
    fibc n id 

// call sequence 
fibc (4) id 
fibc (2) (fun x -> fibc (3) (fun y -> id(x + y))) 
    (fun x -> fibc (3) (fun y -> id(x + y))) (1) 
    fibc (3) (fun y -> id(1 + y)) 
     fibc (1) (fun x -> fibc (2) (fun y -> (fun z -> id(1+z)) (x + y))) 
      fibc (2) (fun y -> (fun z -> id(1+z))(1 + y))) 
      (fun y -> (fun z -> id(1+z))(1 + y))) (1) 
       fun z -> id(1+z)(1+1) 
       id (1+2) 
        3 

従うことは非常に難しいです。

---

さらに悪い：

type Tree<'a> = 
    | Leaf 
    | Node of 'a * Tree<'a> * Tree<'a> 

let node x l r = Node(x,l,r) 

let treeFoldBack f leaf tree = 
    let rec loop t cont = 
     match t with 
     | Leaf -> cont leaf 
     | Node(x,l,r) -> loop l (fun lacc -> 
      loop r (fun racc -> cont(f x lacc racc))) 
    loop tree id 

let tree1 = 
    (node 4 
     (node 2 
      (node 1 Leaf Leaf) 
      (node 3 Leaf Leaf)) 
     (node 6 
      (node 5 Leaf Leaf) 
      (node 7 Leaf Leaf))) 

    // call sequence by means of text replacing 
     ... a lot of steps, lines too long to fit 
     cont(f 4 (f 2 (f 1 Leaf Leaf) (f 3 Leaf Leaf)) 
     (f 6 (f 5 Leaf Leaf) (f 7 Leaf Leaf)))) 

結果が正しいが、従うことが非常に困難です。

loop l (fun lacc -> loop r (fun racc -> cont(f x lacc racc))) 
calculate loop l, result goes in lacc. 
calculate loop r, result goes in racc. 
calculate f x lacc racc and result is argument for cont. 

なぜこの作業を行います。 は、すべてのケースではパターンが似ているのですか？これを理解する方法？

Answer 1

継続継承スタイルを理解する最善の方法は、通常の非継続バージョンの関数を継承ベース関数と比較することです。木の折り目のあなたの「さらに悪化」の例を使用して、まずは普通の再帰を使用して関数を書いてみましょう：

let treeFoldBack f leaf tree = 
    let rec loop t = 
     match t with 
     | Leaf -> leaf 
     | Node(x,l,r) -> 
      let lacc = loop l // Process left and return result 
      let racc = loop r // Process right and return result 
      f x lacc racc  // Aggregate current, left and right 
    loop tree 

あなたが見ることができるように私たちは、その後、loopを呼び出すので、この関数は、末尾再帰Node場合ではありませんloopに再度電話し、最後にfを呼び出してください。

継続の考え方は、「現在の操作が完了した後に何をするか」を表すパラメータを追加することです。これはcontによってキャプチャされます。 Leafの場合は、leafの返品をleafという引き続きで置き換えます。 Node場合は、より精巧である：

let treeFoldBack f leaf tree = 
    let rec loop t cont = 
     match t with 
     | Leaf -> cont leaf 
     | Node(x,l,r) -> 
      loop l (fun lacc -> // Process left and continue with result 
       loop r (fun racc -> // Process right and continue with result 
       cont(f x lacc racc))) // Aggregate and invoke final continuation 
    loop tree id 

あなたが見ることができるように、構造は以前と同じである - しかしむしろloopを呼び出し、letを使用して結果を保存するよりも、私たちは今loopを呼び出し、それを関数を渡す結果を得て残りの作業を行います。

これは慣れるまで少し混乱していますが、実際にはかなり機械的な翻訳であることが重要です。ちょうどletをfunに置き換えてください。