読者です 読者をやめる 読者になる 読者になる

Arrow golfなんていうのも面白いかもしれない

Haskell

短い関数をArrowのコンビネータで組み直す競技.

競技であるから, 一応ルールを書いとかなきゃね.

  1. 使える関数は, Prelude/Control.Arrowでエクスポートされているもの.
  2. 関数hogeを実装せよ, とは, hogeを変数を使用せず書けということである. hoge x = fst x とか hoge = \x -> foo x のxや, where節, let式は認めない. 補助関数の定義, パターンマッチ, ガードも認めない. ifは許す.
  3. 実装の長さとは, hoge = foo bar bazのfからzまでの文字列としての長さとする. この長さが短いほうが良いものとする.
  4. スペースを除くことは構わない. ただし, もちろんコンパイルが通る範囲で.
  5. GHC拡張は使ってはならない. 例えばTupleSections.
  6. Preludeでエクスポートされている関数hogeを実装せよ, とは, Prelude hiding (hoge)とし, Prelude.hogeを使わずに実装せよ, という意味である.
  7. 指定された関数と全く同じ型, 作用の関数を組まねばならない. 逆に言えば, 恒等的な簡約は許される(尤も問題が悪いという話である).

これくらいかなぁ. 割と抜け道があるかもしれない.

じゃぁ, 例題.


【問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とかほとんど関係ない感じだけど...
いろいろ考えたけど, ほとんどで(.)のセクションが発生する. (.)が短くて便利やしな.
なんかいい問題ないかなぁ...