F＃延續傳遞折返

我正在努力理解與CPS的折返。這一次我能理解：F＃延續傳遞折返

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::[]))

但後來：

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.

爲什麼這項工作？如何理解這一點？

來源

2017-04-11 RobF

我認爲理解延續傳遞風格的最好方法是比較函數的普通非延續版本和基於延續的函數。使用樹折的你「更糟糕」的例子，讓我們先使用普通的遞歸編寫函數：

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

正如你所看到的，功能是不是尾遞歸的Node情況下，因爲我們所說的loop，然後再次致電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，並將它傳遞一個功能獲得結果並完成其餘的工作。

這看起來有點令人困惑，直到你習慣了它 - 但關鍵是這實際上是一個相當機械的翻譯 - 你只需用fun以正確的方式取代let！

來源

2017-04-11 16:36:33

F＃延續傳遞折返

回答

相關問題