fixを使うためのヒント

効率化の話はなんだか疲れるので、またデータ再帰の話へ脱線…
id:dachs_hippoさんのfixに関する記事をボーっと読み返していてあることに気づきました…

氏のサンプルのひとつは階乗の計算だったわけですが：

import Data.Function

g :: (Int -> Int) -> Int -> Int
g rec 1 = 1
g rec n = n * (rec $ n - 1)

main = print $ (fix g) 4

ここに出てくる関数gは無理にfixを使わなくても当然かけるわけです…

g :: Int -> Int
g 1 = 1
g n = n * (g n - 1)

main = print $ g 4

この2つを比較して見えてくることは、fixを使ったほうで出てくるgの第一引数recはほとんど関数g自身の別名のような存在だということです…逆に考えれば、fixを使ったコードが書きたければ、まずは普通の再帰呼び出しのパターンでコードを書いて、再帰呼び出しの部分だけ書き換えればよさそげです。

もう一つ気づいたこと、それはfixを使ったコードでもっと単純な例があるということです。

import Data.Function

g :: (Int -> Int) -> Int -> Int
g _ i = i

main = print $ (fix g) 4

まぁ、こうやってさらしてしまうと｢当たり前じゃんか！｣なわけですが、個人的にはfixというとなんだかYコンビネータによる再帰呼び出しが必ず起きているような気がしていたので…実際には、再帰をするかしないかは関数gに完全に任されているわけですね…

もう、何度目かわかりませんが、fixの定義を見てみます：

fix ::  (a -> a) -> a
fix f = x
	where x = f x

ここで定義されている変数xはその宣言部で自分自身を参照しているデータ再帰パターンです。ということはC言語などで出てくる

x = x + 1

のようないんちき数学な式ではなくて、

x = f x

はむしろHaskellのプログラムの内部表現形式であるところのグラフ表現として解釈したほうがよさそうです。つまり、関数fのパラメタと帰り値が同一な変数なわけですから

のようなループを描いているようなイメージです…こうなっていたらfix idなんてやった時点で無限再帰ループ後スタックオーバーフローに陥るのも無理はないような気になってきます。

でも、dachs_hippoさんの話にもあったようにfix::(a->a)->aのaをb->bに置き換えると話が変わってきます。

fix :: ((b -> b) -> b -> b) -> b -> b

のようなイメージでしょうか…なんだか複雑ですが、aの型が単なる値から関数になったことで出入り口のなかったfix fに入り口と出口ができました。

ということで、なんとなくfixを使ったコードはかけるようになってきたような気がするのですが、一体なんでfixを使ったコードを書きたいのかがいまいちわからんです…

WikiPediaのラムダ計算の項を読むと、ラムダ計算の理論にとってのYコンビネータの重要性はラムダ計算では無名関数しかないので再帰呼び出しをする計算を書きたかったらYコンビネータを使うしかないからということのようです…Haskellでは関数に名前をつけることは簡単にできますね…

今読んでいるRecursive Monadic Bindingsの論文を眺めた感じではfix/mfixの有用性の一部はControl.Arrow.loopのようにデータ再帰によるところがあるようです…しかしながら、僕にはfixを使って再帰的データとして定義されていxをうまく利用するコードが思いつきません…

きょうはこのへんで。
ではでは。