Haskell Advent Calendar 2022 10 日目の記事です。

6 月からHaskell で AtCoder を始めました。まだまだ『灰色』 (レート 400 未満) ですが、そろそろ軌道に乗ったので面白かった点をノートしてみます。

技術的内容は 外部サイト (mdBook) に書いたので、合わせてお楽しみください。

内容は誤りを含む と思いますが、多めに見ていただけるようお願いします 🙇

背景

欲望が合体しました。

Haskell とは

公式サイト では "An advanced, purely functional programming language" と称していますが、まず構文に目を惹かれます。たとえば:

isPrime :: Int -> Bool
isPrime n
  | n <= 1 = False
  | n <= 3 = True
  | otherwise = loop 2
    where
      loop i | i >= n = True
             | n `mod` i == 0 = False
             | otherwise = loop (i + 1)

このくらいなら読めますが、やがて モナド が登場します。モナドが分からなくて、僕は Haskell と疎遠になりました。

AtCoder Beginner Contest (ABC) とは

ABC は毎週開催の『プログラミング・コンテスト』です。問題を解くプログラムを提出します。低速な解答は TLE (実行時間の超過) となって受理されませんから、 計算量の小さなアルゴリズム を考える必要があります。

詳しくは 競技プログラミングことはじめ などをご参照ください。

AtCoder を Haskell で

AtCoder では数学的素養が問われ、 『考察』の比重が『実装』よりも重い と言われています。でも実装がやりたいのです！　そこで Haskell を使うことにより、難度を『実装 > 考察』に逆転させます。

Haskell でやる気をハックし、一石二鳥を狙います。

半年後

自分に幻滅していました。

窮地

Haskell はダントツで難しい

Haskell が書けませんでした 。 API ドキュメントが読めず、コンパイルエラーも分かりませんし、 1 問解くのに 6 時間かかったりします。

何かを受信した

苦し紛れに Haskell Weekly Podcast を聞いていると、みんな Nix で環境構築して Coq で検証し、 Haskell で実装している ことに気付きます。壁のシミを眺めながら、自分はナードではなかったと呟くことになりました。

隣人について

AtCoder の Haskell 参加者 (Rated) は僕を含めて 6 ~ 8 人 程度です。身勝手な親近感を覚えます。

隣の Haskell は黒い

誰かの解答を見てみると、 Haskell とは思えない謎のコードを提出、見事 AC (受理) されています。 しかも爆速 ！　Tier 3 の言語 で C++ よりも速いのです。 なによ！！

あるいはコンテスト後の提出を見ると、 1 行で問題を解くコードゴルフが何通りも見られます。 Haskell すきーが伝わってくる気がします。例によって黒魔術なので 全く読めません 。

その他 IntMap 担当、 MVector 担当など、解き方にキャラクター性を感じてしまいます。再帰を使う人、 fold を使う人などの差も見られます。皆かけがえの無い情報源です。

コミュニティの強さ

最近では Haskell で ABC の解説を書いてくれる人がいたり、丁寧に質問に答えて頂いたりと、本当に助かっています。 Haskell に入門し、圧倒的な taker に成り下がろう。

振り返って

Haskell は Rust と似ている？

Rust を知っていると、型クラスや関連型は一撃です。プログラムの書き方もどこか似ている気がします。

とはいえ実際にコードを書くには様々な擦り合わせが必要で、

などの気付きがありました。『無い』ばかりで、有るものには気付いていない気がします。 HKT とか……？

最近は『型族』『データ族』など未知の概念に出会います。モナドの数も増えてきました。 Haskell の本領発揮は、来年の投稿にご期待ください。

久しぶりに Rust を触ると

関数型言語のユーザは『Rust の構文は汚い』とコメントします。僕はそこまで思いませんが、ポイントフリースタイルで高階関数を書きたい気はしました。『至高の言語 Rust』に綻びが見え始めたかもしれません。

ポスト Haskell, ポスト Rust で次に出て来た関数型言語こそが大本命かもしれません。しかし Haskell も大変なものであることは感じられてきましたから、これをやり直す人・作り直す人のバイタリティは計り知れません。遅延評価 (Haskell) でもいいじゃないかという気がしてきました。

良かった本

今度は本の感想で Haskell 入門を掘り下げてみます。

すごいHaskellたのしく学ぼう！

2012 年出版の Haskell 入門書です。巷で『最も簡単』と謳われていますが 十分難しい と思います。

ともあれ競技プログラミングです。 P244 の <$> 演算子を活用すれば、 AtCoder Beginners Selection 第 1 問 が解けるようになります:

module Main (main) where

main :: IO ()
main = do
  [a, b] <- map read . words <$> getLine :: IO [Int]
  let s = if even (a * b) then "Even" else "Odd"
  putStrLn s

以上、成果は『A 問題が解けるようになる』です。 B 問題からは、リストを使うと TLE (時間制限超え) になる危険があります。 AtCoder が始まりました 。

Haskellで戦う競技プログラミング 第2版

さっき読んだ 300 ページは何だったのか……？　梯子を外された気がしますが、課金で解決します。幅を利かせて参りましょう (?) 。

著者ブログ に目次があります。 vector を抑えれば B 問題が安定し、 モナドで失敗する 気持ちも味わえます。 ついに Haskell が始まりました！

ハイライト


特に嬉しかった情報としては:

じっくり書いてほしかった内容としては:

ところで MVector には末尾要素の push がありません。 snoc は \(O(n)\) の操作です。この本を読んだ後でも、 AtCoder の外では全く戦えないことが伺えます。

Haskell High Performance Programming

今年 1 番面白かった本 になるかもしれません。話の重要度が高過ぎました。

たとえば一時変数が GC を妨げるという恐ろしいエピソードがあります:

> Data.list.foldl' (+) 0 [1..10^6]
500000500000

> let xs = [1..10^6] :: [Int]
> Data.list.foldl' (+) 0 xs
<interactive>: Heap exhausted;

実際は最適化のおかげでエラーになりません。結局、アルゴリズム的な失敗の方が遥かに影響が大きいよと P16 にありました。つまり GHC の自慢話 を浴びただけです。 例が凶悪 過ぎて不安ですよ！

内容は『Haskellで戦う競技プログラミング 第2版』に還元される気がします。読んでも読まなくてもいい感じです。もう少しスローペースで詳しく頼むという場合には良いかもしれません。

競技プログラミングの鉄則

151 問の問題集です。 典型 90 問 が応用力を問うのに対し、本書はアルゴリズムのカバー率を重視しているとか。 著者ブログ から目次を確認できます。

難度設定が絶妙 です。よく自力で完答できますし、解けなくても丁寧な解答・解説が読めます。これでレベルアップできますよ！

『鉄則本』に挑むことは、アルゴリズムのテンプレートプログラムを育てる作業でもあります。競技プログラミングが大好きな『盆栽』作業に変わるわけなので、ある意味ゲームチェンジャーですね。このタイミングで出て来てくれたことに御の字です。

まとめ

Haskell で AtCoder に参加した結果、世の中には面白い人がたくさんいるという希望を見つけました。自分は大して面白くない現実にも気付きました。

特に『ナードな自分』というアイデンティティを失ったのが痛く、代わりに『灰色コーダー』 (プログラミングが下手) という客観的な評価が突きつけられます。

クダを巻いている場合ではありませんでした。テキストエディタを研ぎ澄ますとか、 Haskell でゲームを作るとか。そういった積み重ねの先、今よりも遥かなナードを目指さねばなりません。

もっと遊ぼう！

追伸

さっきの ABC で茶コーダーになっていました。灰色詐欺じゃん……！

図らずも色変記事になりました。次は DP を学んで緑色を目指します。

2022-12-atcoder-brown.png