Counting Ways to Make Change -- Is this good functional/Lisp style?

Question

I have just started learning some Scheme this weekend. I recently solved a problem that goes something like:

Count the number of ways possible to give out a certain amount of change using
1 5 10 25 and 50 cent pieces.
--SICP 1.16

So my code to this question looks like this:

(define (make-change amount)
  (define coin-total 5)
  ;;#Function that actually does the calculating
  (define (calculate amount coins)

    ;;#Lookup values on the table vector, if none is found find it and add it.
    (define (lookup)

      ;;#Location on the table vector
      (define position (- (+ coins (* coin-total (- amount 1))) 1))

      ;;#Get the value in the table vector
      (define (search-for amount coins)
        (vector-ref table position))

      ;;#Not quite so functional, but we need to add it somehow
      (define (update val)
        (begin (vector-set! table position val)
               val)) 

      (let ((result (search-for amount coins)))
        (if (= result 0)
          (let* ((left-branch (calculate amount (- coins 1)))
                 (right-branch (calculate (- amount (coin-value coins)) coins)))
           (update (+ left-branch right-branch)))
          result)))

    (cond ((= amount 0) 1 )
          ((or (< amount 0) (= coins 0)) 0)
          (else (lookup))))

  ;;#Table stuff
  (define table (make-vector (* amount coin-total) 0))
  (define (init-table position)
    (if (< position 0)
      0
      (begin (vector-set! table position 1)
             (init-table (- position 1)))))

    ;;#The entry point, sets up the table and starts the calculation  
    (begin (init-table 4) (calculate amount coin-total)))

    ;;#Mapping from coin number to value, order doesn't matter
    (define (coin-value n)
      (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

The logic in this code is sound, it "works" but I'm worried that I'm not writing it very idiomatically. What suggestions or alterations would you make for this code?

Note: I stuck this # in the comments here so that the code highlighting would stop treating it like code and messing up the syntax highlighting

Answer 1

Well, I could try to rewrite it to not use mutation, but it looks like the mutation is just there as a memoization optimization. You could either pass the vector as an argument into calculate, or you could abstract the memoization via something like define/memo provided in memoize.plt, or just roll your own customized one as done here, which I think is just fine.

There are some surface changes you can make as well. For starters, the search-for function doesn't do anything with its arguments, so they can be removed. Next, defines have an explicit begin around the body, so the begin in update can be removed as can the begin near what your comments call the entry point.

The (init-table 4) is an optimization (works without it) that I'm not sure is even worth putting in; especially since I think it deserves a comment to explain that the magic number 4 is because (make-change n) should return 1 for 1 <= n <= 4. If you decide to leave it in, at least replace it by (vector-fill! v 1 0 4) assuming your using srfi-43. It might be different if your scheme dialect has it's own vector libs.

Finally, mapping coin number to value could use case instead of cond for a little less syntax as in:

(define (coin-value n)
  (case n
    ((1) 1)
    ((2) 5)
    ((3) 10)
    ((4) 25)
    ((5) 50)))

Answer 2

I would write the function like this:

(define (make-change amount)
  (define (make-change-with-coins amount coins)
    (cond ((< amount 0) 0)
          ((= amount 0) 1)
          ((null? coins) 0)
          (else (+ (make-change-with-coins (- amount (car coins)) coins)
                   (make-change-with-coins amount (cdr coins))))))
  (make-change-with-coins amount '(50 25 10 5 1)))

Most of the problems in the early parts of SICP can be solved with very few lines of code. The main idea behind functional programming is to think in terms of the list data structure and recursive functions without side effects. Note that make-change-with-coins has only one statement: no value is computed and then ignored.

The basic idea of this is that if I have coins of value N0, N1, N2, ... Nk, I can make an amount A in two ways: either with one or more coins of value N0 or with no coins of value N0.

As a general approach, you should write your code in the way that's the clearest expression of your algorithm; ignore optimizations for the moment. If your code is too slow, then go back and see if optimization is possible.