Control.Arrow - コードの恵み

『プログラミングHaskell』の次に『Real World Haskell』を読みはじめた。
でも先に Control.Arrow とか Control.Applicative が何であるかを知りたい。
ありがたいことに日本語のブログが結構あるので読ませてもらって少し分かってきた。

99 questions/Solutions/10 - HaskellWiki

encode :: Eq a => [a] -> [(Int, a)]
encode = map (\x -> (length x, head x)) . group

encode :: Eq a => [a] -> [(Int, a)]
encode xs = map (length &&& head) $ group xs

これを読んで (&&&) の定義を調べたことがあった。

(&&&) :: a b c -> a b c' -> a b (c, c')

となっている。
2つだったらまだ理解できるのにとか思っていたがやっと気がついた。

class Category a => Arrow a where

の部分を読み飛ばしていたのがまずかった。
a は Arrow の a でモナドの m と同じだった。

Java 風に書けば B を引数に C を返す関数という意味だ。

interface Arrow<B,C>

Arrow の instance に (->) があって Arrow は関数より抽象度が高いことが分かった。

とりあえずの Arrow の部分だけ実装*1。

class ArrowOps {
  static def '&&&'(Closure a, Closure a_) {
    return { List l -> l.collect { [a(it), a_(it)] } }
  }
  static def '***'(Closure a, Closure a_) {
    return { List l -> l.collect { def (b,b_) = it; [a(b), a_(b_)] } }
  }
}

def arr    = { Closure a -> a }
def first  = { Closure a -> { List l -> l.collect { def (b,d) = it; [a(b), d] } } }
def second = { Closure a -> { List l -> l.collect { def (d,b) = it; [d, a(b)] } } }

use (ArrowOps) {
  assert [[3, 2], [4, 4], [5, 6], [6, 8], [7, 10]] == { it + 2 }.'&&&'{ it * 2 } ([1,2,3,4,5])
  assert [[3, 2], [4, 4], [5, 6], [6, 8], [7, 10]] == { it + 2 }.'***'{ it * 2 } ([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]])
  assert [[3, 1], [4, 2], [5, 3], [6, 4], [7, 5]]  == first { it + 2 } ([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]])
  assert [[1, 3], [2, 4], [3, 5], [4, 6], [5, 7]]  == second{ it + 2 } ([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]])
}

他に実装している人がいないか探したら JavaScript で Arrow.js というのを発見した。
ソースはまだ詳しく調べていないのだが解説がとても分かりやすかった。

とりあえず Arrow を使ってみるということでアリ本の Ants の問題を Haskell で実装してみる。
棒の上を n 匹のアリが右か左に移動していなくなるまでの最小、最大時間を求める問題。
アリの初期位置 xs、棒の長さ l が与えらる。

import Control.Arrow
import Test.HUnit


solve :: Int -> [Int] -> (Int, Int)
solve   l    = (maximum *** maximum) . unzip . map (minimum &&& maximum <<< (\x -> [x, l-x]))
solve'  l    = (maximum *** maximum) . unzip . map (minimum &&& maximum <<< (\(x,y) -> [x,y]) <<< id &&& (l-))
solve'' l xs = (maximum *** maximum) $ unzip $ [(minimum &&& maximum) [x, l-x] | x <- xs]


testSolve = runTestTT $ test [
  (4,8) ~=? (solve   10 [2,6,7]),
  (4,8) ~=? (solve'  10 [2,6,7]),
  (4,8) ~=? (solve'' 10 [2,6,7])]

Groovy の assert の代わりに HUnit を使ってみた。

2011-05-15 追記

Arrow 関連のリンクを張ろうとしたが多すぎた。
とりあえず Haskell を学習する上で理解できないときにすることをメモしておく。理解できないときはここに戻ってくること。

最初に型を調べる

Haskell は関数型なので in と out が必ずあるはずだし、:type を使えば組合せても追いかけていける。型さえ理解していれば hoogle で型検索してそこから別の型に変換する関数を調べることもできる。

簡単な言葉で説明する

Haskell の関数は単体ではそれほど難しいことをしているわけではないはず。型を見て何をしているのか理解できないときは、言葉にしてみる。図による説明が分かり易いというのはこの段階を終えてからの話。最初から図をみると混乱する。図はイメージを固めるのに使う。

目的まで一気に理解しようとしない

キーワードが分かり検索して調べられる段階
コードを読んで理解できる段階
その概念を使ったコードが自由に書ける段階

コードを追える段階までいけば他の人のコードを見て上達するはずなので無理しない。
デザインパターンのように目的があってコードがあるとは限らない。何を行っているかの理解を優先する。

私は、想像の範囲内のことしかできない道具を作りたいとは思わない。
Bjarne Stroustrup

Haskell は逃げない

知らない言葉が多すぎるときは学習する順序を間違えている。貪欲法で枠にとらわれず理解できる部分から学習していく。外堀が埋まればいつか本丸も落ちる。

「急ぐことはない。ゆっくりと造れ。宋は逃げぬよ」
『地果て海尽きるまで(下)』森村誠一

*1:Arrow.hs を見るとまだ知らない遅延パターンが使われていたので今回は適当に実装