「アルゴ式」をHaskellで学ぶための準備

この記事は、CAMPHOR- Advent Calendar 2021 の7日目の記事です。

---

「アルゴ式」というプログラミングを学んで実践できる非常に良質なWebサービスがあります。

アルゴリズムについて解説された教科書だけでなく、実際にプログラミングを書いて提出してオンラインでジャッジしてくれるシステムを備えた練習問題も用意されているのが特徴です。さらにこのオンラインジャッジシステムは多くのプログラミング言語に対応しており、その中にはHaskellも含まれています。

今回はこのアルゴ式を読むにあたって練習問題をHaskellで解くために必要になりそうな知識についてまとめました。アルゴ式は現在ベータ版なので将来的な変更で変わってしまうものもあるかもしれませんが、2021年12月現在の練習問題を全てHaskellで解いた上で必要になったものをまとめているので参考にしていただけると幸いです。

Haskellで競技プログラミングに取り組むためのノウハウをまとめた記事は既にたくさん存在するので、この記事ではアルゴ式の練習問題に取り組むにあたって特に考える必要があったことについて簡単にまとめることにします。アルゴ式はあくまで教育がメインで作られたサービスなので競技プログラミングに比べると実行速度などに関して求められる基準は優しい印象です（とはいえ雑なコードを書くとすぐにTLEになってしまうので教科書の内容はしっかり学ぶ必要があります）。競技プログラミング向けの知識が気になる人は以下の記事を参考にしてみてください。

• Haskellで解くAtCoder - The curse of λ
• AtCoder に登録したら解くべき精選過去問 10 問を Haskell で解いてみた - Qiita
• HaskellでAtCoderに参戦して水色になった | 雑記帳

また、書籍にはなりますが「Haskellで戦う競技プログラミング」も内容が豊富で分かりやすく書かれておりオススメです。

• Haskellで戦う競技プログラミング

入力を受け取る

まずは標準入力からデータを受け取る方法についてです。

速度を気にするならStringではなくByteStringを使うべきですが、最初からHaskellの知識で躓いても本末転倒なので慣れない内はStringで処理してしまって問題ないでしょう（実際ほとんどの問題はStringで十分です）。

以下に標準入力からからデータを読み取る頻出パターンを列挙します。関数をパッと見て挙動が分からない場合は各関数へのリンクを下に貼っていますのでHaddockを読み込んで慣れておきましょう。

main = do
  -- | 標準入力から一行読み込む
  -- | 型は省略可
  s <- getLine :: IO String

  -- | 標準入力から一行読み込みInt型の値に変換する
  -- | read <$> getLine とほぼ同じ
  -- | Integer や Double として読み込みたい時は後ろの型を変える
  -- | 型は省略しない方が無難
  n <- readLn :: IO Int

  -- | 標準入力から一行読み込み、空白区切りで文字列のリストに変換する
  xs <- words <$> getLine :: IO [String]

  -- | 標準入力から一行読み込み、空白区切りでInt型の値のリストに変換する
  ns <- map read . words <$> getLine :: IO [Int]

  -- | 標準入力から一行読み込み、空白区切りでInt型の値を取り出す
  -- | 1行あたりで与えられるパラメータの数が予め分かっているときに便利
  [n, m] <- map read . words <$> getLine :: IO [Int]

  -- | 標準入力からn行読み込み、文字列のリストとして返す
  xs <- replicateM n getLine :: IO [String]

  -- | 標準入力からn行読み込み、Int型の値のリストとして返す
  ns <- replicateM n readLn :: IO [Int]

  -- | 標準入力からn行読み込み、各行を空白区切りでInt型の値のリストに変換したリストを返す
  nss <- replicateM n (map read . words <$> getLine) :: IO [[Int]]

登場した関数を眺めてみるとほとんどPreludeで定義されていることが分かります。

• getLine
• readLn
• words
• <$>
• read
• map
• replicateM

Haskellは豊富な関数・コンビネータが提供されているので簡単なアルゴリズムであれば標準ライブラリで提供されている関数を適切に組み合わせることで一瞬で作れてしまうことがよくあります。上記の関数に自信のない人は、まずは腰を据えてPreludeのHaddockからじっくり読んで見ることもオススメです。

replicateMはControl.Monadで提供されている関数なので使用するためには先にモジュールをimportする必要があります。

import Control.Monad

毎回 import を書くのは面倒ですが、アルゴ式はマイページからコードテンプレートを編集することが可能なのでそこに追加しておくのがオススメです。

例として「グラフアルゴリズム - Q1-2. フォロー」の入力を受け取る処理は例えば以下のように記述することができます。

main = do
  [n, m] <- map read . words <$> getLine :: IO [Int]
  abs <- replicateM m (map read . words <$> getLine) :: IO [[Int]]

出力のパターン

答えの出力に関しても覚えておくと便利なパターンがいくつかあります

main = do
  -- | 文字列型の値を出力する
  putStrLn (xs :: String)

  -- | Int, Integer, Double 等の方の値を出力する
  -- | String も出力できるがダブルクオーテーションがついてしまうので
  -- | String を出力する際は putStrLn を使う
  print (n :: Int)

  -- | リストの値を先頭から順番に一行ずつ出力する
  -- | 文字列のリストを出力する際は print を putStrLn　に置き換える
  mapM_ print (ns :: [Int])

  -- | リストの値を空白区切りで一行で出力する
  putStrLn . unwords . map show $ (ns :: [Int])

• putStrLn
• print
• mapM_
• unwords

Note: エディターについて

追記 2021/12/11
こちらの内容を改めて確認したところエラーが再現しなくなっていたので改善された模様です。運営に感謝🙏

現在のアルゴ式のエディターでHaskellを書く場合、気をつけないといけないことが一つあります。それは改行時に自動でインデントが挿入される際にタブ文字が使われることがあるとういことです。インデントの中にタブ文字と空白文字が混在すると

Main.hs:15:1: warning: [-Wtabs]
  Tab character found here.
  Please use spaces instead.

というようなwarningが出て正常に実行されないので、こちらのエラーが発生したらインデントのタブ文字を探して削除し空白文字に置き換えてください。

全探索

基本的にはリストをうまく使いこなせるかを問われる問題が多いです。自信がない人はまずはData.ListのHaddockをじっくり読むことをオススメします。

少し捻りのある関数として「配列に含まれる要素の個数を種類ごとにカウントする」というようなものがあるでしょう。リストだけでこのような処理を行う場合、

group . sort :: (Eq a, Ord a) => [a] -> [[a]]

• group
• sort

と組み合わせることで実装できます。これで同じ要素がまとめられたグループのリストが手に入るので、個数をカウントしたければ length を使って調べることができます。

上記のコードは$O(n\log n)$の計算オーダーで動きますが、配列を使えば$O(n)$で処理することができます。本音を言えば配列としてvectorパッケージを使いたいところですが^[1]アルゴ式では現時点でvectorを使うことができず、代わりにarrayパッケージを使うことができるのでそちらを使いましょう。上記の問題を解く関数は直接提供されているわけではありませんがData.ArrayのHaddockにそのままの関数の実装方法が記載されています。

hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]

Arrayの使い方

arrayパッケージの基本的な使い方について見ておきましょう。まず提供されている型でよく使うものを以下に挙げます。

型	種類	説明	提供モジュール
Array	Immutable	最も基本的な配列の型。一度配列を構築した後は値の更新はできない（//で特定の要素が違う新しい配列を作ることはできる）。	Data.Array
UArray	Immutable	Array i eと基本的には同じだが要素のボックス化を行わないので高速に動作する。ただし要素の型として使えるものに制限がある。使える時はこっちを使う	Data.Array.Unboxed
IOArray	Mutable	IOを伴うが配列の要素を後から書き換えることができる配列。要素をスワップしたり頻繁に値を書き換える処理の場合はこっちを使う。ST版もある	Data.Array.IO
IOUArray	Mutable	IOArrayの要素のボックス化を行わないバージョン。高速に動作するので使える時はこっちを使う	Data.Array.IO

Immutable Array

ランダムアクセスが頻繁に発生するアルゴリズムではリストを最初に Immutable Array に変換して使い回すと良いでしょう（添字アクセスに関する計算オーダーはリストは$O(n)$で配列は$O(1)$）。Immutable Array を構築する方法には以下の2つがあります。

-- | 添字の範囲 (i, i) と要素のリスト [e] を使って配列を構築する
listArray :: Ix i => (i, i) -> [e] -> Array i e

-- | 添字の範囲 (i, i) と添字付けられた要素のリスト [(i, a)] を使って配列を構築する
-- | 同じ添字で要素が重複した時の更新処理 (e -> a -> e) とデフォルト値 e を指定するので
-- | 添字付けられた要素のリストは同じ添字の要素が重複していても、特定の添字の要素が欠落していても問題ない
accumArray :: Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e

• listArray
• accumArray

構築した配列の要素には (!) を使ってアクセスすることができます。

> as ! 1
123

• (!)

Mutable Array

頻繁に要素を更新する必要があるアルゴリズムの場合は Mutable Array を使うのが良いでしょう。

-- | 添字の範囲 (i, i) とデフォルト値 e を取って全ての要素が同じ値の配列を作成する
newArray :: (MArray a e m, Ix i) => (i, i) -> e -> m (a i e)

-- | 添字の範囲 (i, i) のみから未初期化の配列を作成する
newArray_ :: (MArray a e m, Ix i) => (i, i) -> m (a i e)

-- | 添字の範囲 (i, i) とリストから対応する配列を作成する
newListArray :: (MArray a e m, Ix i) => (i, i) -> [e] -> m (a i e)

• newArray
• newArray_
• newListArray

要素の読み書きには以下の関数を用います。

-- | 配列 a i e と添字 i を取って要素 e を返す（ただし返り値は m に包まれる）
readArray :: (MArray a e m, Ix i) => a i e -> i -> m e

-- | 配列 a i e の添字 i の要素を e に更新する
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()

• readArray
• writeArray

さらに以下の2つの関数はライブラリでは提供されませんが、定義しておくと便利です。

-- | 配列の特定の添字の要素の値を与えられた関数で更新する
modifyArray :: (MArray a e m, Ix i) => a i e -> i -> (e -> e) -> m ()
modifyArray a i f = do
  ai <- readArray a i
  writeArray a i (f ai)

-- | 配列の2つの添字の要素を交換する
swapArray :: (MArray a e m, Ix i) => a i e -> i -> i -> m ()
swapArray a i j = do
  ai <- readArray a i
  aj <- readArray a j
  writeArray a i aj
  writeArray a j ai

ビット演算（bit演算）

Data.Bitsの基本的な使い方を理解しておくと良いでしょう。特にHaskellではビット演算がBitsという型クラスのメソッドとして定義されているので、いちいちバイナリへの変換等を行わなくても例えばInt型のままビット演算を行うことができるのでコードの記述量も少なくなります。

正規表現

残念ながら現在のアルゴ式ではHaskellで正規表現を扱うためのライブラリに対応してないようなので出題者の意図通りに練習問題を解くことができません。

それでも解きたいという場合選択肢としては以下の2つがあるでしょう。

1. 関数をフル活用して強引に解く
2. パーサーを自前で実装して解く

2の選択肢は一見困難に見えますが、実はアルゴ式ではmtlライブラリを使うことができるので、驚くほど簡単に実装することができます。

type Parser a = StateT String [] a

こちらで大体完成です。

StateTはControl.Monad.Stateで定義されているStateモナドのモナドトランスフォーマーです。

追記 2021/12/07
自分でパーサーコンビネータを実装しなくてもbaseパッケージにあるText.ParserCombinators.ReadPを使えばほぼ同等のことができてしまうとコメントで教えていただきました。感謝🙏

パーサーを組み立てる上で基本的な構成要素となる関数をいくつか用意します。

item :: Parser Char
item = do
  xs <- get
  case xs of
    ""     -> lift []
    (x:xs) -> put xs >> pure x

itemは現在パースしている文字列の先頭の文字を取り出すコンビネータです。

char :: Char -> Parser Char
char c = do
  x <- item
  if x == c
    then pure c
    else lift []

char は item によって取り出した文字が想定していた文字と一致しているかを判定するコンビネータです。例えば char 'a' >> char 'b' >> char 'c' は文字列 "abc" と一致しているかを試していることになります。文字列の各文字に対していちいちこのように記述するのは大変なので、もう一つ便利なコンビネータを定義しておきましょう。

string :: String -> Parser String
string "" = pure ""
string (x:xs) = char x >> string xs

もうお気づきかもしれませんが、我々は文字を取り出す・判定するという関数を作っただけで残りの一文字ずつ処理する（>>）ような関数はモナドの標準的な関数を利用しています。このようにStateT Strint [] aに対して抽象的に機能する関数を活用すればパーサーを構築するのに必要な残りの関数はほとんど定義する必要はありません。

例えば /abc*d/ という正規表現に対応するパーサーは以下のように実装することができます。

parser = do
  string "ab"
  many $ char 'c'
  char 'd'

ここで出てきた many は型クラス Alternative のメソッドで標準ライブラリから提供されているものです。他にも標準ライブラリから提供されておりパーサーで便利に使える関数として以下のようなものがあります。

• many - コンビネータに0回以上マッチするか判定する
• some - コンビネータに1回以上マッチするか判定する
• <|> - 2つのコンビネータのいずれかがマッチするか判定する
• msum - 複数のコンビネータのいずれかがマッチするか判定する
• replicateM - コンビネータにn回マッチするか判定する

例えば /(a|b){1,4}/ という正規表現に対応するパーサーは以下のように書くことができるでしょう。

parser = msum $ map (\n -> replicateM n (char 'a' <|> char 'b')) [1..4]

最後に組み立てたパーサーに文字列が適合するか判定する関数を用意しておきます。

validate :: Parser a -> String -> Bool
validate parser xs =
  case find null (execStateT parser xs) of
    Nothing  -> False
    (Just _) -> True

パースが正常に終了していれば与えられた文字列は全て消費されているはずなのでnullであるものを探しています。反対にどこかでパースに失敗していれば lift [] によって状態が空リストになっているはずなのでfindが失敗するという運びになっています。

パーサーコンビネータの詳しい動作原理が気になった人は以下の文献を一読するのをオススメします。英語ですが内容は分かりやすく書かれているので読みやすいです。

• Monadic Parser Combinators

最後に、「正規表現 4-4 typical_snake_case」では日本語を含む文字列を扱う必要があるのですが、現在のアルゴ式では標準入力から日本語の入った文字列をgetLineで読み込むと invalid byte sequence と言われて失敗してしまいます。これに対処するためにはByteStringのgetLineを使って読み込めば大丈夫です。読み込んだ文字列をStringに変換することはできませんが、この練習問題はByteStringが提供する関数を使って簡単に解くことができるでしょう。

動的計画法

基本的には計算結果を保存する中間的なデータ構造を引き回す再帰関数を書くことで解くことができます。再帰関数をいちいち書くのが面倒臭良い時は flip fix を使ってループ処理を書いてしまうのも良いでしょう。

また繰り返しの処理を書くにあたって map や foldl などを使う場面も増えると思います。これらの関数は処理を行う関数が第一引数に来るので関数が大きくなると書くのが大変です。かといって処理を行う関数にいちいち別名をつけるのも大変なので、処理を行う関数が大きくなる場合は以下のように記述することで一番外側に関数を書くことができて視認性も良くなります。

flip map ns $ \i -> ...
(\f -> foldl f e xs) $ \e x -> ...

関数が複雑になると細かい境界条件の違いなどでデバッグすることも増えてくるでしょう。純粋な関数の処理の途中で変数の値を確認したい時はDebug.Traceの関数を使うのが定石です。traceShowを使えば純粋な関数の中でも簡単に変数の中身を確認することができます。アルゴ式の場合 traceShow で出力された値は「エラーログ」の中に表示されます。ただし traceShow は式が評価されないと出力されないので、遅延評価で評価されない場所に書いてしまうと表示が出てこない時もあるので注意が必要です。

動的計画法の基本は計算結果を保存して使い回すことです。単純な再帰関数で計算結果の値を持ち回すのが大変になってきたと感じたらStateモナドを使うのも一つの手でしょう。あとメモ化といえば以下のパターンを覚えておくのも役に立つかもしれません。

fibs :: [Int]
fibs = map fib [0..]

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fibs!!(n-1) + fibs!!(n-2)

フィボナッチ数列は再帰計算の中で同じnに対するf nの値を何回も参照しますが、一度計算された値はfibsのリストの要素として記録されているので再計算されることはないという仕組みです。

ソートアルゴリズム

ソートアルゴリズムは要素の交換を要求されることが多いので基本的には IOUArray i e を使って解くのが簡単です。

一つ注意点があるとすれば現在のアルゴ式ではrandomパッケージを使うことができないので、「ソートアルゴリズム - Q1-5. 乱択クイックソート」において乱数を使うところで詰んでしまいます。現時点では線形合同法などの簡単な疑似乱数生成を実装するなど何らかの工夫を行う必要があります。

次のコンテンツである「グラフアルゴリズム」も配列を適切に使うことで解くことができるでしょう。

整数論的アルゴリズム

• 素数判定
• 約数を求める関数
• 素因数を求める関数
• エラトステネスの篩

辺りの関数を速度を意識して実装しておけば、あとは数学の問題として解けるものが多いです。

入力される数字の桁数が大きくなることがあるので、そういう場合はIntではなく多倍長整数型であるIntegerを使って実装するのが良いでしょう。

設計技法とデータ構造

UnionFindをHaskellでどう実装するべきかという問題があります。単純な配列を使って

type UnionFind = IOUArray Int Int

と定義し、教科書の「Union-Findの実装」を参考に

rootUF :: UnionFind -> Int -> IO Int
rootUF uf i = ...

uniteUF :: UnionFind -> Int -> Int -> IO ()
uniteUF uf x y = ...

といった関数を実装すれば基本的には問題なく解けると思います。

おわりに

アルゴ式で情報科学を学びながらHaskellの書き方を同時に学ぶのは一石二鳥じゃないでしょうか！

もしHaskellの書き方で分からない所があれば、ぜひHaskell-jpのSlack（#beginners や #questions チャネル）で質問してみてください！Slackにまだ登録されていない方はこちらからお気軽にどうぞ！

次のCAMPHOR- Advent Calendar 2021の記事は、honaiさんです。お楽しみに！

---

＼読んでいただきありがとうございました！／
この記事が面白かったら いいね♡ をいただけると嬉しいです☺️
バッジを贈っていただければ次の記事を書くため励みになります🙌

脚注

1. vectorは扱える配列が添字がIntのものに限られますが提供されている関数が豊富で使い勝手がとても良いです。反対にarrayは添字として(Int, Int)やChar等、色々な型の値を使うことができますが提供されている関数が最低限のものしか無く自分で実装する手間がかかる印象です。大抵の課題では工夫すれば添字がIntでも問題ないので、Haskellで配列を使いたいと思った時はまず第一候補としてvectorを考えるのが良いでしょう。