CODEWITHSUNDEEP
functional-programmingsml
anon_swe
anon_swe

Reputation: 9335

Standard ML: Backtracking Confusion

I'm confused by an example Harper gives in his Intro to SML on p. 110. He's writing a function to make a certain amount of change from a list of coin values, backtracking when needed.

e.g. If I run change [5, 2] 16, I get [5, 5, 2, 2, 2] (algorithm should be greedy when possible).

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

A few questions:

1) I'm a bit confused about how this algorithm implements backtracking. It looks like when change is called with an empty list of coin values as its first argument, it raises the Change exception.

But the Change exception handler calls change coins amt. How is this "undoing the most recent greedy decision?

2) Why is the handler placed within the else clause? I would have thought it'd be totally separate...

Thanks for the help, bclayman

Upvotes: 2

Views: 245

Answers (1)

Ionuț G. Stan
Ionuț G. Stan

Reputation: 179119

Here's a execution trace for the call change [5,2] 16. The parts to the left of handle represent what the function has computed thus far, while the part on the right is the state to continue with when backtracking is requested via a Change signal.

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

As you can see, when the Change exception is caught, the algorithm goes back two stack frames, drops the third 5 coin from the result list and recurses only with a 2 coin in the list of coins. The amount is also reset to 6.

The first line, the part before handle tries to use another 5 as a possible decomposition, while the exception handler represents the backtracking option, i.e., remove the 5 we've just tried and adjust the coin list and the remaining amount.

The final line signals the last installed exception handler to backtrack.

> 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

In other words, the algorithm backtracks when it reaches a state where no more coin types are available to choose, but the amount is still positive. It's greedy because the algorithm will use the same coin until it catches an exception.

The exception handler is attached to the else expression because it's where the greedy choice is made.

Hopefully I've been intelligible with my explanation.

Upvotes: 3

Related Questions