AtCoder Beginners SelectionをHaskellで解く(1) ABC086A - Product

最近なんとなく私は関数型言語が好きなのではないか!という根拠のない直感に従ってHaskellを始めました。始めると言ってもHaskellで作りたいものが特にあるというわけでもないので,AtCoder Beginners Selection (ABS) をとりあえず埋めてみようと思います。先に言っておくとABSをHaskellで埋めてる人は私以外にもたくさんいるので,もし参考にするものを探しているのであれば他のHaskell上級者さんのブログをあたった方がいいかもしれません。

追加ルール

で,まあ普通に埋めてもよかったんですが,ちょっと変なルール追加した方が面白い気がしたので,単にACするだけでなく,以下のルールを追加します。

  • 関数をポイントフリースタイルで定義する。

コードゴルフとかでもよかったんですが,ゴルフはもう少しHaskellに習熟してからやった方が楽しいと思うので今回はパスしました。

具体的にはこんな感じのルールです。他人と競ってるわけではないのでふわっとしています。私が合法だと思ったら合法なのだ。

  • main 関数では,入力をパースして変数に代入し,関数 f を適用した結果を出力する。
  • 入力を空白で区切る,数値型に変換するなど,入力文字列から適切なデータ構造への変換はしてよい。
  • f を適用した結果を文字列型に変換,なども main 関数内で行ってよい。
  • f はポイントフリースタイル,つまり仮引数を用いずに定義しなければならない。

要は計算の本質パートをポイントフリースタイルで書こう,という感じです。ふわふわ。今後解き進めていくにあたって私に都合よくルールが少しずつ変化していくと思われます。

解答

今回解く問題はABS 1問目の ABC086A - Productです。簡単に言うと与えられた整数A, Bの積の偶奇判定をします。

とりあえず出来上がったコードがこちらです。

import Data.Bool
 
f = (bool "Even" "Odd".).(odd.).(*)
 
main = do
  [a, b] <- (map read . words) <$> getLine
  putStrLn $ f a b

やりたいことの雰囲気が掴めたかと思います。

解く

とりあえず普通に解きます。

f a b = if odd (a * b) then "Odd" else "Even"

しょっぱなから大問題発生です。if-elseはどうやったらポイントフリーにできるのか。そもそもifは関数じゃないし………。そこで「haskell if point free」とかでググるbool というif-elseと等価な関数の存在を知ります。これを使うと,

f a b = bool "Even" "Odd" $ odd (a * b)

というなんとかなりそうな形になります。うるさいことを言うと, bool は非ポイントフリースタイルで実装されているので,これを使って f をポイントフリースタイルにするのはルール上どうなんだ,と思いましたがまあ誰かと競ってるわけじゃないのでこれは合法ということにしちゃいます。もう少しHaskell力が上がってこれをどうにかできるようになったら再挑戦してみるかもしれません。

ここからはゴリゴリ変形していきます。気合で仮引数を右へ右へと動かしていって関数合成の形になったらすかさず . 演算子,という感じでやるとできます。

f a b = bool "Even" "Odd" $ odd (a * b)
f a b = bool "Even" "Odd" $ odd ((a *) b)
f a b = bool "Even" "Odd" $ (odd.(a *)) b
f a b = bool "Even" "Odd" $ (odd.((*)a)) b
f a b = bool "Even" "Odd" $ ((odd.).(*))a b
f a b = (bool "Even" "Odd").(((odd.).(*))a)$ b
f a b = ((bool "Even" "Odd").)(((odd.).(*))a)$ b
f a b = (((bool "Even" "Odd").).((odd.).(*))) a  b
f = (((bool "Even" "Odd").).((odd.).(*)))
f = (bool "Even" "Odd".).(odd.).(*)

完成!🎉🎉🎉

途中で括弧が多くなってきて,どれがどれに対応するのかわからなくなってくるので,これだけのためにVSCodeの対応する括弧に色をつける拡張機能を入れました。

marketplace.visualstudio.com

関数合成は結合法則が成り立つので,最後は結構カッコが外れます。最後じゃなくて途中で外していってもよかったかもしれません。

元のコードを知っているというのもあるとは思いますが,これくらい簡単な処理であればポイントフリースタイルでも挙動を頭の中で追える気がします。

というわけで「AtCoder Beginners SelectionをHaskellで解く」第1回, ABC086A - Productでした。これは今後も続くのでしょうか。続けられるのでしょうか。まあいけるところまで頑張ります。ポイントフリースタイルがキツくなってきたら普通に解こうと思います。

つづく

pizzacat83.hatenablog.com