functional-programming - 标准ML : Backtracking Confusion

Question

我对 Harper 在他的 SML 介绍中给出的一个例子感到困惑。 110. 他正在编写一个函数，用于从硬币值列表中进行一定数量的更改，并在需要时回溯。

例如如果我运行change [5, 2] 16，我会得到[5, 5, 2, 2, 2](算法应该尽可能贪婪)。

exception Change
fun change _ 0 = nil
    | change nil _ = raise Change
    | change (coin::coins) amt = 
        if coin > amt then
            change coins amt
        else
            (coin :: change (coin::coins) (amt - coin))
            handle Change => change coins amt

几个问题:

1)我对这个算法如何实现回溯有点困惑。看起来，当使用空的硬币值列表作为第一个参数调用 Change 时，它​​会引发 Change 异常。

但是Change异常处理程序调用change coin amt。这是如何“撤销最近的贪婪决定？

2) 为什么处理程序放置在 else 子句中？我本以为它会完全分开......

感谢您的帮助， BClayman

Answer 1

这是调用 change [5,2] 16 的执行跟踪。左边的零件 handle 的部分代表函数迄今为止计算的内容，而部分 右侧是通过 Change 信号请求回溯时继续的状态。

> change [5, 2] 16
> 5 :: change [5, 2] (16 - 5)                 handle Change: change [2] 16
> 5 :: change [5, 2] 11                       handle Change: change [2] 16
> 5 :: 5 :: change [5, 2] (11 - 5)            handle Change: 5 :: change [2] 11
> 5 :: 5 :: change [5, 2] 6                   handle Change: 5 :: change [2] 11
> 5 :: 5 :: 5 :: change [5, 2] (6 - 5)        handle Change: 5 :: 5 :: change [2] 6
> 5 :: 5 :: 5 :: change [5, 2] 1              handle Change: 5 :: 5 :: change [2] 6
> 5 :: 5 :: 5 :: change [2] 1
> 5 :: 5 :: 5 :: change nil 1
> raise Change => 5 :: 5 :: change [2] 6
> 5 :: 5 :: 2 :: change [2] (6 - 2)           handle Change
> 5 :: 5 :: 2 :: change [2] 4                 handle Change
> 5 :: 5 :: 2 :: 2 :: change [2] (4 - 2)      handle Change
> 5 :: 5 :: 2 :: 2 :: change [2] 2            handle Change
> 5 :: 5 :: 2 :: 2 :: 2 :: change [2] (2 - 2) handle Change
> 5 :: 5 :: 2 :: 2 :: 2 :: change [2] 0       handle Change
> 5 :: 5 :: 2 :: 2 :: 2 :: nil
> [5, 5, 2, 2, 2]

正如你所看到的，当捕获到Change异常时，算法会返回两个 堆栈帧，从结果列表中删除第三个 5 硬币，并仅递归 硬币列表中的 2 枚硬币。金额也重置为 6。

第一行，handle之前的部分尝试使用另一个5作为可能 分解，而异常处理程序代表回溯选项， 即删除我们刚刚尝试过的 5 个并调整硬币列表和剩余的 金额。

最后一行表示最后安装的异常处理程序要回溯。

> 5 :: 5 :: 5 :: change [5, 2] 1              handle Change: 5 :: 5 :: change [2] 6
> 5 :: 5 :: 5 :: change [2] 1
> 5 :: 5 :: 5 :: change nil 1
> raise Change => 5 :: 5 :: change [2] 6

换句话说，当算法达到不再存在的状态时就会回溯。 硬币种类可供选择，但金额仍为正值。真是贪心 因为算法将使用相同的硬币，直到捕获异常。

异常处理程序附加到 else 表达式，因为它位于 做出了贪婪的选择。

希望我的解释能够被理解。