回溯到标准ML

我在我的SML手册中看到了以下函数，该函数计算特定更改需要特定类型的硬币数量。例如change [5,2] 16 =[5,5,2,2,2]因为2 5硬币和3-2金币一个得到16回溯到标准ML

下面的代码是一个回溯的方法：

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

handle Change=> change coins amt;

它的工作原理，但我不明白究竟怎么了。我知道回溯是什么，我只是不明白这个特定的功能。

到目前为止我的理解是：如果amt为0，这意味着我们的变化是计算出来的，没有什么可以列入最终列表。

如果我们的'硬币列表'中没有更多的硬币，我们需要返回一步。 这就是我迷失的地方：举一个异常如何帮助我们回去？ 当我看到它，处理程序试图调用更改函数，但不应该“硬币”参数为零？因此进入无限循环？为什么它会“返回”;

最后一个条款对我来说很明显：如果硬币价值大于剩余金额要更改的余额，我们使用剩余的硬币来构建更改。如果它小于剩余的数量，我们将它放在结果列表中。

来源

2013-07-27 Radu

您可以改用这种使用例外情况来改为使用'a option类型。原有的功能：

exception Change; 
fun change _ 0 = [] 
    | change [] _ = 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;

在下面的修饰的功能，而不是例外冒泡，就变成了NONE。变得稍微更加明显这里的一件事是coin仅发生在这两种情况一个（其中，在上面的代码中它总是发生但在回溯的情况下被还原）。

fun change' _ 0 = SOME [] 
    | change' [] _ = NONE 
    | change' (coin::coins) amt = 
    if coin > amt 
    then change' coins amt 
    else case change' (coin::coins) (amt-coin) of 
      SOME result => SOME (coin :: result) 
      | NONE  => change' coins amt

另一种方式来证明什么情况是通过绘制调用树。这不收集结果作为安德烈亚斯Rossberg的评价用手工，但它确实表明，只有时间change正在采取的else分枝有没有走回头路的可能性，并且如果发生一个回溯（即NONE返回或抛出一个异常），结果中不包括coin。

(original call ->) change [2,5] 7 
         \ (else) 
         `-change [2,5] 5 
        /\ (else) 
    ___________________/ `-change [2,5] 3 
/     /\ (else) 
/     / `-change [2,5] 1 
`-change [5] 5  /  \ (then) 
    \ (else)   /  `-change [5] 1 
    `-change [] 0 /   \ (then) 
    \   /   `-change [] 1 
     `-SOME []  `-change [5] 3 \ (base) 
        \ (then)   `-NONE 
         `-change [] 3 
         \ 
         `-NONE

来源

2013-08-03 23:26:17

通过写出评估如何进行的一个简单示例，可以很好地看出这一点。在每一步中，我只需更换由各自的右手边change打电话（我加了额外的清晰度额外的括号）：

change [3, 2] 4 
= if 3 > 4 then ... else ((3 :: change [3, 2] (4 - 3)) handle Change => change [2] 4) 
= (3 :: change [3, 2] 1) handle Change => change [2] 4 
= (3 :: (if 3 > 1 then change [2] 1 else ...)) handle Change => change [2] 4 
= (3 :: change [2] 1) handle Change => change [2] 4 
= (3 :: (if 2 > 1 then change [] 1 else ...)) handle Change => change [2] 4 
= (3 :: (raise Change)) handle Change => change [2] 4

此时异常被引发。它的气泡上升到目前的处理程序，以便评估过程如下：

= change [2] 4 
= if 2 > 4 then ... else ((2 :: change [2] (4 - 2)) handle Change => change [2] 4) 
= (2 :: change [2] 2) handle Change => change [2] 4 
= (2 :: (if 2 > 2 then ... else ((2 :: change [2] (2 - 2)) handle Change => change [2] 2)) handle Change => change [2] 4 
= (2 :: ((2 :: change [2] 0) handle Change => change [2] 2)) handle Change => change [2] 4 
= (2 :: ((2 :: []) handle Change => change [2] 2)) handle Change => change [2] 4 
= (2 :: (2 :: [])) handle Change => change [2] 4 
= 2 :: 2 :: []

没有更多的失败了这里，所以我们成功地终止。

总之，每个处理程序都是一个回溯点。在每次失败（即提高）时，您都会在最后一个回溯点处进行处理。每个处理程序本身都设置为包含相应的调用来尝试。

来源

2013-07-27 20:40:25

回答

相关问题