ブログに書いてみるとよく分からなくなってきました 🙃
Haskell-jp で回答をもらいました。
@lotz84_ さんの記事や GHC のプロファイルに出てくる CAF がよく分かってなかったのをまとめる。
qiita.com
fact のメモ化
lotz さんの記事の階乗 fact 関数を題材にする。
fact :: Int -> Integer
fact 0 = 1
fact n = fromIntegral n * fact (n-1)
lotz さんの記事よれば、次の実装だとメモ化されるとのこと。
memoize :: (Int -> a) -> Int -> a
memoize f = (map f [0..] !!)
fact :: Int -> Integer
fact = memoize fact'
where
fact' 0 = 1
fact' n = fromIntegral n * fact' (n-1)
な、なんで……
1つめを fact1、2つめを fact2 として GHCi で確かめてみる。
> :set +s
> fact1 50000 `seq` pure ()
(2.44 secs, 2,605,979,968 bytes)
> fact1 50000 `seq` pure ()
(2.41 secs, 2,605,979,968 bytes)
> fact2 50000 `seq` pure ()
(2.50 secs, 2,613,580,040 bytes)
> fact2 50000 `seq` pure ()
(0.00 secs, 88,432 bytes)
確かに fact2 の2回めの評価はすぐに終わっている。
簡単のために fact2 を次のように書き換える。
fact3 :: Int -> Integer
fact3 = (map fact' [0..] !!)
where
fact' 0 = 1
fact' n = fromIntegral n * fact' (n-1)
> fact3 50000 `seq` pure ()
(2.47 secs, 2,611,180,024 bytes)
> fact3 50000 `seq` pure ()
(0.00 secs, 88,432 bytes)
同じようにメモ化されている。
では次のように書き換えると？ポイントフリー化されていたのを引数を明示するようにした。
fact4 :: Int -> Integer
fact4 x = map fact' [0..] !! x
where
fact' 0 = 1
fact' n = fromIntegral n * fact' (n-1)
> fact4 50000 `seq` pure ()
(2.58 secs, 2,619,180,432 bytes)
> fact4 50000 `seq` pure ()
(2.59 secs, 2,619,180,432 bytes)
メモ化されない。
もう1つ、ラムダ式で定義すると？
fact5 :: Int -> Integer
fact5 = \x -> map fact' [0..] !! x
where
fact' 0 = 1
fact' n = fromIntegral n * fact' (n-1)
> fact5 50000 `seq` pure ()
(2.57 secs, 2,619,180,432 bytes)
> fact5 50000 `seq` pure ()
(2.52 secs, 2,619,180,432 bytes)
メモ化されない。
何か特別な形である必要があるみたい。
Constant Applicative Form・Super Combinator
Haskell High Performance Programming によると、その特別な形は Constant Applicative Form（定作用形）というらしい。プロファイルを取ると Cost Centre に CAF と書かれてあるやつ。
www.packtpub.com
項が定作用形あるとは、項がスーパーコンビネーターでありかつラムダ式でないものである。
Constant applicative form - HaskellWiki
とりあえず、項がラムダ式であるとダメだそうなので fact5 は CAF ではない。
項がスーパーコンビネーターであるとは、項が定数もしくは、項がコンビネーターであり全ての部分項がスーパーコンビネーターであるものである。
Super combinator - HaskellWiki
これは次の定義と同値だそう。
任意の \x1 x2 … xn -> E（E はラムダ式でない。
。）の形の式で次の場合に限りそれはスーパーコンビネーターである。E における自由変数は x1, x2, … xn のみで、かつ E に出現するラムダ式は全てスーパーコンビネーターである。
fact3 が CAF であるかを確認する。
fact3 :: Int -> Integer
fact3 = (map fact' [0..] !!)
where
fact' 0 = 1
fact' n = fromIntegral n * fact' (n-1)
map fact' [0..] !! はラムダ式でないためスーパーコンビネーターであればよい。
map fact' [0..] !! は定数でないため部分式が全てスーパーコンビネーターであればよい。
部分項である map は、あ、あれ？定数でないしスーパーコンビネーターでもなくただの変数では……？2つめの定義においても x1, x2, … xn 以外の自由変数だし……
…………
……
…
いかがでしたか？関数がメモ化関数になるためには定義が CAF でないといけないようです 😎
なんで fact3 が CAF なのか教えてください 🙏
Haskell-jp で回答をもらいました。
（Markdown モードで引用の中でコードブロック書くのどうやるんだ……）
@mizunashi-mana
スーパーコンビネータは，一般の文脈では確かにコンビネータで部分項がスーパーコンビネータであるものを指しますが， CAF の文脈では，
- ラムダ式でない
- ローカル関数が全てグローバルに出しても問題ない定義になっている
だと思うのが良いと思います．厳密には，
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/rts/storage/gc/CAFs
に書いてある通り，要はサンクとなる static closure のことを指しています．
ところでメモ化の要因は，確かに fact3 が CAF であることもありますが，一番の要因として， Core では関数適用の引数は let を通して変数に束縛されることになるので，実際にはこのプログラムは
fact3 = (!!) fact3'
where
fact3' = map fact' l
l = [0..]
fact' 0 = 1
fact' n = ...
みたいなものと等価になります (厳密にはこれも怪しいですが) ．で， fact3' が CAF となるからというのが大きいですね (なお実際 GHC 8.6.5 では fact3' が floating out されていて， fact3 自体は最終的に eta expand されて fact3 = \x -> (!!) fact3' x という形になっていました)
