メモ

Data.MemoCombinatorsモジュールについて言及したblog
http://www.amateurtopologist.com/2009/11/22/data-memocombinators-and-you/
を見つけて、何をどうしてCombinatorsというモジュール名にしたのかというのとどういう実装に成っているか知りたいので読んでみました。

blogの方ではメモ化フィボナッチ関数の実装をしていて、しかしモジュールの該当するコードを読んでもぱっと見た感じ明示的にmemoizeしているようには見えません。良く分からん！

ので、必要な部分だけ引っ張りだしてみて

{-
via http://www.amateurtopologist.com/2009/11/22/data-memocombinators-and-you/

Following is Essence of Data.MemoCombinators Module:
http://hackage.haskell.org/packages/archive/data-memocombinators/0.3/doc/html/Data-MemoCombinators.html

Ref : http://www.haskell.org/haskellwiki/Memoization
-}

{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ScopedTypeVariables #-}

import Data.Bits

type Memo a = forall r. (a -> r) -> (a -> r)

{-
10進10 -> 0b1010 -> [False,True,False,True]
-}
integralBits :: (Integral a) => a -> [Bool]
integralBits 0 = []
integralBits x = let (q,r) = quotRem x 2 in toBool r : integralBits q
    where
    toBool 0 = False
    toBool 1 = True

integralFromBits :: (Integral a) => [Bool] -> a
integralFromBits [] = 0
integralFromBits (x:xs) = unbit x + 2*integralFromBits xs
    where unbit True = 1 ; unbit False = 0

bool :: Memo Bool
bool f = cond (f True) (f False)
    where
    cond t f True  = t
    cond t f False = f

boollist :: Memo [Bool]
boollist (f :: [Bool] -> a) = table (f []) (bool (\x -> boollist (f . (x:))))
    where
      table :: a -> (Bool -> ([Bool] -> a)) -> [Bool] -> a
      table nil cons [] = nil
      table nil cons (x : xs) = (cons x) xs

fib5 = fib5'
    where
      fib5' 0 = 0
      fib5' 1 = 1
      fib5' n = fib5'' (n - 1) + fib5'' (n - 2)
      fib5'' x = f $ integralBits x
      f = boollist g -- calculating function!!
      -- f x = (boollist g) x -- 直前のfと同じように見えるが、こちらのfを使うと不味い
      g x = fib5' $ integralFromBits x

元の関数をごちゃごちゃ弄って等価っぽい関数に変換(η変換とか)しまわってたらfib5とかになってしまったのはさておき。

肝心な部分は

f = boollist g

と

bool :: Memo Bool
bool f = cond (f True) (f False)
    where
    cond t f True  = t
    cond t f False = f

で、fに関しては「gという関数」を計算させたくて、そこで重要なのがboolさんで、boolは引数fにTrueとFalseを適用させてしまう。

なので、

{-
fのcomputationを手動でやってみる。

boollist g
=>
table (g []) (bool (\x -> boollist (g . (x:))))
=>
table 0 (cond (boollist (g . (True:))) (boollist (g . (False:))))

boollist (g . (True:))
=>
table (g [True]) (bool (\x -> boollist ((g . (True:)) . (x:))))
=>
table (fib5' 1) (cond (boollist ((g . (True:)) . (True:))) (boollist ((g . (True:)) . (False:))))

boollist ((g . (True:)) . (True:))
=>
table (g [True,True]) (bool (\x -> boollist (((g . (True:)) . (True:)) . (x:))))
=>
table (fib5' 3) (cond (boollist (((g . (True:)) . (True:)) . (True:))) (boollist (((g . (True:)) . (True:)) . (False:))))

...
-}

という、2進化した木を作って行く感じです。

折角なのでHaskellWiki(http://www.haskell.org/haskellwiki/Memoization)を見てみると色々面白い事が書いていました。
例えば、

memoized_fib :: Int -> Integer
memoized_fib =
   let fib 0 = 0
       fib 1 = 1
       fib n = memoized_fib (n-2) + memoized_fib (n-1)
   in  (map fib [0 ..] !!)

とかは評価戦略に沿った実装になっていてすごひ。

先にこっちを知っていればData.MemoCombinatorsの実装ももうちょっと楽に読み解けたかもしれません。