Haskellのメモ化のこと：その2

先日の記事をポストした後に思い出したようにやったことがメモ化についてネットで調べてみることでした…(はじめにやっとけば良いのに…)

メモ化, Memoize, Memoizationで検索するとwww.sampou.orgとwww.haskell.org が引っかかります。こちらのほうではデータストラクチャを積極的に使って行うMemoizeが書かれています。

どうやらHaskellのメモ化は能動的と受動的の2種類に分けることができるということでしょうか？まぁ、もちろん、能動的メモ化も受動的メモ化をうまく利用できればより効率よく達成できますよね。だから、受動的メモ化がいつおきるかを知っておくのは有用なことですね…

先日のリストとタプルの振る舞いの違いをもうちょっと踏み込んでみてみました…

import Debug.Trace

sumL = (trace "sumL 0 is called" 0) : zipWith (+) sumL [1..]

main = do
　print [(sumL!!3, sumL!!4)]
　print [(sumL!!3, sumL!!4), (sumL!!3, sumL!!4)]
　print [(sumL!!3, sumL!!4), 
　　　　(sumL!!3, sumL!!4), 
　　　　(sumL!!5, sumL!!6)]
　print ([sumL!!3, sumL!!4], 
　　　　[sumL!!5, sumL!!6], 
　　　　[sumL!!7, sumL!!8])
=>
sumL 0 is called
sumL 0 is called
[(6,10)]
sumL 0 is called
sumL 0 is called
[(6,10),(6,10)]
sumL 0 is called
sumL 0 is called
[(6,10),(6,10),(15,21)]
sumL 0 is called
sumL 0 is called
sumL 0 is called
([6,10],[15,21],[28,36])

これはちょっと面白いですね…1つ目から3つ目の例はリストの中にsumLを2つ含むタプルがそれぞれ１−３個入っているのですが、どれもトレースは2回しか出ません。この2回というのはどうやらということはタプルの中に繰り返されている回数に一致しているようで、!!Nの部分の違いにかかわらずsumLの結果はなぜか共有されているようです…一体どうゆう仕組みでこうゆう結果が出るのでしょう？謎は深まるばかりです…

4つ目の例でもトリプルに対してトレースが3回ですね…こちらでは前の例とは逆にトリプルの中にリストを入れてみました…

つぎにTree型も試してみましょう：

import Data.Tree

print $ fmap (sumL!!) $ 
　　Node {rootLabel=4, subForest = 
　　　　[Node {rootLabel=5, subForest = }]}

=>
sumL 0 is called
Node {rootLabel = 10, subForest = 
　　[Node {rootLabel = 15, subForest = }]}

ということで、うまくメモ化は起きているようですね…どうやらメモ化はリスト特有のものではないようです。

うーん…うなってしまいます…はっきりとした説明は今のところ見つけられていないし、自分なりの説明もはっきりとしたものはあがってきません…

今のところの僕の考えはこうです：

メモ化できるためには型の同一性がコンテナ側で要請されていなくてはいけない…

これはタプル内でメモ化が働かないのに、タプルを含むリストとしてはタプルの各要素についてメモ化が行われていることを説明しようとしたものです…
タプルという型自身は第一要素と第2要素の型は同じである必要がありません。

("hello", 4) :: (String, Int)

そのことが何かしらの形でメモ化の振る舞いに影響を与えているという考えです。
しかしながら、タプルを含むリストではリストの各要素が型の組み合わせ方の同じタプルしか含めません。
リストは各要素が同じ方であることを要請しているので、
[("hello", 4), ("world", 5)] :: [(String, Int)]
はできても
[("hello", 4), (Just "world", 5)]
は許されませんね…

ということで、
[(a, b)]という型のリストに関しては、型aと型bについて別々にメモ化が行われるようです…

メモ化されるのは、パラメタを取らない関数の実行結果のみ

これは例の中で
print [(sumL!!3, sumL!!4), (sumL!!3, sumL!!4)]
のように同じパラメタで(!!)が呼び出されているのにもかかわらず、その結果はメモ化されていません。これはすなわち、メモ化は値型(a)に対してされるものであって、関数型(a -> a)にされるものではないということのようです。

それじゃあ
sumL3 = sumL!!3
sumL4 = sumL!!4

print [(sumL3, sumL4), (sumL3, sumL4)]
とやればメモ化が期待できるかというと、じつは、できてしまうようです。

メモ化が起きるのはコンテナ型の中のみ

これは、サンプルの中でsumLがたくさん呼ばれているのに、メモ化は各行のリスト表現の中身にだけ起きていることからきています。

つまり、メモ化はc aな型cが型aについて行うことというもののようです。

以上をまとめるとメモ化はどうやらタイプシステムの上に構築されているということのようですね…

なんとなく受動的メモ化の適用ルールみたいなものが見えてきました…

ではでは。