標準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表達式，因爲它是 作出的貪婪選擇。

希望我能理解我的解釋。