フィボナッチ数列をアレする

フィボナッチ数列

fib = 0:1:zipWith (+) fib (tail fib)

で、これを新しい名前を作ることなく、かつ無名関数を書かずにやってみる。まずは関数の形になおす。

fib = let fib' x y = x:fib' y (x+y) in fib' 0 1

fib'のパターンを書かないように変形する。

fib = let fib' = curry $ fst &&& (snd &&& uncurry (+) >>> uncurry fib') >>> uncurry (:) in fib' 0 1

Arrowさまさま…。次にfib'を、fixと無名関数使って変形。

(curry $ fix (\f->fst &&& (snd &&& uncurry (+) >>> f) >>> uncurry (:))) 0 1

これでfibもなくなった。なお、変形するついでにfib'だった関数のパラメータのパターンを変更して、タプルで受けるようにした。でも一番外側の形は変えたくなかったので、curryを適用している。
で、無名関数だけとりだして、変形していく。

\f->fst &&& (snd &&& uncurry (+) >>> f) >>> uncurry (:)
\f->((fst &&&) . (snd &&& uncurry (+) >>>)) f >>> uncurry (:)
(>>> uncurry (:)) . (fst &&&) . ((snd &&& uncurry (+)) >>>)

はい、fも消えた。全部合わせると、

(curry $ fix $ (uncurry (:) <<<) . (fst &&&) . (snd &&& uncurry (+) >>>)) 0 1

やったね！ただしどうにも不恰好…
ところで、別解。

fib = let fib' x y = x:fib' y (x+y) in fib' 0 1

先にfib'を消して、やっぱりxとyをタプルで受けるように変更。

fix (\f (x, y)->x:f (y, x+y)) (0, 1)

無名関数を変形して、パターンを書かないようにする。

\f (x, y)->x:f (y, x+y)
curry $ (snd >>> fst) &&& (second (snd &&& uncurry (+)) >>> uncurry ($)) >>> uncurry (:)

curryを適用しなければ、この関数の引数のパターンは(f, (x, y))という形で、そこからArrowでがんばっている。で、これが全体。

(curry $ fix (curry $ (snd >>> fst) &&& (second (snd &&& uncurry (+)) >>> uncurry ($)) >>> uncurry (:))) 0 1

最初のより長いけど、こっちのほうが変形は単純だと思う。短くする余地はあるけどもういいや。今日は満足した。