>>41
I went to sleep after posting this (actually I woke up to write it), but I've implemented what I was thinking of last night. I also made the process work with currency systems whose lowest denomination is not one. Something that's still not clear to me is when to make data abstractions local, and when to make them global, especially in the case of this generic memoization macro. It seems reasonable to have multiple implementations of maps for different situations, so reason tells me that the data abstraction should be made local, while my intuition tells me that data abstractions should not be made local to a macro. Similarly, it seems useful to be able to construct different sets of denominations so that you can for example make a `euro-change' or `øre-change', but the utility of having global procedures to define the largest denomination of a set etc. is not clear. Does anyone have any tips on when to make data abstractions local/global?
(define (make-map keys values) (cons keys values))
(define (null-map) (make-map '() '()))
(define (values map) (cdr map))
(define (keys map) (car map))
(define (args->key . keys) keys)
(define (extend-map key value map)
(make-map (cons key (keys map))
(cons value (values map))))
(define (lookup-map key map)
(let L ((k (keys map)) (v (values map)))
(cond ((null? k) #f)
((equal? key (car k)) (car v))
(else (L (cdr k) (cdr v))))))
(define-syntax def-memo
(syntax-rules ()
((_ (name args ...) body ...)
(define name
(let ((map (null-map)))
(lambda (args ...)
(or (lookup-map (args->key args ...) map)
(let ((result (begin body ...)))
(set! map (extend-map (args->key args ...) result map))
result))))))))
(define (make-kinds . kinds) (sort > kinds))
(define (change kinds)
(define (largest kinds) (car kinds))
(define (not-largest kinds) (cdr kinds))
(define (smallest? kinds) (null? (cdr kinds)))
(lambda (a)
(def-memo (C a n)
(let ((big-n (largest n))
(rest-n (not-largest n)))
(+ (cond ((= a big-n) 1)
((> a big-n) (C (- a big-n) n))
(else 0))
(cond ((smallest? rest-n)
(if (= (modulo a (largest rest-n)) 0) 1 0))
(else (C a rest-n))))))
(C a kinds)))
;; example usage
(define (øre-round a)
(let ((change (modulo a 100)))
(cond ((< change 25) (- a change))
((< change 75) (+ (- a change) 50))
(else (+ a (- 100 change))))))
(define (øre-change a)
((change (make-kinds 50 100 200 500 1000 2000 5000 10000 20000 50000 100000))
(øre-round a)))
(øre-change 1397)
;; => 112