Backtracking in Standard ML

Question

I have seen in my SML manual the following function, which computes how many coins of a particular kind are needed for a particular change. For example change [5,2] 16 =[5,5,2,2,2] because with two 5-coins and three 2-coins one gets 16.

the following code is a backtracking approach:

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;

It works, but I don't understand how exactly. I know what backtracking is, I just don't understand this particular function.

What I understood so far: If amt is 0, it means our change is computed, and there is nothing to be cons'd onto the final list.

If there are no more coins in our 'coin-list', we need to go back one step.

This is where I get lost: how exactly does raising an exception helps us go back?

as I see it, the handler tries to make a call to the change function, but shouldn't the "coins" parameter be nil? therefore entering an infinite loop? why does it "go back"?

The last clause is pretty obvious to me: if the coin-value is greater than the amount left to change, we use the remaining coins to build the change. If it is smaller than the amount left, we cons it onto the result list.

Answer 1

You can rewrite this use of exceptions into using the 'a option type instead. The original function:

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;

In the modified function below, instead of the exception bubbling up, it becomes a NONE. One thing that becomes slightly more apparent here is that coin only occurs in one of the two cases (where in the code above it always occurs but is reverted in case of backtracking).

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

Another way to demonstrate what happens is by drawing a call tree. This does not gather the result as Andreas Rossberg's evaluation by hand, but it does show that only the times change is taking an else-branch is there a possibility to backtrack, and if a backtrack occurs (i.e. NONE is returned or an exception is thrown), don't include coin in the result.

  (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