キミならどう書く Scheme編

「キミならどう書く」の問題。
http://ll.jus.or.jp/2006/blog/doukaku2
先日はC++で書いたわけだが、今回はScheme版を考えてみた。ハッシュテーブルはGaucheの拡張を使っている。メモ化関数が汎用的でない形に変形せざるを得なかったのが多少残念だが、分離できただけでも上等だろう。Gaucheだと勝手に多倍長演算してくれるのであふれる心配もない。かなり大きい値を与えても案外速く終わる。

(use srfi-1)

(define (memoize f)
  (let ((table (make-hash-table)))
    (hash-table-put! table 1 1)
    (lambda (x y)
      (let ((memo (hash-table-get table x #f)))
	(if memo
	    (+ memo y -1)
            (let ((result (f x y)))
              (hash-table-put! table x (- result y -1))
              result))))))

(define (f n step)
  (memoized-f
   (if (even? n) (/ n 2) (+ 1 (* 3 n)))
   (+ 1 step)))

(define memoized-f (memoize f))

(define (h n)
  (if (> n 0)
      (max (memoized-f n 1) (h (- n 1)))
      0))

(define (main args)
  (print (h 100)))

Document ID: 537ddd52d40ff014f0c8e532b61735b0