回溯到標準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

回答

相關問題