w1 = (\x -> (\y -> f x y)) X と w2 = (\y -> f X y)が異なる時

http://twitter.com/ranha/status/6103936333
の弁明。

遠回り

先日のメモ化fib関数について色々弄っていたのでその過程の何ソレを書き出してみます。

まず大元の定義は

at :: ∀a.[a] → Int → a
at (a : b) 0 = a
at (a : b) (n + 1) = at b n

map' :: ∀a b.(a → b) → [a] → [b]
map' _ [] = []
map' f (a : b) = f a : (map' f b)

mem_fib = get_result
    where
      fib 0 = 0
      fib 1 = 1
      fib n = get_result (n - 2) + get_result (n - 1)
      get_result = at (map' fib [0 ..])

これは期待通りに働いてくれますが

mem_fib2 = get_result
    where
      fib 0 = 0
      fib 1 = 1
      fib n = (get_result (n - 2)) + (get_result (n - 1))
      get_result = (\v -> at (map' fib [0 ..]) v)

これは期待通りには働いてくれません。

mem_fib3 = get_result
    where
      fib 0 = 0
      fib 1 = 1
      fib n = (get_result (n - 2)) + (get_result (n - 1))
      allfib = map' fib [0 ..]
      get_result = (\v -> at allfib v)

これは期待通りに働いてくれます。

ちゃんと調べるのが面倒臭い時には、そうDebug.Traceです。

import Debug.Trace

...

mem_fib2 = get_result
    where
      fib 0 = 0
      fib 1 = 1
      fib n = (get_result (n - 2)) + (get_result (n - 1))
      get_result = (\v -> at (trace "mem_fib2" map' fib [0 ..]) v)

まずコイツから調べてみます。

*1259404021*Main> mem_fib2 0
mem_fib2
0

*1259404022*Main> mem_fib2 1
mem_fib2
1

*1259404023*Main> mem_fib2 2
mem_fib2
mem_fib2
mem_fib2
1

*1259404024*Main> mem_fib2 3
mem_fib2
mem_fib2
mem_fib2
mem_fib2
mem_fib2
2

まぁココまで来たら大体分かって、mem_fib2 4の時は1 + 3(= mem_fib2 2) + 5(= mem_fib2 3)で9個出るんでしょう

*1259404025*Main> mem_fib2 4
mem_fib2
mem_fib2
mem_fib2
mem_fib2
mem_fib2
mem_fib2
mem_fib2
mem_fib2
mem_fib2
3

これではてんでダメな事が分かります。メモ化したいんだから、こんな毎回呼ばれているようでは困ります。

なんでこんな事に成ってしまうのか・・・ですが、HaskellはCall-by-NeedというCall-by-Nameと比べて賢い子版を使っていて、Call-by-Nameは

(λx.なんとかかんとか)

のλ式に遭遇すると、そこで評価を止めます。つまりλ式のbodyを評価しない。

弱頭部正規形(Weak-Head-Normal-Form WHNF)というおどろおどろしい単語を見た事があるかもしれませんが、これがまぁそんな感じで、デフォルト遅延呼び出しな言語におけるλ式の評価戦略みたいなものです。

参考 : http://encyclopedia2.thefreedictionary.com/Weak+Head+Normal+Form
参考 : http://itpro.nikkeibp.co.jp/article/COLUMN/20070305/263828/?ST=develop&P=2

しかし、今回はコレが仇となってしまっています。

get_resultが呼び出される度に、肝心要の"map' fib [0 ..]"が毎回呼び出されて(作られて)しまっているわけです。

そういうわけであれば！！という事でmem_fib3

mem_fib3 = get_result
    where
      fib 0 = 0
      fib 1 = 1
      fib n = (get_result (n - 2)) + (get_result (n - 1))
      allfib = trace "mem_fib3" map' fib [0 ..]
      get_result = (\v -> at allfib v)

これは

*1259404026*Main> mem_fib3 2
mem_fib3
1

*1259404027*Main> mem_fib3 3
2

*1259404028*Main> mem_fib3 4
3

先と明らかに違う事が分かると思います。

とは言え、これがメモ化に直接繋がるかどうかというとまだあやふやな感じがします。

直接繋がる感覚は、reference(参照)の概念を知っていれば分かると思います。

mem_fib3 5がどのように評価されるかを見てみます！！

mem_fib3 5
=>
get_result 5
=>
at allfib 5
=>
at [fib 0@REF0,fib 1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 5
=>
at [fib 1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 4
=>
at [fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 3
=>
at [fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 2
=>
at [fib 4@REF4,fib 5@REF5,...] 1
=>
at [fib 5@REF5,...] 0
=>
fib 5
=>
get_result 3 + get_result 4

 get_reuslt 3
 =>
 at allfib 3
 =>
 at [fib 0@REF0,fib 1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 3
 =>
 at [fib 1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 2
 =>
 at [fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 1
 =>
 at [fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 0
 =>
 fib 3@REF3
 =>
 get_result 1 + get_result 2

  get_result 1
  =>
  at [fib 0@REF0,fib 1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 1
  =>
  at [fib 1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 0
  =>
  fib 1@REF1 => 1@REF1　よって

  allfibはこの瞬間
  [fib 0@REF0,1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...]
  となる！！

  get_result 2
  =>
  at [fib 0@REF0,1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 2
  =>
  at [1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 1
  =>
  at [fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 0
  =>
  fib 2@REF2
  =>
  get_result 0 + get_result 1

   get_result 0
   =>
   at [fib 0@REF0,1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 0
   =>
   fib 0@REF0 => 0@REF0　よって

   allfibはこの瞬間
   [0@REF0,1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...]
   となる！

   get_result 1
   =>
   at [fib 0@REF0,1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 1
   =>
   at [1@REF1,fib 2@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...] 0
   =>
   1

  =>
  fib 2@REF2 = get_result 0 + get_result 1 = REF0 + REF1 = 0 + 1 = 1　よって

  allfibはこの瞬間
  [0@REF0,1@REF1,1@REF2,fib 3@REF3,fib 4@REF4,fib 5@REF5,...]
  となる！

 =>
 fib 3@REF3 = get_result 1 + get_result 2 = REF1 + REF2 = 1 + 1 = 2 よって

 allfibはこの瞬間
 [0@REF0,1@REF1,1@REF2,2@REF3,fib 4@REF4,fib 5@REF5,...]
 となる。

 get_reuslt 4
 => ... に関しても同様で

 allfib = [0@REF0,1@REF1,1@REF2,2@REF3,3@REF4,fib 5@REF5,...]
 を得る事に成る。

最終的にmem_fib3 5の計算結果はREF3 + REF4 = 2 + 3 = 5となり、
allfib = [0@REF0,1@REF1,1@REF2,2@REF3,3@REF4,5@REF5,...]

REFxというのは、参照を表すみたいな雰囲気で１つお願いします・・・。

mem_fib3がメモ化出来るという事は説明出来ましたが、

mem_fib2で何故ダメかというのはWHNFという変な単語を出して来て誤摩化した感が余りに強いです。
まぁGHCの実装がどうなってるか知らないのであくまで予想ですが、mem_fib2のget_resultは引数が与えられる度に中の関数オブジェクトっぽいものが作られてしまっているので、mem_fib3のようにallfibが一貫して存在していないとか。多分。

mem_fibはなんでアレで上手くいくねん！！という感じだと思いますが、get_resultは1度使われると永遠使われる関数オブジェクトなので、そこにそこはかとなく存在している式「map' fib [0 ..]」は延々と使われるとかそんな感じなんじゃないでしょうか。

表題

fib 0 = 0
fib 1 = 1
fib n = get_result (n - 2) + get_result (n - 1)
get_result = (\l -> (\v -> at l v)) (map' fib [0 ..]) -- OK
{-
-- 多分コレと同じ
get_result = let l = map' fib [0 ..]
             in (\v -> at l v)
-}

fib 0 = 0
fib 1 = 1
fib n = get_result (n - 2) + get_result (n - 1)
get_result = (\v -> at (map' fib [0 ..]) v) -- Bad

という事で、ぱっと見同じく見えるこのコードが同じ挙動をしないのは、上で挙げた様なかくかくしかじかによって説明出来て、厳密に言えばHaskellでは違う、っていう感じなんでしょう。

で、多分この先の世界がPurely Functional Data StructureもといHaskell Programmingの何ソレでCircular Programmingとかetcetcなんでしょうけど手続きの世界の住人は一々こんな風に考えてると死ぬので、脳に革命を起こさないと辛いシーンが多々あります。

何が言いたかったかというと、名付けは大事ですよねという事ですね。
ちゃんと命名してあげれば存在するし、再帰だって自分の名前を呼んであげれば良い。

「萌え萌え　正しく名付ちゃお！！」とかいう本が出ないんですかね。オメガ欲しいですよ・・・。

参考 : http://homepages.inf.ed.ac.uk/wadler/topics/call-by-need.html#need-journal
参考 : http://en.wikibooks.org/wiki/Haskell/Graph_reduction