fixと無限リストの相性

昨日のポストは単なるいかさまだったわけですが、これに懲りずに、また何か展開があったら懲りずにデータ再帰についてポストしていきたいと思います。(泣)

それとは別に、fixで無限リストを生成するコードが書けたのでそれについて簡単に書いておきたいと思います。

a -> aな関数fをパラメタにとるときにfixで値を返す方法の一つはこんなやつでした：

fix (\_ -> 1)
=> 
1

fixで無限再帰がいつ起きるかというと関数fがそのパラメタを評価したときです。だから、パラメタを見る前に値を返さなくてはいけないわけですね…更に、fixの特徴として、fix fが返した値はfへのパラメタがとしてそのままわたってくるわけです。こんなのはどうでしょう？

fix (\x -> 1 : x)

これはrepeat 1と同じ結果で無限個の1を含むリストができます…無限リストを返す関数ならば、無限再帰になっても使い道はありますね…

take 5 $ fix (\x -> 1 : x)
=>
[1, 1, 1, 1, 1]

となるわけです。

ちょっとひねって：

take 5 $ fix (\x -> 1 : map (+1) x)
=>
[1, 2, 3, 4, 5]

なんていうのもできます…

フィボナッチ数列をやってみました。i番目の値は：

fib i = if i > 1 then
	fib(i - 1) + fib(i - 2)
	else i

という数式で求められます。つまり、自分の直前2つの要素の和なわけですね…（最初の2つは１ですね。)
こうゆう再帰はf:: (a->a)->a->aなfixで書けば：

fib = fix (\f i -> if i <= 2 
	then 1 else (f $ i - 1) + (f $ i - 2))

とかけます。これをf::a->aなfixでやるのはどうも無理そうです。何せfにfixの外側からパラメタiを与えて、それを再帰が深くなるごとにi-1とやったりする方法がないからです。でも、最初にあげた無限リストを使った方法ならこうかけます：

fib = fix $ \x -> [1, 1] ++ (zipWith (+) x $ tail x)

(print.(take10)) fib
=>
[1,1,2,3,5,8,13,21,34,55]

みたいな感じですね…

なんとなくfixの使い方がわかってきた気がします。
ただ、できなかったのはf::a->aなfixで階乗を書くことです…

今日はこの辺で。
ではでは。