F# 扩展欧几里得算法与 Continuations 问题

Question

我是 F# 的新手，自大学以来就没有做过函数式编程，但我一直在尝试自学。我写了一个朴素的递归扩展欧几里德实现，它工作得很好，现在我再次尝试但有延续。

我用一个小例子手写了两次代码并得到了正确答案，但是当我运行它通过解释器时我没有得到相同的结果，所以我显然误解了一些东西我正在努力。

我手动运行 eea 7 3，我计算的（正确）结果是 (1, 1, -2)

但是当我在解释器中运行它时，我得到

eea 7 3;;
val it : int * int * int = (1, 0, 1)

这是我的实现：

let eea a b = 
    let rec contEEA a b f = 
        match b with
        | 0 -> f () (a,1,0)
        | _ -> 
            contEEA b (a%b) (fun () t ->
                let (d,x',y') = t
                (d, y', x'-(y'*(a/b)))
            )
    contEEA a b (fun () t -> t)

作为参考，直接来自教科书的天真方法是

let rec eea_gcd a b =
    match b with
    | 0 -> (a, 1, 0)
    | _ -> 
        let d, x', y' = eea_gcd b (a % b)
        (d, y', x'-(y'*(a/b)))

Answer 1

你的基于延续的版本总是只做一次迭代（最后一次）。当你进行递归调用时，你的延续只是直接 returns 结果而不是 "returning" 通过传递给前一个延续来将它传递给前一个调用。

所以调用顺序是这样的：

eea 7 3
contEEA 7 3 (fun () t -> t)
b <> 0 ==> 第二种情况匹配
contEEA 3 1 (fun () t -> ... (d, y', ...))
b <> 0 ==> 第二种情况匹配
contEEA 1 0 (fun () t -> ... (d, y', ...))
b = 0 ==> 第一种情况匹配
继续调用f () (1, 1, 0)
继续计算结果(1, 0, 1 - (0*(3/1)) = (1, 0, 1)并立即returns它

你想要做的是当第一个延续计算 (1, 0, 1) 的结果时，它应该将它传递给 previous continuation，以便它可以从那里进行计算，最终将结果传递给第一个 continuation fun () t -> t，returns 它返回给消费者。

为此，请替换此行：

(d, y', x'-(y'*(a/b)))

有了这个：

f (d, y', x'-(y'*(a/b)))

另外，一些其他方面的注意事项。

continuation 的第一个参数（单位，()）不是必需的，因为它从未实际使用过（怎么可能？）。你可以丢了。
去掉单位参数后，第一个continuation变成fun t -> t，有一个特殊的名字id（又名"the identity function"）
与其使用 let 解构三元组，不如直接在参数声明中进行。参数可以是模式！

应用以上所有内容以及实际问题修复，这是一个更好的版本：

let eea a b = 
    let rec contEEA a b f = 
        match b with
        | 0 -> f (a,1,0)
        | _ -> 
            contEEA b (a%b) (fun (d,x',y') -> 
                f (d, y', x'-(y'*(a/b)))
            )
    contEEA a b id

F# 扩展欧几里得算法与 Continuations 问题

F# extended Euclidian algorithm with Continuations question

continuations

f#

functional-programming