ブログに書いてみるとよく分からなくなってきました 🙃

Haskell-jp で回答をもらいました。

@lotz84_ さんの記事や GHC のプロファイルに出てくる CAF がよく分かってなかったのをまとめる。

`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 はラムダ式でない。 $n ≧ 0$ 。）の形の式で次の場合に限りそれはスーパーコンビネーターである。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 という形になっていました)

趣味はデバッグ……

関数のメモ化

`fact` のメモ化

Constant Applicative Form・Super Combinator

fact のメモ化

Constant Applicative Form・Super Combinator

`fact` のメモ化