Erlang/2005/09/04/Note:memoise

うむ。N=1000程度でスローダウンするのはやっぱりおかしい。

Scheme版

(define (memoise f)
  (let ((m '()))
    (lambda (x)
      (cond ((assoc x m) => cdr)
            (else
             (let ((n (f x)))
               (set! m (cons (cons x n) m))
               n))))))

(define (fib x)
  (if (<= x 1)
      1
      (+ (fib (- x 1)) (fib (- x 2)))))

(set! fib (memoise fib))

GaucheやscmだとN=10000でも大丈夫だし。 どこかおかしいに違いない。

と思ったらN=10000時にScheme 48がheap overflowで死亡。 N=8000くらいならなんとか。

うーむ。