短い関数をArrowのコンビネータで組み直す競技.
競技であるから, 一応ルールを書いとかなきゃね.
- 使える関数は, Prelude/Control.Arrowでエクスポートされているもの.
- 関数hogeを実装せよ, とは, hogeを変数を使用せず書けということである. hoge x = fst x とか hoge = \x -> foo x のxや, where節, let式は認めない. 補助関数の定義, パターンマッチ, ガードも認めない. ifは許す.
- 実装の長さとは, hoge = foo bar bazのfからzまでの文字列としての長さとする. この長さが短いほうが良いものとする.
- スペースを除くことは構わない. ただし, もちろんコンパイルが通る範囲で.
- GHC拡張は使ってはならない. 例えばTupleSections.
- Preludeでエクスポートされている関数hogeを実装せよ, とは, Prelude hiding (hoge)とし, Prelude.hogeを使わずに実装せよ, という意味である.
- 指定された関数と全く同じ型, 作用の関数を組まねばならない. 逆に言えば, 恒等的な簡約は許される(尤も問題が悪いという話である).
これくらいかなぁ. 割と抜け道があるかもしれない.
じゃぁ, 例題.
【問1】curryを実装せよ
【答】
curryはPreludeでエクスポートされているので, 例えば
c = curry
は有効な回答ではない. Prelude hiding (curry)とした上で, curryの実装を考える.
まずは
curry f x y = f (x, y)
と書いてみる. もちろん, f x yなどと書いているのでダメ.
curry f x y = f ((,) x y)
curry f x y = (f . (,) x) y
curry f x = f . (,) x
curry f x = ((f .) . (,)) x
curry f = (f .) . (,)
curry f = (. (,)) (f .)
curry = (.(,)).(.)
したがって,
curry = (.(,)).(.)
となった. 長さは10である.
【答終わり】
こんな感じ. curryみたいな簡単な関数だとArrow関係ないやん.
【問2】次の関数plusを実装せよ
plus = \m n f x -> m f (n f x)
【答】
plus = \m n f x -> (m f.n f) x
plus = \m n f -> m f.n f
plus = \m n f -> (.) (m f) (n f)
これは競技だから, (.)じゃなくてArrowなら(<<<)使えよなんていうArrow狂の戯言を聞いている暇はない.
plus = \m n f -> (app.((.).m &&& n)) f
uncurryなんて使ったらその文字数でおそらくアウトだろう.
plus = \m n -> app.((.).m &&& n)
plus = \m n -> ((app.).((.).m&&&)) n
plus = \m -> (app.).((.).m&&&)
plus = \m -> (app.).(((&&&).((.).))m)
plus = \m -> (((app.).).(((&&&).((.).))))m
plus = ((app.).).(((&&&).((.).)))
以上の変形から,
plus = ((app.).).(&&&).((.).)
長さは22である.
【答終わり】
ちょっぴり難しい関数になると, (&&&)などを使わないと本当に表現できなくなることがある.
上の回答は一例であって, もしかしたらこれよりも短いがあるかもしれないが, もしそういうのを見つけたら読者の勝ちという事で.
【問3】次の関数sevenを実装せよ
seven = \f x -> f (f (f (f (f (f (f x))))))
【答】
まずは, 次のようにかけることに気がつく.
seven = \f -> f.f.f.f.f.f.f
しかしこれではfのラムダ式を使っているのでアウトである. 一つの回答は, (&&&)で以て
seven = app.((.)&&&app.((.)&&&app.((.)&&&app.((.)&&&app.((.)&&&app.((.)&&&id))))))
と書いてみる. Arrowを使った標準的な回答であるが, あまりに長すぎてダメダメである. そこで, iterateを用いて
seven = iterate((app.).((.)&&&))id!!6
長さは29である. ところがどっこいである. foldlで簡単に書ける.
seven = \f -> foldl1(.)$replicate 7 f
これを変形して
seven = foldl1(.).replicate 7
21文字である.
【答終わり】
Arrowの演算子はどれも三文字なので, 割と他の方法を模索したほうが短くなることがある.
じゃぁ最後に一つ.
【問4】次の関数predを実装せよ
pred = \n f x -> n (\g h -> h (g f)) (\u -> x) (\u -> u)
自分の答えはこの下に書いた. ぼくの答えを見る前にまずは自分で考えて欲しい.
割と素直な変形で出てきたのは次の式
pred = (((.const).(($id).)).).(.(flip($).).flip($))
44文字かな.
もしかしたら読者に負けるかもしれない><
nもfもxも一回しか参照されないので, Arrowとかほとんど関係ない感じだけど...
いろいろ考えたけど, ほとんどで(.)のセクションが発生する. (.)が短くて便利やしな.
なんかいい問題ないかなぁ...