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

---

但是之后:

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

正如您所看到的,该函数在该Node情况下不是尾递归的,因为我们调用loop,然后loop再次调用然后最终调用f.

延续的想法是添加一个参数,表示"当前操作完成后要做什么".这被捕获了cont.在这种情况下Leaf,我们只leaf用leaf作为参数的调用continuation 替换返回.的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以正确的方式替换!