参照透過性と言えばメモ化
そういや誰かがHaskellではメモ化がデフォルトだと言ったので その場で一緒に確かめたらそんなことはなかった. 入出力まで含めて参照透過性を作ってしまったHaskellなんだから, 本当にそうであってもいいと思ったのに
Land of Lisp を読んでてヤバいメモ化を思いついた！と思ったけど 書いてみたら別にそんなことはなかった.
メモ化はメモ (cache) として例えばハッシュテーブルを使うけど
関数そのものをデータを保存するためのものとして使うこと
そう言えばHaskellで経路探索問題を書く課題で、マップのデータとして 関数を使ってそんなことしてるのは私だけだったのを思い出した
-- 複数あるブロックの座標を与えます
b = [[1,3], [2,1], [5,3], [5,6]]-- 私はこう書いた
b 1 3 = True
b 2 1 = True
b 5 3 = True
b 5 6 = True
b _ _ = Falseだって、リストから具体的にデータを取得するの面倒でしょ getter関数どうせ定義するんでそ？ 線形時間かかるし 私のなら、データを直接 getter関数として書くことになる
人に見せたら、このコードはやばいと言われたけれど
で、本題
;; 普通のメモ化関数
(define fib
(let1 memo (make-hash-table)
(lambda (n)
(cond ((<= n 1) n)
((hash-table-get memo n #f) => values)
(else
(let1 ans (+ (fib (- n 1)) (fib (- n 2)))
(hash-table-put! memo n ans)
ans))))))レキシカルスコープに変数 memo をハッシュテーブルとして作成 副作用満載にキャッシュを更新する
ハッシュテーブルの構造を利用する代わりに、(memo n) という 手続きを作る (memo n) は (fib n) の答えを知らなければ #f を返す. 最初はただ #f を返す定数関数である. その時、memoという手続き自体を更新してしまう
(cond ((memo n) => values) ; values は恒等関数
(else (update-memo! ...)))こういう感じ 具体的に フィボナッチを計算するのは 下
(define (fib2 n)
(define (memo n) #f)
(cond ((<= n 1) n)
((memo n) => values)
(else
(let ((ans (+ (fib2 (- n 1)) (fib2 (- n 2))))
(memo0 memo))
(set! memo (lambda (m) (if (= m n) ans (memo0 m))))
ans))))(hash-table-get memo n #f) とかいう長いゲッターが (memo n) とかいう簡単になる、のはいいけれど、 手続きを更新するトコがちょっとやばい
あー、あのねー、 最初間違えてて、fib2からfibを呼び出してて、fibってのは はじめに書いた方 それで全然fibもfib2も速度変わらなくてすげーって思ってたんだけど
関数を毎回それを包み込む関数に更新するとかいうことして 残念ながら非常に遅いです
まあ、ただの冗談だってことで