HaskellでAtCoderに参戦して水色になった

コメントを残す

3月下旬からAtCoderのRatedコンテストに参加しています（AtCoderプロフィール）。この度、5月26日のABC128でようやく水色になりました（AtCoder社長の記事によると、これは上位15%に相当するらしいです）。

使用言語はHaskellです。コンテストの時間中に提出したコードは全てHaskellだったと思います。

この記事では、Haskellを使う理由や、Haskellで競技プログラミングをするコツ、AtCoderでHaskellを使う際のアレコレなどを書いていきます。「水色になるための方法」みたいな話はしません（できません）。

目次

Haskellを使う理由

私のメイン言語はHaskellなので、競技プログラミングでもHaskellを使うのは自然な発想です。

ただ、Haskellは工夫すれば高速なコードを書けますが、あちこちに「遅くなる」罠があります。罠に怯えるくらいならHaskellをやめる、という選択もありますが、私としては、競プロでHaskellをやる上でどういう罠があるかを見極め、Haskellで高速なコードを書くための知見を貯めたい、と思っています。

まあ勉強がてらRustとかで競プロをするのもアリだとは思いますが、Haskellに慣れきってしまった体で（好きな言語が使える競プロにおいて）わざわざ他の言語を使うのは相応の活性化エネルギーが必要です。

ちなみに、某paizaのスキルチェックではHaskellが使えないので仕方なくC++で頑張っています。（私がHaskellをやり始める前は（C++03時代の）C++をガリガリやっていたので、C++も得意言語の一つです。今のC++はrange-based forや無名関数があって、Haskellほどではないですが便利です）

Haskellで書く上でのコツ

AtCoderの問題をHaskellで解く話に関しては、すでにいくつか記事が書かれているのでそちらも参照してください：

また、競プロに限らずHaskellで高速なプログラムを書くコツについては、私が昔書いた記事があります：

大抵の注意点は紹介した記事を読めば大体カバーされているのですが、重要な注意点は何回でも強調する価値があるので、この記事でも繰り返しておきます。

入出力：Stringは遅い

@hsjoihs氏の記事では、整数列の入力を受け取るのに map read . words <$> getLine というコードを使っています。初心者向けの解説であまり性能を気にしても仕方がないのであの記事ではあれでいいのだと思いますが、Haskell中級者以上は map read . words <$> getLine からは卒業するべきです。

まず、Haskell標準の文字列型 String は、汎用的なリスト型 [a] の要素を Char にしたもので、効率が悪いです。また、words :: String -> [String] 関数は入力文字列全体を複製するので、その点でも効率が悪くなります。

せいぜい1個か2個の整数を読み取るならともかく、読み取る整数が数千・数万個あると、 String 型の弱点はかなり大きなものになってきます。具体的には、入力だけで数百ms使ってしまう場合もあります。

解決策としては、紹介した他の記事でも触れられているように、 ByteString を使うことです。（Unicode文字列を使う場合は Text を使うことになります。入力がUnicode文字列な問題の例としては、 Xmas Contest 2018 の J – Japanese Exponentation があります）

Data.ByteString で提供されている関数は ByteString をバイト列（Word8 の列）として扱います。一方で、Data.ByteString.Char8 で提供されている関数を使うと ByteString を Char の列として扱ってくれるので、「ASCIIの範囲に制限された String の代替品」が欲しい場合はこっちをimportしましょう。以下、 import qualified Data.ByteString.Char8 as BS とします。

標準入力から1行読み取る関数の ByteString 版は BS.getLine です。スペース区切りでリストに分割する場合は BS.words が使えます。read 関数の入力はあくまで String なので、 BS.unpack :: BS.ByteString -> [Char] を使って変換するか、Int の場合は BS.readInt :: BS.ByteString -> Maybe (Int, BS.ByteString) を使います。

とりあえず ByteString を使ってみたい、という人は map read . words <$> getLine を map (read . BS.unpack) . BS.words <$> BS.getLine で置き換えましょう。結局 String を使ってるじゃないか！と思われるかもしれませんが、

  • words :: String -> [String] は入力文字列のほぼ全体をコピーするのに対して BS.words :: BS.ByteString -> [BS.ByteString] は入力文字列をコピーしない
  • read . BS.unpack での String の使い方は「一瞬だけ使ってゴミになる」ので、GCの特性によってはそんなに負担にならないかも……？（自信なし）

なので、全部 String で済ませるよりはマシです。特に、1つの入力行に大量の整数が入っている場合に効果的です。

もっと効率的にやりたい、という人は（整数の場合） BS.readInt を使いましょう（多倍長整数の場合は BS.readInteger）。ただし、帰ってくる型が Maybe に包まれたタプルなので read をそのまま置き換えることはできません。 fst . fromJust . BS.readInt という風にするか、 words と組み合わせるのをやめて unfoldr (BS.readInt . BS.dropWhile isSpace) <$> getLine としましょう。後者は Vector の unfoldr 系関数にも応用できます。

read系関数は型の曖昧性の温床です。プログラム全体を見ても型が確定しない場合は型注釈を書く必要がありますが、その際のノウハウは後述する TypeApplications のところを読んでください。

配列について

配列は1次元なら Data.Vector, 2次元以上なら Data.Array を使います。ただし、要素が Int や Double などのプリミティブ型なら、より効率的なunboxed vector / unboxed arrayを使うこともできます。vectorの場合は要素が (Int, Double) のようなタプルの場合でもunboxed vectorが使えます。

可変な配列の場合は Data.Vector(.Unboxed).Mutable や Data.Array.(ST/IO) を使います。

Haskellの場合、可変な配列の操作は読み取り・書き込みともに IO や ST などのモナドを使うことになります。そうすると、純粋な関数からは使いづらかったり、fold系演算が使いにくかったりして不便です。そこで、「可変な配列として構築してその後は不変な配列として使う」だとか「最初から不変な配列として構築する」などの方法で頑張ります。

1次元配列の構築時に破壊的更新をしてその後は不変な配列として使いたい、という場合は Data.Vector(.Unboxed).create が使えます。

累積和のようなパターンの場合は、scan系関数が便利です。scan系関数をうまく使うと、破壊的更新の代わりになったりします。

AtCoderでのHaskell

GHCのバージョンが古い件

2019年5月現在、AtCoderで使えるHaskellはGHC 7.10系です。GHC 7.10系では、最近のGHCで使える便利な拡張が一部使えません。

競技プログラミングの場面で使えると便利な、最近のGHCで追加された拡張をいくつか挙げてみます。

Strict, StrictData

Haskellで高速なコードを書くにはBangPatterns拡張を使い、不要なサンクが作られないようにするのがコツです。しかし、あまりBangPatterns拡張を使いすぎると、ソースコードがビックリまみれになってしまいます。

そこで、GHC 8.0で導入されたStrict拡張を使うと、束縛がデフォルトで正格になります（語弊あり）。

ただし、Strict拡張は万能の薬ではありません。例えば、

let (a,b) = (1, undefined)
in print a

はエラーになりません（b の束縛は正格にならない）し、

foldl' (\(a,b) x -> (a+x,b+1)) (0,0) [1..1000000]

というコードは従来通りスペースリークします。あと、whereのような宣言的なスタイルとStrict拡張は相性が悪い気がします。例えば、次のコードは意図通りに動きません：

maybeDiv :: Int -> Int -> Maybe Int
maybeDiv a b | b == 0 = Nothing
             | otherwise = Just q
  where q = a `div` b

個人的には、Strict拡張よりは、地道にBangPatternsや seq, $! を使っていく方が好みです。Strict拡張に十分習熟すれば意見が変わるかもしれませんが、年単位の時間がかかる気がします。

Strict拡張はともかく、StrictData拡張はめっちゃわかりやすくて有益だと思います。

TypeApplications

read系関数を使うと型が曖昧になったり、意図しないdefaultingが起こりがちです。read系関数で型を明示する標準的な方法は

main = do
  n <- readLn :: IO Int
  xs <- map ((read :: String -> Double) . BS.unpack) . BS.words <$> BS.getLine
  ...

かと思いますが、型注釈が冗長です。GHC 8.0で導入されたTypeApplications拡張を使えば、

{-# LANGUAGE TypeApplications #-}
main = do
  n <- readLn @Int
  xs <- map (read @Double . BS.unpack) . BS.words <$> BS.getLine
  ...

と書けるようになります。

なお、古いGHCで型を明示する場合、パターンの部分に型注釈を書くという手があります。パターンの部分に型注釈を書くには、ScopedTypeVariables拡張が必要となります。

{-# LANGUAGE ScopedTypeVariables #-}
main = do
  n :: Int <- readLn
  xs :: [Double] <- map (read . BS.unpack) . BS.words <$> BS.getLine
  ...

GHC拡張を使わない方法としては、

readLnInt :: IO Int
readLnInt = readLn
readDouble :: String -> Double
readDouble = read

とあらかじめ定義しておく（これらの関数はコピペで使いまわせる）か、

main = do
  n <- readLn
  let _ = n :: Int
  xs <- map (read . BS.unpack) . BS.words <$> BS.getLine
  let _ = xs :: [Double]
  ...

という風にダミーの束縛を定義する方法が考えられます。

Semigroup-Monoid Proposal

現在のGHCでは Semigroup クラスおよび <> 演算子がPreludeからエクスポートされていますが、GHC 7.10ではそもそも Data.Semigroup すら存在しません。Semigroup が存在しないということは、自分で Monoid のインスタンスを定義する際にGHC 7.10とGHC 8.6で共通のコードを使えないということです。しんどい。

提出コードのシンタックスハイライトがおかしい件（識別子中のプライムが文字列扱いされている）

この問題は「Haskellのシンタックスハイライトがおかしい」と捉えてしまうと正解にたどり着けません。他の言語でもシンタックスハイライトが不正確であることに気づけるかがポイントです。

例えば、他のML系言語（OCamlやSML）でも識別子中にプライムを使えますが、これらのプライムも文字列扱いされています。

そして、よく見るとC++のようなメジャーな言語でも、微妙に不正確なハイライト表示が行われています。例えば、C++では string はキーワードではないのにキーワード扱いされています。

この辺の問題は原因を特定した上で @chokudai 氏に報告済みなので、そのうち直るのではないかと思います。

次の目標

これまでは「とりあえず水色になる」を目標にしていたので、次の目標を考えなくてはなりません。際限なく上を目指せるわけではないのはわかっていますが、とりあえず今は「青色になる」を目標にします。

これまでは既存の知識+αでどうにかなっていましたが、そろそろ本などを読んでアルゴリズム・データ構造を真面目に勉強する必要がありそうです（ばくぜんとした感想）。特に、グラフ系のアルゴリズムが弱い気がしているので、なんとかしたいところです。

このエントリーをはてなブックマークに追加

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です