标准 ML：回溯混乱

Question

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

例如如果我运行改变 [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 coins amt。这是如何“撤销最近的贪婪决定？

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

感谢您的帮助，克莱曼

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 表达式，因为它位于做出贪心的选择。

希望我的解释能被理解。

标准 ML：回溯混乱

Standard ML: Backtracking Confusion

functional-programming

sml