MonadFixの理解のために(1)---fixを考える

Haskell

Control.Monad.FixとData.Functionにfixなる関数が定義されています．

fix:(a->a)->a
fix f = let x = f x in x

何か詐欺みたいな定義です．この定義から分かることは

  • fixは関数fに対して，x=f xとなるx，つまりfの不動点（fixed point）を返す

ということです．

ここでおおっと思って次のようなコードを書いてみます．

f::Int->Int
f x = 2-x
p = fix f

x = f x = 2-x なのですから，x=1となってpを評価すると1になる！？とかつい期待してしまいます．上のfは恣意的に解（この場合はy=xとの交点で不動点）が整数になるようにしましたが，実際は整数からは簡単にはみ出します．果たしてHaskellは（METAFONTのように）方程式を解いてくるのでしょうか？

そこで実際にpを評価すると，もちろん型チェックは問題ありませんが，いつまでたっても計算します．停止しません．方程式を解いてくれるわけもありません．冷静に考えると計算を繰り返すだけの無限ループです．つまり

  • pを知りたいから，pの定義をみよう
  • fix fだ
  • fix f = f (fix x) だから，f (fix f)だ
  • てことは，f (f (fix f)) だ
  • てことは，f (f (f (fix) )) だ
  • ・・・・・

という流れになるのでしょう．

これはまさに数学でいうところの漸化式で，延々と繰り返すと（存在するならば）極限に到達します．漸化式で定義された数列に極限が存在するならば，その極限は漸化式の不動点になるということと一致します．不動点と極限，再帰性がこんな形で連結するなんて全然思いもしませんでした（気がつくと当たり前かもしれませんが。。。まさにコロンブスの卵）．

上のような無限ループを避けるには当然「停止条件」が必要です．とはいっても，f x = 2-xのような普通の関数だったら停止条件のつけようがないです．だから，繰り返しでてくるfix fそのものが何か条件を受け付けるものでないと実際には意味がありません．つまりfix fそのものが関数である場合が実用的なのでしょう．型で書くと

fix::(a->a)->a

なんですけども

fix::((a->a)->(a->a))->(a->a)

つまり，

fix::((a->a)->a->a)->a->a

となるパターンが有用なのかと考えてみます．

階乗を考える

ということまで整理すると，「不動点関数fixを使った階乗」というWeb上にいくつかあるサンプルが理解できてきます．これは

g :: (Int->Int)->Int->Int
g f n  | n==0      = 1
       | otherwise = n* f (n-1) 
fact = fix g

という形の階乗の定義です．これを最初にみたときはなんで？とかなり考え込みました．型とかいろいろ考えてやっと納得です．

型をみるとまさに上の考察と同じパターン，つまり，fact = fix g::Int->Intです．factに実際に値をいれて展開してみます．

fact n = (fix g) n -- nは0より大きいとしておきます
= g (fix g) n -- ここで，fix gの定義を使用．部分適用で g (fix g)は関数です
              -- 遅延評価でfix gは放置
= n * (fix g) (n-1)  -- g の定義より．gの定義のfがfix gになっている
                     -- 遅延評価でfix gは放置
= n * g (fix g) (n-1)
= n * (n-1) * (fix g) (n-2) 
= -- 以下同様に続く
= n * (n-1)* ... * 2 * (fix g) 1
= n * (n-1)* ... * 2 * g (fix g) 1
= n * (n-1)* ... * 2 * 1 * (fix g) 0
= n * (n-1)* ... * 2 * 1 * g (fix g) 0
= n * (n-1)* ... * 2 * 1 * 1 -- g の定義でn==0のときにはf（今はfix g）は関係ないので
                             -- 結局fix gは具体的には評価されない！！
= nの階乗

というわけです．遅延評価と「不動点という名前」に騙された感じです．本質的には同じですが，不動点というと「関数空間上の写像gで値を変えないを変えないものを先に確定させてから計算する」ように考えてしまいますけど，それは人間が先回りする，あらかじめ方程式を解いてしまう，ようなものなのでしょう．

このfixをYcombinatorというようです．いわゆるλ計算のものと形が違いますが，λ計算の表記のYcombinatorが満たす性質を満たしているので問題ないのでしょう（Haskellだと型の問題でλ計算の表記のものは定義できないとのことです）．

リストの最大値を得る

http://www010.upp.so-net.ne.jp/okshirai/ycomb-j.htmlを参考にさせていただいて，リストの最大値を得るfindmax::Ord a=>[a]->aを考えてみます．

findmax::Ord a=>[a]->a
findmax = fix g 
   where g f ns | ns == []     = error "Null List!" 
                | tail ns ==[] = head ns
                | otherwise    = max (head ns) (f (tail ns))

-- maxも引数にする
find'::Ord a=> (a->a->a)->[a]->a
find' h = fix g 
          where g f ns | ns == []     = error "Null List!" 
                       | tail ns ==[] = head ns
                       | otherwise    = h (head ns) (f (tail ns))

findmaxはPreludeのmaximumですが，Preludeではfoldl1で定義されています．find'のhにはmaxをいれればmaximum=findmax，minならminimum，(+)ならsumになります．というか，find'はほとんどfoldl1です．

もうちょっと具体例で遊びます．

お約束のフイボナッチと二項係数

-- fix::((a->a)->a->a)->a->a 
-- g::(a->a)->a->a
fib = fix g
    where g f n | n<=0      = 0
                | n==1      = 1
                | otherwise = f(n-1) + f(n-2)

-- fix::((a->a->a)->a->a->a)->a->a->a
-- g::(a->a->a)->a->a->a
comb = fix g
   where g f n r | r==0 = 1 
                 | n==r = 1
                 | otherwise = f (n-1) (r-1) + f (n-1) r