LoginSignup
17

More than 5 years have passed since last update.

ポイントフリースタイルへの道 〜最大公約数編〜

Last updated at Posted at 2015-07-02

概要

標準入力から改行区切りで2つの数を読み込み、最大公約数を出力するプログラムを題材にして、ポイントフリースタイルの練習を行います。

出典

出典は anarchy golf - Greatest Common Divisor です。
35byte が Haskell における最短コードらしいので、それを目指して頑張ります。

実装

単純な実装からポイントフリースタイルへ頑張って変換していこうと思います。

ナイーブな実装

まずは do 記法を使って単純に記述します。

main = do
  x <- readLn
  y <- readLn
  print $ gcd x y

全く問題無いですね。

通常記法へ変換

do 記法は単なるモナドのシンタックスシュガーであるため、これを通常記法へ変換します。

まずは y の部分を>>=とラムダ式で書き換えてみます。

main = do
  x <- readLn
  readLn >>= (\y -> print $ gcd x y)

x も同様にラムダ式で書き換えてみます。

main = do
  readLn >>= (\x -> readLn >>= (\y -> print $ gcd x y))

これで do が取れそうです。

main = readLn >>= (\x -> readLn >>= (\y -> print $ gcd x y))

無事に通常記法へとたどり着きました。

ラムダ式をポイントフリースタイルへ変換

関数的記述に変換することができたので、ポイントフリースタイルへ変換していきます。
基本的に括弧で括る -> $で括弧を外す -> .で関数合成という手順でポイントフリースタイル化は可能なようです。

\y -> print $ gcd x yをポイントフリースタイル化

まずは一番内側のラムダ式である\y -> print $ gcd x yをポイントフリースタイル化します。
これはすでに括弧が外れて$のみの状態ですので、print . gcd xとすれば良さそうです。

main = readLn >>= (\x -> readLn >>= (print . gcd x))

大丈夫でした。

\x -> readLn >>= (print . gcd x)をポイントフリースタイル化

今度は\x -> readLn >>= (print . gcd x)をポイントフリースタイルへと変換します。
見るからに強敵です。どうしたら良いのか全くわからないので、まずは演算子を括弧で括って通常の関数と見なしてみます。

とりあえず>>=を括りだしてみます。

main = readLn >>= (\x -> (>>=) readLn (print . gcd x))

まだまだどうしていいかわからないので、今度は.を括りだしてみます。
printgcd xの合成をしているので、(.) (print) (gcd x)となる点に注意が必要です。
printgcd xの間に$を置いておけば括弧は使わずに済みそうです。

main = readLn >>= (\x -> (>>=) readLn ((.) print $ gcd x))

さて、次ですが、(>>=)に注目すると、readLn((.) print $ gcd x))の2引数を取る関数となっています。この間に$を置けば括弧が外せそうなので試してみます。

main = readLn >>= (\x -> (>>=) readLn $ (.) print $ gcd x)

なんと外せました。$にできたので、今度は.を使った関数合成にしてみます。

main = readLn >>= (\x -> (>>=) readLn . (.) print $ gcd x)

動きました。すでに難読すぎてヤバイですね。. (.)とか何だコレ……。

さて、次ですが、今回の変換でgcd xをしてから、(>>=) readLn . (.) print関数に渡すという意味になっているので、$を外して.による関数合成が使えそうです。

main = readLn >>= (>>=) readLn . (.) print . gcd

キタキタキタキタ━━━(゚∀゚≡(゚∀゚≡゚∀゚)≡゚∀゚)━━━━!!

無事、ポイントフリースタイルへとたどり着きました……!
長かった……本当に長かった……!!

更なる高みへ

括弧で括られている演算子があるので、括弧を外して中置記法へ戻してみます。

正直何がなんだかわかりませんが、最初に結合するであろう右の方から見ていくと、(.) print . gcdで括弧付きの演算子が使われています。
(.)は2引数を取る関数とみなせるので、おそらくその右側には2つの引数が存在していると思います。
無理やり考えてみると、(.) (print .) gcdとなるということでしょうか。やってみます。

main = readLn >>= (>>=) readLn . (.) (print .) gcd

うわ、動いた。動いたので中置記法へ変換しておきます。

main = readLn >>= (>>=) readLn . (print .) . gcd

とりあえず1つ演算子の括弧を取り除くことが出来ました。

次は(>>=)を取り除きたいと思います。
(>>=) readLnの部分ですが、これは単純に2引数関数に部分適用した状態になんとなく見えるので、(readLn >>=)と書き換えてみます。

main = readLn >>= (readLn >>=) . (print .) . gcd

動いた……!

ゴルファーを目指して

ポイントフリースタイルとしては割りと完成形な気がしますが、35byte には到底及びません。
最初の目標に 35byte と書いた手前、ここでやめるわけには行かないので、短くする方法を考えてみます。

ぼんやり眺めてみると、readLn >>=というのが被っていますね。
よし、括りだしましょう!!

括りだしたいのですが、よく見るとこの関数、readLnという関数と(readLn >>=) . (print .) . gcdという関数が>>=の引数となっている状態なので、このまま置き換えることはできなさそうです。
$や括弧で区切りを入れて、括り出せそうな形に変形してみます。

main = (readLn >>=) $ (readLn >>=) . (print .) . gcd

動きました。

良い感じに(readLn >>=)という共通関数ができたので、それを定義して置き換えてみます。

r = (readLn >>=)
main = r $ r . (print .) . gcd

動きましたー!!あとは余分な空白を全て除去すれば……!

r=(readLn>>=)
main=r$r.(print.).gcd

35byte キタ━━━ヽ(∀゚ )人(゚∀゚)人( ゚∀)ノ━━━!!

まとめ

全ての基本は「括弧で括る -> $で括弧を外す -> .で関数合成」であると信じている。
ポイントフリースタイルへの道のりは険しく遠い。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
17