ArrowLoopとCircularPrograming

Haskell Data Recursion Arrow

こうゆう問題を考えて見ましょう。

数字の入ったリストがある。そのリストの各要素をそのリストの最小値で引いた値を返す関数decWithMinを書け。つまり、

decWithMin [5, 10, 20, 4, 3, 100]
=> [2, 7, 17, 1, 0, 97]

そんなの簡単じゃんと：
decWithMin ls = map (\x -> x - min) ls
　　where
　　　　min = minimum ls

なんてやるわけなんですが、なんとこのコードには重大な欠陥が！...と大げさになるほどのことでもないのですが、要はこのコードはリストlsを2回トラバースしているわけですね...一回目はminimum ls、もう一回はmapで。でも、もうちょっと広いスコープで見ると、ちょっと面白いことに気づきます。
もしdecWithMinの実行結果を誰も見ないとしたら、HaskellはLazyなので実はlsは一回もトラバースされない可能性もあるわけです。逆に、decWithMinの結果が参照されているとすれば、参照された部分については最低3回トラバースされるわけですよね…

HaskellのLazinessを活用すると実はdecWithMinはトラバースを1回だけすれば済んでしまうのです。

decWithMin [5, 10, 20, 4, 3, 100]
の実行結果は、HaskellはLazyなので、
[5 - min, 10 - min, 20 - min, 4 - min, 3 - min, 100 - min]
という形になっているはずで、実際の要素の引き算はその要素が使われるときに実行されるわけです。ということは、decWithMinをうまく書くことができれば、minの値はdecWithMinの中では確定する必要がないわけです。

こんなことが実際できちゃうのかと驚いたわけなんですが、それをやるために用意されているクラスが実はArrowLoopらしいのです。最初にArrowLoopの名前を見たときは、これを使えばループが表現できるのかなーと勘違いしていました...ループのほうは、再帰呼び出しでやってくださいということのようです...ArrowLoopの定義のほうは以下のとおり：

class Arrow a => ArrowLoop a where
loop :: a (b, d) (c, d) -> a b c

なんだかfirstメソッド：
first :: a b c -> a (b, d) (c, d)
の正反対といった感じなわけですが、コメントを見るととんでもなく混乱します。

The loop operator expresses computations in which an output value is fed back as input, even though the computation occurs only once. It underlies the rec value recursion construct in arrow notation.
「ループ関数は返り値が入力パラメタとなる計算を表現しています。Arrow上での'rec'値再帰の基礎となります。」みたいなことが書いてあると思うんですが、なんだかもうぜんぜんわかりません。ごにょごにょと探していたら、http://www.haskell.org/haskellwiki/Circular_programming　にぶち当たりました。

ここの解説によると、どうやらloopは a (b, d) (c, d) なArrowを引数にとって、a b cのように見せてくれるのはシグネチャどおりなのですが、第一引数のArrowのパラメタdがフィードバックループを形成しているようです...？そんなこといわれてもぜんぜんピンときません...そこで、コードを見てみましょう。関数全般(->)もArrowLoopのインスタンスになっていて、そのインプリメンテーションはこんな感じです：

instance ArrowLoop (->) where
	loop f b = c where (c,d) = f (b,d)

やけにシンプルですが、だからといって、言ってることがすぐわかるわけでもありません…実はこれ、dachs_hippoさんのところで取り上げられている MonadFixのコードにそっくりです。どうやらこれは関数型言語の話を読んでいると時々出てくるY Combinatorというやつらしいですよ…

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

Y Combinatorの筋で攻めてみても僕の頭がついてこないので、先ほどのHaskell WikiにあるCircular Programmingのほうを読んでみると、Y Combinatorの名前は出さずにもうちょっと泥臭いドメインで話をしてくれています。そして、この記事にdecWithMinを一回のトラバースで終わらせる方法が書いてあったわけです。その方法とは以下のとおり：

decWithMinA :: [Int] -> [Int]
decWithMinA ls = (loop _decWithMinA) ls
　　where
　　　　_decWithMinA ([x], m) = ([x - m], x)
　　　　_decWithMinA ((x:xs), m) =  ((x - m) : xs', min x m')
　　　　　　where (xs', m') = _decWithMinA (xs, m)
			
簡略化のために少しエラーハンドリングを省いています。

何が起きているかというと、_decWithMinAの中に出てくるmというのは全て同じ変数を指していて、コードを実際に実行したときに、どこかmの値が参照される以前の時点でmの値が確定すれば、このコードはうまく動くようです。このサンプルでは、mの値が確定するのはリストの要素が1つになったとき、つまり：
_decWithMinA([x], m) = ([x - m], x)
です。
それ以外の場所でも、x - m　とやってみたり、 min x m'とやってみたりしていますが、これらはみんなリストの要素が最後の1つになって、ｍの値が確定されてから動くので、まったく問題ないようです…何が一番不思議かというと、変数の値が変化しないはずの関数型言語で、mは再帰の各段で変化を許されているように見えることです…不思議ですね…

ちょっとコードを眺めていると実は_decWithMinAだけを呼び出すことも可能なようです。でも、_decWithMinAを自分で普通に呼び出そうとすると、ｍとして何か値を渡してやらなくてはなりませんね…そして、loopは(c, d) = f(b, d)となるようなdが存在すると仮定して、それをdに入れておいてくれるような感じですね…

狐につままれたとはまさにこのこと。そのうちちゃんと理解できる日が来るのでしょうか？

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