2

我在我的 SML 手册中看到了以下函数，该函数计算特定更改需要多少特定种类的硬币。例如change [5,2] 16 =[5,5,2,2,2]，因为有两个 5 硬币和三个 2 硬币，一个得到 16。

以下代码是一种回溯方法：

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，这意味着我们的变化是计算出来的，在最终列表中没有什么可以被 cons'd 的。

如果我们的“-list”中没有更多的硬币coin，我们需要后退一步。

这就是我迷失的地方：引发异常究竟如何帮助我们返回？

如我所见，处理程序尝试调用该change函数，但“ coins”参数不应该是nil吗？因此进入无限循环？为什么会“回去”？

最后一个条款对我来说非常明显：如果硬币价值大于剩余的找零数量，我们使用剩余的硬币来构建找零。如果它小于剩余的数量，我们将其添加到结果列表中。

4

3 回答 3

4

通过写出一个简单示例的评估如何进行，可以最好地看到这一点。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 [] 4)
= (2 :: change [2] 2) handle Change => change [] 4
= (2 :: (if 2 > 2 then ... else ((2 :: change [2] (2 - 2)) handle Change => change [] 2)) handle Change => change [] 4
= (2 :: ((2 :: change [2] 0) handle Change => change [] 2)) handle Change => change [] 4
= (2 :: ((2 :: []) handle Change => change [] 2)) handle Change => change [] 4
= (2 :: (2 :: [])) handle Change => change [] 4
= 2 :: 2 :: []

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

简而言之，每个处理程序都是一个回溯点。在每次失败（即引发）时，您都会在最里面的处理程序处继续，这是最后一个回溯点。每个处理程序本身都设置为包含相应的 try 调用。

于 2013-07-27T20:40:25.737 回答
3

您可以将这种对异常的使用重写为使用该'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

演示发生了什么的另一种方法是绘制调用树。这并没有像 Andreas Rossberg 的手工评估那样收集结果，但它确实表明只有时间change采取else-branch 才有可能回溯，如果发生回溯（即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-03T23:26:17.730 回答
0

来源：https ://www.cs.cmu.edu/~rwh/introsml/core/exceptions.htm

表达式exp handle match是一个异常处理程序。通过尝试评估exp来评估它。如果它返回一个值，那么这就是整个表达式的值；在这种情况下，处理程序不起作用。但是，如果exp引发异常exn，则将异常值与匹配的子句进行匹配（就像将子句函数应用于参数一样）以确定如何继续。如果子句的模式与异常exn匹配，则使用该子句的表达式部分继续计算。如果没有模式匹配，则重新引发异常exn以便外部异常处理程序可以对其进行调度。如果没有处理程序处理异常，则将未捕获的异常作为评估的最终结果发出信号。也就是说，计算因未捕获的异常exn而中止。

在更操作方面，exp handle match的评估通过安装由match确定的异常处理程序进行，然后评估 exp。异常处理程序的先前绑定被保留，以便在不再需要给定处理程序时可以恢复它。引发异常包括将exn类型的值传递给当前异常处理程序。将异常传递给处理程序会卸载该处理程序，并重新安装以前活动的处理程序。这确保如果处理程序本身引发异常，或未能处理给定的异常，则异常会在评估之前传播到活动的处理程序handle 表达。如果表达式未引发异常，则在完成handle表达式评估的过程中恢复先前的处理程序。

于 2021-05-21T09:29:52.557 回答