Haskellの再帰とCのループの違い - 取り急ぎブログです

今日は、Haskellでのmapについて少し考えてみたいと思います。
Cでこんなコードを書いてみます:

void foo()
{
	int rg[10]={};
	int i;
	
	for (i = 0; i < 10; i++)
		rg[i] = i;
		
	for (i = 0; i < 10; i++)
		rg[i] *= 2;
		
	for (i = 0; i < 10; i++)
		rg[i] += 100;
	
	for (i = 0; i < 10; i++)
		printf("%d\n", rg[i]);
}

この関数fooにはループが４つありますね...一つ目は配列rgの中身を初期化してます。２つ目と３つ目は各要素に計算をかけている。最後のループで表示してますね...そして、このコードが走るときは配列は初期化の部分を除いて３回走査されますね…話の都合上、初期化の部分を分けて考えるとして、このコードは次のように書き換えることができますね…そして、書き換えた結果、３つあったループは一つになります。

void foo()
{
	int rg[10]={};
	int i;
	
	for (i = 0; i < 10; i++)
		rg[i] = i;
		
	for (i = 0; i < 10; i++)
		printf("%d\n", (g[i]) * 2 + 100);
}

Haskellに書き換えます。

foo :: IO ()
foo = mapM_ (print) $ map (+100) $ map (*2) [1..10]

と１行ですんでしまいますね。うれしくなっちゃいますね。HaskellはCなどの言語に比べて、とても簡潔に物事が記述できるのが気持ちいいですね。でも、言いたかったのはそのことではないんです。

mapの定義は:

map _ [ ]= [ ]
map f (x: xs) = f x : map f xs

ですよね？そして、HaskellはLazyなので、map (*2) [1..10]の結果のリストから最初の要素をとろうとしたときにおきることは:

(x: xs) = map (*2) [1..10]
	x = 1 * 2 : 
	xs = map (*2) [2..10]

だけなわけですよね…だとしたら、map (+100) $ map (*2) [1..10] の結果のリストから最初の要素をとろうとした時は:

(x:xs) = map (+100) $ map (*2)[1..10]
	= map (+100) $ (1 * 2: map (*2) [2..10])
	
	x = 1  * 2 + 100
	xs = map (+100) $ map (*2) [2..10])

となるわけで、それぞれのmapの中で起きていることがCの場合よりも何というかより深い形で混ざっているような気がしませんか？式をまとめてmapを一つに変えた場合と比べてみると:

(x:xs) = map (*2 + 100)[1..10]
	= (1 * 2 + 100: map (*2 + 100) [2..10]
	
	x = 1  * 2 + 100
	xs = map (*2 + 100) [2..10])

ということで、Cの場合では別々におきる(*2)と(+100)の計算がHaskellの例では計算をまとめてもまとめなくても結果として一つのまとまりである(+100).(*2)として評価されている感じです…
とはいっても、mapの回数だけリストのトラバースは起きているし、関数型なおかげで、新しいリストがmapを呼び出す回数だけ生成されているはずです。関数型であることから来るメモリー消費を避けるためにmutableなIOUArrayなんかを持ってくると、今度はそれぞれのマップがmapMになってしまって（つまり、各要素の評価がその場で起きてしまう。）、Cの動きにずっと近くなっちゃいますね...配列の要素が１億個あるんだけど、使うのは最初の何個かだけというときはHaskellのリストを使って関数型で行くのが圧倒的に有利ですね...でも、その１億個の要素全部使うという場合はCのようなモデルでないとメモリの消費がひどくて実行すらできないということもありえそうです...まぁ、CではLazyはそう簡単には手に入らないけど、Haskellは両方提供しているので、優位に立つことができるのでしょうか？

一歩進んで、map f $ map g $ xsという式を見て、map f.g xsという最適化がされたらさらに強力ですね…実はリストはApplicativeなので、
　~~pure f <*> pure g <*> （ZipList xs)~~（追記：これがダメな理由はこちらを参照してみてください。）
　pure f <*> ( pure g <*> （ZipList xs) )
と書くことができますね...もし、<*>の定義で
(<*>) (Pure a) (Pure b) = Pure $ a b
なんていうのが追加できたら、計算をまとめる操作をコンパイラが勝手にやってくれるようになりますね...なんだか、やってみたらできそうな感じです…

今日はこの辺で...