Arrowパズル解答 (とArrowLoop解説)

まず最初にArrowLoopについて説明します。数学的な話は一切しません(できません)。

ArrowLoopの仕組み

ArrowLoopというクラスにはloopという関数が一つだけ属しています。このloopはArrowから新しいArrowを作り出してくれる関数です。
まずloopに入れるArrowはこんな形をしています。

入力が2つあり、出力も2つあります。ただし、Arrowは入力と出力がどちらも１つずつでなければならないので実際はタプルとして入出力します。標準ライブラリで定義されているArrowLoopクラスのインスタンスには普通の関数と、モナドをArrow化したKleisliというArrowがあります。

ここでは例として次のArrowを考えます。

swap_mul = \(x, y) -> (2 * y, 3* x)

実行例

> swap_mul (3, 4)
(8,9)

簡単な関数ですね。これをloopに入れてみます。loop関数は２入力２出力のArrowの１つの出力をフィードバックさせ、全体としては１入力１出力のArrowに作りかえるということをします。

これに数字を入れたら何が返ってくるでしょうか？

> loop swap_mul 3
18

3 * 3 * 2 = 18が返ってきました。上の図のまんまですね。

これはよくよく考えてみると、swap_mulの戻り値を引数として参照しているということです。普通の関数についてのloopの定義を見てみると、そのまんまの実装になっています。

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

戻り値であるはずのdが引数として渡されています。なんでこういうコードが通用するのかという説明も必要かとは思いますが、とりあえずはあまり深入りせずに上の図のイメージで捉えていきましょう。

ArrowLoopで無限リスト

前回の初級編の最初の問題の解説をします。

loop (snd &&& uncurry(:))
loop (snd &&& uncurry(++))

これはそれぞれrepeat関数とcycle関数のArrowによる実装です。

> loop (snd &&& uncurry(:)) 1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,........
> loop (snd &&& uncurry(++)) [1, 2, 3]
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,........

まず中身の式について説明が必要ですね。ここではrepeatの中身の式について説明します。
(&&&)はArrow固有の演算子で入力を2つに複製し、それぞれをArrowに通した後タプルとしてまとめるということをします。

今loopの中身は２入力２出力でしたので、下図のような感じになっています。sndやuncurryの説明は省きます。

普通の関数として書くと

snd &&& uncurry(:)  ==  \(x, y) -> (y, x:y)

です。

これをloopに入れるとこうなります。図では1を入力として与えています。

内部では何が行われるかというと、ひたすらフィードバックの先頭に1を追加するということが行われます。(じゃぁ一番最初の1は何に対して追加するんだというツッコミもあるかとは思いますが、あくまでイメージです)
[追記:Haskellは遅延評価ですから、ひたすら1を追加するという表現はおかしいですね。必要になっときに必要になった分だけ1を追加する処理が行われます。"追加する"ってのもおかしいんですけれど(汗)]

それをそのまま出力に出しているのですから、無限に1が並んだリストが生成されます。

図を見てもらえれば分かるように、aと1:aは同じ値ですから

a = 1:a

が成立します。これが1の無限リストになるということには納得してもらえるかと思います。普通再帰的なデータというのは名前をつけて、その名前を介して自分自身を参照します。しかし、loopを使用すると名前をつけずに再帰させる事ができるという事になります。

これは数学的に非常に意味のあることなのですが、ここでは深入りしません。こういう話はYコンビネータなどで調べてもらえれば詳しい解説が見つかると思います。

初級編の最後の

loop $ snd >>> id&&&(id&&&tail >>> uncurry (zipWith (+)) >>> (1:) >>> (1:))

はフィボナッチ数列を生成します。解説は省略します。

ArrowLoopで再帰関数

初級編では再帰的な"データ"を実装しました。中級編の問題では再帰的な"関数"を実装しています。

cond f = \x -> if f x then Left x else Right x

loop $ (snd&&&fst>>>app)&&&((<<<(cond(== 0)))<<<(const 1|||)
    <<<(uncurry(*)<<<)<<<(id&&&)<<<(<<<(subtract 1))<<<snd)

これは階乗を計算するArrowの定義です。

順を追って説明します。まず普通に階乗factを定義しましょう。

fact = \x -> if x == 0 then 1 else x * fact(x-1)

ここではあえて\x -> の形で書いています。とりあえずこれをloopに入れてしまいましょう。出力すれば一周して戻ってくるのでしたから

fact' = loop $ \(x, f) -> (f x, fact)
fact = \x -> if x == 0 then 1 else x * fact(x-1)

の様に一周して戻ってきたf(つまりfact)にxを入れれば、fact xが出力されます。ギャグの様なコードですが、この一旦出力して戻ってきた関数に引数を入れるというのが基本形です。

次はfactの部分を埋め込んでしまいましょう。ここでさっきと同じ話ですが、factを埋め込んでしまうのでfactという名前で自身を参照することはできなくなっています。しかし、出力された関数自身は一周して引数の部分に束縛されています。
なので、fを自身を参照するために使用することができます。(図の中のappはとりあえずは関数適用だと思ってください)

これをコードにするとこうなります。

loop $ \(x, f) -> (f x, \n -> if n == 0 then 1 else n * f(n-1))

高階Arrow

今のコードは変数を使用していてArrow的ではありません。これを変数を一切使わない形に書き換えます。
まずloopの中身がどんなArrowになっているかというと
入力: 数値xと関数fのタプル
出力: 数値f xと無名関数\n -> if n == 0 then 1 else n * f(n-1)のタプル
という感じになっています。つまり第２要素だけみれば、関数を受け取って関数を返す関数になっています。関数じゃないArrowだってありますから、この場合のloopの中身は「Arrowを受け取ってArrowを返すArrow。すなわち高階Arrow」ということになります。*1

まずは普通に数値を入出力するArrowのイメージを掴んでおきましょう。
例えばxを入力してx+2+3を出力するArrowはこう書けます。

((+ 2) >>> (+ 3))

イメージは工場の生産ラインみたいな感じでしょうか。(+ 2)とか(+ 3)という部品が流れてきたものに取り付けられていきます。

       (+ 2)   >>>    (+ 3)
         v              v
x ->  x + 2  -> x + 2 + 3

説明していませんが、(+ 2)や(+ 3)のようなものを関数の部分適用とかセクションとかって言います。詳しくは省きます。

Arrowを入出力するArrowはどう書けばいいでしょうか。関数型言語では関数も値ですから、(もちろんArrowも値)普通の数値などと同じように考えることができます。
まず入力からfが流れてくるとします。それを元にf>>>g>>>hというArrowを作るArrowは

((>>> g) >>>  (>>> h))

と書けます。上と同じですね。

       (>>> g)   >>>     (>>> h)
         v                    v
f -> f >>> g     ->  f >>> g >>> h

これで高階Arrowができました。後はこれを使って関数を組み立てていくだけです。

長くなってしまうので、先ほどのコードのn * f (n -1)の部分だけ説明します。

loop $ \(x, f) -> (f x, \n -> if n == 0 then 1 else n * f(n-1))

まず細かくArrow化していきましょう。最初に出力される側のArrowを作ります。ここは入力がnですから、

n-1         => subtract 1
f(n-1)      =>  (subtract 1) >>> f 
n * f(n-1)  =>  id&&&((subtract 1)>>>f) >>> uncurry (*)

ですね。nを複製し、片方はそのまま、もう片方は1引いた後fに入れ掛け算をしています。

次にこのArrowを出力するArrowを作ります。入力は(x, f)ですから、まずfだけとってしまって、順番に組み立てていきます。

         snd >>>((subtract 1)>>>) >>> (id&&&)                    >>>                           (>>> uncurry(*))
           v             v                 v                                                          v     
(x, f) -> f ->  (subtract 1)>>>f  ->  id&&&((subtract 1)>>>f)  -> id &&& ((subtract 1)>>>f) >>> uncurry(*)

これに条件分岐の為の(|||)などをくっつけていけば完成です。ただし、(>>>)演算子は右結合性の為に、この順番で書くと右から合成されてしまいますので、括弧をつけるとか(<<<)演算子を使うなどの注意が必要です。

ArrowApply

出力の第１要素は入力のfをxに適用したものですので、

(x, f) ->  f x

の様な変換を行いたいです。これは今までの方法では出来ません。ArrowとArrowの合成は上のようにできるのですが、Arrowへの入力は上のようにはかけません。
その為に、ArrowApplyというクラスが存在します。このクラスではappというArrowが定義されていてタプルの第1要素のArrowに第２要素を注入してくれます。

app (f, x) -> f x

ということで、これは(x, f)のxとfを入れ替えてからappに流し込めばOKですので

snd&&&fst>>>app

となります。
以上の2つの出力を&&&でつなげればタプルにしてくれるので、これで階乗を計算するコードの完成です。

上級編解答

loop $ (snd&&&fst>>>app)&&&((<<<(cond null))<<<(const []|||)
    <<<(uncurry(++)<<<)<<<(second(uncurry(:))<<<)<<<(uncurry(&&&))                             
    <<<(<<<app<<<(filter<<<(>)<<<head)&&&tail)
    &&&((head&&&)<<<(<<<app<<<(filter<<<(<=)<<<head)&&&tail))<<<snd)

は上と同じ方法でクイックソートを実装したものです。変数が1つもありません!(condの実装を除けば)。filterやheadやuncurryが複数箇所に散らばってますので、これはまだまだ短縮することができると思います。partition関数を使って一期に分割してしまってもよいかと思います。

ぜひいろんなコードを書いてみてください。おもしろいですよ。

こんなコードばかり書いていたらArrowは難読化の為のものなのだと誤解されてしまいそうですが、実際は適切に細かくパーツに分けてモジュール化をしていけば良いと思います。

また、前回話したように自分で新しい計算の方法をArrowとして定義することもできました。そして当然、自作Arrowを使用して今までのようなアルゴリズムを記述することができます。関数じゃないのに関数のようにアルゴリズムが書けるようになるわけですね。
その為には、自作したArrowをArrowLoop、ArrowApply、(説明してないですが、ArrowChoice、ArrowZero、ArrowPlusなどもあります)のインスタンスにすべく、appやloopなどを定義する必要があります。
次回はそういった事を書きます。