I don't think that solution is so elegant. It seems to me that the use of exceptions is gratuitous. Here's how I would have written something like this in ML:

fun intf base next 0 = base
  | intf base next n = next (n, (intf base next (n-1)));
val iota = intf [0] (op ::);

local
      val append = foldl (op @) []
      fun repeat x = intf [] (fn (_,ls) => x::ls)
      fun rep2each x n ls = map (fn e => (repeat x n) @ e) ls
in
  fun change nil 0 = [[]]
    | change nil _ = []
    | change (c::cs) x =
         append (map (fn n => rep2each c n (change cs (x - n*c)))
                     (iota (x div c)))
end;
[download]

Unlike the code in the original post, this one generates all the solutions instead of only the first one. One interesting approach if you only need one solution is to define a datatype that represents a possibly-absent solution:

  datatype 'a option = Solution of 'a | Nothing;
[download]

Then you need a couple of utility functions for dealing with it:

  fun sflat ls = foldr (fn (Solution x, _) => Solution x
                         | (Nothing,v) => v) 
                       Nothing ls;
  fun smap _ Nothing = Nothing | smap f (Solution x) = Solution (f x)
[download]

sflat takes a list of possibly-missing values and returns the first one that isn't missing. smap takes a function and applies it to a (possibly missing) value. Then you can implement change like this:

local
  fun repeat x = intf [] (fn (_,ls) => x::ls)
in
  fun change1 nil 0 = Solution []
    | change1 nil _ = Nothing
    | change1 (c::cs) x =
         sflat (map (fn n => smap (fn x => (repeat c n) @ x) (change1 
+cs (x - n*c)))
                     (iota (x div c)))
end;
[download]

Now change1 [5,1] 12 returns Solution [5,5,1,1] and change1 [3,8] 10 returns Nothing. Haskell has this Solution / Nothing type built in. Also, in Haskell, whenver you think of this "option" type, you immediately start thinking about monads. I think use of monads would probably simplify this version of the function considerably---at the expense of introducing monads---but that's a post for another day. (Short summary: monads abstract out the similarities between all three of these solutions, replacing the exceptions, the list values, and the option type values with a single abstraction.)

If all you want is to count the solutions, it's simpler, because you can get rid of all of ML's clumsy value construction syntax:

local val addup = foldr (fn (a,b) => a+b) 0
in
  fun countchange nil 0 = 1
    | countchange nil _ = 0
    | countchange (c::cs) x =
         addup (map (fn n => countchange cs (x - n*c))
                    (iota (x div c)))
end;
[download]

ML has a TCL look to it...

I don't think anyone has ever said that ML's syntax was one of its better points.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.