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