lisp change machine

dynamic programming mixed with HOFs. originally an exam question. brain on fire for an undergrad fuckwit like myself

(define (change amt coins)
(cond
((= amt 0) '(()))
((or (<= amt 0) (null? coins)) '())
(else
(fold-right (lambda (a b) (append a b))
'()
(map
(lambda (n)
(map
(lambda (u)
(append (list n) u))
(change (- amt n)
(filter (lambda (k) (>= k n)) coins))))
coins)))))

;; -----------------------------------------------------------------------

(define (display-nl u)
(display u)
(newline))

(define display-elements
(lambda (u)
(map display-nl u)))

(define (demo r k)
(display-nl '-----------------------------)
(display r) (display ';;) (display k) (newline)
(display-nl '=============================)
(display-elements (change r k))
(display-nl '-----------------------------)
(newline))

;; -----------------------------------------------------------------------

(newline)

(demo 5 '(1 2 5))
(demo 13 '(1 3 5 7))
$ ./lisp <change.lisp

Loaded `prefix.txt'

-----------------------------
5;;(1 2 5)
=============================
(1 1 1 1 1)
(1 1 1 2)
(1 2 2)
(5)
-----------------------------

-----------------------------
13;;(1 3 5 7)
=============================
(1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 1 1 3)
(1 1 1 1 1 1 1 1 5)
(1 1 1 1 1 1 1 3 3)
(1 1 1 1 1 1 7)
(1 1 1 1 1 3 5)
(1 1 1 1 3 3 3)
(1 1 1 3 7)
(1 1 1 5 5)
(1 1 3 3 5)
(1 3 3 3 3)
(1 5 7)
(3 3 7)
(3 5 5)
-----------------------------

>>6

Sorry about that, SICP background showing again. in the lectures they use Scheme throughout but refer to it verbally as "Lisp". I will be careful to be more pedantic in future