标准ML：回溯混乱

Question

我很困惑哈珀在他的介绍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 coins 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] 

正如你所看到的，变化异常被捕获时，则算法进行退二 堆栈帧，从结果列表下降到第三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表达式，因为它是 作出的贪婪选择。

希望我能理解我的解释。