; catalan numbers
(define (choose n k)
(if (zero? k) 1
(* n (/ k) (choose (- n 1) (- k 1)))))
(define (catalan n)
(if (zero? n) 1
(- (choose (+ n n) n) (choose (+ n n) (- n 1)))))
(do ((i 0 (+ i 1))) ((< 30 i))
(display i) (display #\tab)
(display (catalan i)) (newline))
(define-syntax define-memoized
(syntax-rules ()
((define-memoized (f arg ...) body ...)
(define f
(let ((cache (list)))
(lambda (arg ...)
(cond ((assoc `(,arg ...) cache) => cdr)
(else (let ((val (begin body ...)))
(set! cache (cons (cons `(,arg ...) val) cache))
val)))))))))
(define-memoized (catalan n)
(if (zero? n) 1
(let loop ((i 1) (count 0))
(if (< n i) count
(loop (+ i 1) (+ count (* (catalan (- i 1))
(catalan (- n i)))))))))
(do ((i 0 (+ i 1))) ((< 30 i))
(display i) (display #\tab)
(display (catalan i)) (newline))
OyBjYXRhbGFuIG51bWJlcnMKCihkZWZpbmUgKGNob29zZSBuIGspCiAgKGlmICh6ZXJvPyBrKSAxCiAgICAoKiBuICgvIGspIChjaG9vc2UgKC0gbiAxKSAoLSBrIDEpKSkpKQoKKGRlZmluZSAoY2F0YWxhbiBuKQogIChpZiAoemVybz8gbikgMQogICAgKC0gKGNob29zZSAoKyBuIG4pIG4pIChjaG9vc2UgKCsgbiBuKSAoLSBuIDEpKSkpKQoKKGRvICgoaSAwICgrIGkgMSkpKSAoKDwgMzAgaSkpCiAgKGRpc3BsYXkgaSkgKGRpc3BsYXkgI1x0YWIpCiAgKGRpc3BsYXkgKGNhdGFsYW4gaSkpIChuZXdsaW5lKSkKCihkZWZpbmUtc3ludGF4IGRlZmluZS1tZW1vaXplZAogIChzeW50YXgtcnVsZXMgKCkKICAgICgoZGVmaW5lLW1lbW9pemVkIChmIGFyZyAuLi4pIGJvZHkgLi4uKQogICAgICAoZGVmaW5lIGYKICAgICAgICAobGV0ICgoY2FjaGUgKGxpc3QpKSkKICAgICAgICAgIChsYW1iZGEgKGFyZyAuLi4pCiAgICAgICAgICAgIChjb25kICgoYXNzb2MgYCgsYXJnIC4uLikgY2FjaGUpID0+IGNkcikKICAgICAgICAgICAgKGVsc2UgKGxldCAoKHZhbCAoYmVnaW4gYm9keSAuLi4pKSkKICAgICAgICAgICAgICAgICAgICAoc2V0ISBjYWNoZSAoY29ucyAoY29ucyBgKCxhcmcgLi4uKSB2YWwpIGNhY2hlKSkKICAgICAgICAgICAgICAgICAgICB2YWwpKSkpKSkpKSkKCihkZWZpbmUtbWVtb2l6ZWQgKGNhdGFsYW4gbikKICAoaWYgKHplcm8/IG4pIDEKICAgIChsZXQgbG9vcCAoKGkgMSkgKGNvdW50IDApKQogICAgICAoaWYgKDwgbiBpKSBjb3VudAogICAgICAgIChsb29wICgrIGkgMSkgKCsgY291bnQgKCogKGNhdGFsYW4gKC0gaSAxKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChjYXRhbGFuICgtIG4gaSkpKSkpKSkpKQoKKGRvICgoaSAwICgrIGkgMSkpKSAoKDwgMzAgaSkpCiAgKGRpc3BsYXkgaSkgKGRpc3BsYXkgI1x0YWIpCiAgKGRpc3BsYXkgKGNhdGFsYW4gaSkpIChuZXdsaW5lKSk=