2

私の SML マニュアルで、特定の変更に必要な特定の種類のコインの数を計算する次の関数を見たことがあります。たとえばchange [5,2] 16 =[5,5,2,2,2]、2 枚の 5 コインと 3 枚の 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 の場合、変更が計算され、最終的なリストにコンスされるものがないことを意味します。

「-list」にコインがもうない場合は、coin1 ステップ戻る必要があります。

これは私が迷っているところです: 例外を発生させることは、私たちが戻るのにどのように役立ちますか?

change私が見たように、ハンドラーは関数を呼び出そうとしますが、 " coins" パラメーターはnil? したがって、無限ループに入りますか？なぜ「戻る」のですか？

最後の節は私には明らかです。coin-value が釣り銭の残りの金額よりも大きい場合、残りのコインを使用して釣り銭を構築します。残りの量よりも小さい場合は、結果リストにコンスします。

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 :: []

ここまで失敗は無かったので、無事終了。

つまり、すべてのハンドラーはバックトラッキング ポイントです。それぞれの失敗 (つまり、レイズ) で、最後のバックトラッキング ポイントである最も内側のハンドラーに進みます。各ハンドラー自体は、代わりに試行するそれぞれの呼び出しが含まれるように設定されています。

于 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の 1 つは、2 つのケースのいずれかでのみ発生することです (上記のコードでは常に発生しますが、バックトラッキングの場合は元に戻されます)。

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

何が起こるかを示すもう 1 つの方法は、コール ツリーを描画することです。changeこれは Andreas Rossberg の手による評価として結果を収集するものではありませんが、elseバックトラックの可能性があるかどうか、およびバックトラックが発生した場合 (つまりNONE、返されるか、例外がスローされた場合)、don結果に含め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 に答える