functional-programming - F# 扩展欧几里得算法与延续问题

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

基于延续的版本始终只执行一次迭代(最后一次)。当您进行递归调用时，您的延续直接返回结果，而不是通过传递到前一个延续来将其“返回”到前一个调用。

所以调用顺序是这样的:

1. eea 7 3
2. contEEA 7 3 (fun () t -> t)
3. b <> 0 ==> 第二种情况匹配
4. contEEA 3 1 (fun () t -> ... (d, y', ...))
5. b <> 0 ==> 第二种情况匹配
6. contEEA 1 0 (fun () t -> ... (d, y', ...))
7. b = 0 ==> 第一个案例匹配
8. 延续称为 f () (1, 1, 0)
9. 继续计算结果(1, 0, 1 - (0*(3/1)) = (1, 0, 1)并立即返回

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

为此，请替换此行:

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

这样:

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

---

此外，还有一些其他方面的注释。

1. 延续的第一个参数(单位 () )不是必需的，因为它从未实际使用过(怎么可能？)。你可能会失去它。

2. 删除单位参数后，第一个延续变为 fun t -> t ，它有一个特殊的名称 id (又名“恒等函数”)

3. 而不是用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