競プロ AOJ Haskell

オンラインジャッジを使って体で覚えるHaskell入門 パート1

Haskell完全初心者向けにHaskellを理論ではなく実際にAizu Online Judgeの問題を解きながら体で覚えようというHaskell入門シリーズの第1弾です
Feb. 7, 2020, 1:49 a.m.

目次

この記事の対象読者と目的

この記事は、Haskell完全初心者向けにHaskellを理論ではなく実際にAizu Online Judgeの問題を解きながら体で覚えようというHaskell入門シリーズの第1弾です。
(私自身が今Haskell初心者です。)

新しい言語を学ぶ時に競技プログラミングのジャッジシステムを利用するのは良い方法です。
なぜなら入出力が明確で、正解やエラーがひと目で分かるのでゲーム感覚で進められるからです。
分からない場合は他の人が提出した回答を見ることが出来、AC(正解)のものであればそれが確実に正しく動くコードだということが保証されています。

今回対象とする問題

今回はHaskellをほとんど知らないことを前提に、Aizu Online Judgeのプログラミング入門コースを1から順番に解いていきます。
最初の問題はHelloWorldから始まるので初心者に優しく作られています。

Aizu Online Judgeを使ったことの無い方は、これを機会にぜひ登録してみて下さい。
新バージョンは正解時が結構気持ちいいアニメーションになっています。

問題と解答

ITP1_1_A - Hello World

問題

Hello Worldと改行を出力する問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A

解答

Haskellで改行付きの標準出力はputStrLnを使うそうです。

1
main = putStrLn "Hello World"

ITP1_1_B - x の 3 乗

問題

整数が1つ与えられて、その3乗を出力する問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_1_B

解答

doというキーワードが新しく登場。
先程なかったのに今回登場したのは、2行になったのと関係していそうですが、とりあえず今は深追いしません。

次に、整数の入力は型を書かずに推測させると1.0と小数になってしまったため、型を指定する方法を調べて追加しました。
IO Intは入出力を伴う整数という意味らしいです。

最後にprintで出力していますが、これは引数を文字列表現に変換してそれを標準出力する関数です。
先にxを3乗したいので、$で優先順位を変えて3乗してからprintしています。

1
2
3
main = do
  x <- readLn :: IO Int
  print $ x * x * x

ところでdoは調べてみるとモナド(モナドが何かは深く考えません)を結合するための簡易構文(シンタックスシュガー)らしいです。
なので、1行目と2行目を違う方法で結合できればdoが不要になるだとうと考えて試してみました。

以下でもAC(正解)となりました。

1
main = readLn >>= print . solve where solve x = x * x * x

演算子>>=はモナド同士を左→右の順に結合します。
.は関数合成かなと思っています。
先程と逆で右から左に実行されます。
なので全体としては、readLnsolveprint の順に実行されます。
whereというのは実行のコンテクストだと思います。
where以下に定義しておけば本文中で使える脚注のようなイメージです。
本当は、print . (x -> x * x * x)whereを使わずに短く書きたかったのですがコンパイルエラーでした。
なので仕方なく一時的にsolveという名前をつけています。

ITP1_1_C - 長方形の面積と周の長さ

問題

長方形の縦と横の長さが2つの整数として与えられます。
その面積と周の長さを答える問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_1_C

解答

getLineは1行を丸々取得してlineに格納します。
letwhereと同じようにコンテクストを提供する道具ですが、whereと違ってこちらは事前に書きます。
定義したものはこの後使用できます。

mapというのは有名な関数で、関数を受け取ってそれを次に受け取るリストの各要素に適用するという関数です。
readは文字列を1つ受け取って、それを適切な型に変換する関数です。
例えば、"12"を整数12に変換します。

map readは、上の2つを組み合わせた新たな関数です。
次に受け取る文字列のリストの各要素を適切な型に変換して新たなリストを作る関数です。
$は先に見たように、引数が間違った関数に渡されないようにする区切りです。
words lineは1つの空白区切りの文字列を文字列のリストに変換します。
[a, b] は「パターンマッチ」という文法の1つで、aにリストの第一要素、bにリストの第二要素が代入されます。
今回は入力が2つの整数と分かっているので必ずマッチします。

出力部分ではスペース区切りで1行に2つの整数を出力するのですが、printを使うと改行されてしまうので改行が無いputStrを使用しています。

面積と周の長さを計算する関数にはそれぞれfgという名前を付けています。
これらは2つの引数を受け取る関数です。

1
2
3
4
5
6
7
8
9
main = do
  line <- getLine
  let [a, b] = map read $ words line
  putStr $ show $ f a b
  putStr " "
  print $ g a b
  where
    f x y = x * y
    g x y = (x * 2) + (y * 2)

ITP1_1_D - 時計

問題

秒が与えられてそれを時:分:秒のフォーマットに直して出力する問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_1_D

解答

新しい関数としてmod div が出てきましたがこれらは他の言語でもおなじみの剰余算と除算です。
新しい演算子++はリスト同士を連結するもので、文字列もリストなので連結可能です。

余談ですが、関数の引数部分に関数実行が含まれる場合に、(div totalSec 60)のようにカッコが出てしまうのが読みづらいですね。
最後の引数であれば、$ div totalSec 60と書いて可読性があがります。
何かいい方法は無いものでしょうかね。
今は深追いしません。

1
2
3
4
5
6
7
8
9
main = do
  line <- getLine
  let totalSec = read line :: Int
  let sec = mod totalSec 60
  let min = mod (div totalSec 60) 60
  let hr = div totalSec 3600
  putStrLn $ fmt hr min sec
  where
    fmt hr min sec = (show hr) ++ ":" ++ (show min) ++ ":" ++ (show sec)

ITP1_2_A - 大小関係

問題

2つの整数の大小関係を答える問題です。
ガード節が使えるので楽しいです。

https://onlinejudge.u-aizu.ac.jp/solutions/problem/ITP1_2_A

解答

3行目の2つの変数を読み込むところは前回までに見たとおりです。
ただ、readの型をString -> Int)と明示しないと後半のa == bのところでコンパイルエラーになってしまい原因は分かりませんでした。

sの代入にはガード節というものを使っています。
これは条件に応じて、異なる値を1つの変数に代入(束縛)するというものです。
変数名 | 条件 = 条件がTrueの場合の値 という構造が条件の数だけ並んでいます。

1
2
3
4
5
6
7
main = do
  s <- getLine
  let [a, b] = map (read :: String -> Int) $ words s
  let s | a < b = "a < b"
        | a > b = "a > b"
        | a == b = "a == b"
  putStrLn s

ITP1_2_B - 範囲

問題

3つの整数が与えられて真ん中の整数が左右の範囲に収まっているかを答える問題です(a < b < c)。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_2_B

解答

ガード節ですべての条件にマッチするワイルドカード(デフォルト値)はotherwiseで表せます。

1
2
3
4
5
6
main = do
  s <- getLine
  let [a, b, c] = map (read :: String -> Int) $ words s
  let s | a < b && b < c = "Yes"
        | otherwise = "No"
  putStrLn s

ITP1_2_C -

問題

3つの整数を小さい順にソートし出力する問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_2_C

解答

整数は3つと少ないので全組み合わせを列挙しています。
unwordsは文字列のリストを受け取り、空白でつなげた1つの文字列を返す関数です。
文字列という型にマッチさせるためにshowで変換しています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
main = do
  input <- getLine
  let [a, b, c] = map (read :: String -> Int) $ words input
  let sorted | a <= b && b <= c = [a, b, c]
             | b <= a && a <= c = [b, a, c]
             | b <= c && c <= a = [b, c, a]
             | c <= b && b <= a = [c, b, a]
             | a <= c && c <= b = [a, c, b]
             | c <= a && a <= b = [c, a, b]
  putStrLn $ unwords $ map show sorted

Data.Listというライブラリにsort関数があるそうです。
Intのリストを渡すだけでソートしてくれます。

ついでに、doを使わずに>>=と関数合成で書き直してみました。
方向は右から左ですが、かなり直感的に書けるのですごく気持ちいいです。
入力がIntであることがどこかで推測出来ればコンパイル出来そうなのでshowのところに書いてみました。

1
2
import Data.List
main = getLine >>= putStrLn . unwords . map (show :: Int -> String) . sort . map read . words

ITP1_2_D - 長方形と円

問題

長方形と円が与えられて、円が長方形の内部に完全に収まるかを答える問題です。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_2_D

解答

条件を愚直に実装してみました。
最後の1行はインプットが5つの整数のフォーマット出なかった時にマッチし、実行されます。
(競プロではインプットの形式は決まっているので不要ですね。)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
main = getLine >>= putStrLn . solve . map (read :: String -> Int) . words

solve [w, h ,x, y, r]
  | 0 <= bottom && 0 <= left && top <= h && right <= w = "Yes"
  | otherwise = "No"
  where
    bottom = y - r
    top = y + r
    left = x - r
    right = x + r
solve xs = "Error parsing input"