SICP Exercise 2.19 - how to extend this?

Question

I am just exploring functional programming via SICP, and am wondering how I can extend Exercise 2.19 to do something more useful (and which seems to require side-effects).

The exercise involves a program that counts the number of ways one can make change for a given amount (in pennies) with a given a list of coin denominations. The solutions is quite simple (cc stands for "count-change"):

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(define (first-denomination coinTypes) (car coinTypes))
(define (except-first-denomination coinTypes) (cdr coinTypes))
(define (no-more? coinTypes) (null? coinTypes))

You can see the relevant SICP section here and this links to description of the algorithm if above is not clear.

I first wanted to see what actual combinations of coins constitute each way to make change so I wrote my own version that prints out each solution as a list:

(define (count-change amount coinTypes)
    (define (cc amount coinTypes currChangeList)
        (cond ((= amount 0) 
                    (display (reverse currChangeList)) 
                    (newline) 
                    1)
              ((or (negative? amount) (null? coinTypes)) 
                    0)
              (else (+ (cc amount (cdr coinTypes) currChangeList)
                       (cc (- amount (car coinTypes)) coinTypes (cons (car coinTypes) currChangeList))))))
    (cc amount coinTypes ()))

So here's where I am stuck: I want to modify my method so that instead of returning an integer result = # of ways to make change, and simply printing each way during it's computation, I want it to return a list of the solutions (a list of lists, the length of which = # of ways to make change). However, I am at a loss of how to make this happen. It's easy to do in imperative/OO languages, but I can't figure out how to do it functionally.

Does anybody have any idea of how to achieve this? It seems like it should be a pretty easy thing to do for an experienced functional coder.. Please help satisfy my curiosity, and net yourself some coding karma :)

Thanks

Since solving a problem is much more fun than reading a solution: what if the result of cc wasn't the number of ways to make change, but a list of them? — molbdnilo
thanks for the hint! you're right, solving a problem is much more fun — noobler

to_the_crux to_the_crux · Accepted Answer · 2013-01-30T09:02:59

(define (count-change amount coinTypes)
    (define (cc amount coinTypes currChangeList)
        (cond ((= amount 0) 
               (list (reverse currChangeList)))
              ((or (negative? amount) (null? coinTypes)) 
               '())
              (else
                (append
                   (cc amount (cdr coinTypes) currChangeList)
                   (cc (- amount (car coinTypes))
                       coinTypes
                       (cons (car coinTypes) currChangeList))))))
    (cc amount coinTypes '()))

SICP Exercise 2.19 - how to extend this?

1 Answers