競プロ AOJ Haskell

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

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

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

Haskell完全初心者向けにHaskellを理論ではなく実際にAizu Online Judgeの問題を解きながら体で覚えようというHaskell入門シリーズの第2弾です。

前回までの内容はこちら。

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

目次

ITP1_3_A - 複数の Hello World の出力

問題

1000個のHello Worldを出力する問題です。

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

解答

1
main = mapM_ putStrLn $ replicate 1000 "Hello World"

手続き言語だと繰り返しにあたるものは、関数型で書くと本当に楽しいですね。
replicateは同じ要素を複数もつリストを生成する関数です。

mapM_についてはまだ完全に理解していませんが、mainの型IO aの条件を満たすものを返しているのは確かです。
リストを処理していますが、返り値は必ずIO ()になっています。
Mとついているだけあって、IOだけでなく汎用的なモナドに対応しているのかもしれませんね。
これがただのmapだと[()]を返すのでコンパイルエラーです。
mapMというのもあり、これは結果を保持していて引数と同じサイズのリストで型はIO [()]です。
mainの型には合っているのでこちらもコンパイルは通ります。

ITP1_3_B - テストケースの出力

問題

長さの決まっていない入力を読み込む練習問題です。
終了条件が事前に決まっていない読み込みはHaskellでどのように実装するか気になっていたので興味深かったです。

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

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
main = readAndDo showCase isEnd 1

readAndDo fn fin depth = do
  line <- getLine
  if fin line then return ()
  else do
    fn (show depth) line
    readAndDo fn fin $ depth + 1

-- 終了判定関数
isEnd line = line == "0"

-- 毎行実行する関数
showCase s1 s2 = do
  putStrLn $ "Case " ++ s1 ++ ": " ++ s2

再帰的に入力を読み込む関数readAndDoを定義しました。
もし0であれば何もせず終了し、それ以外の場合には指定の文字列を出力してもう一度readAndDoを実行します。
「何もしない」というのをどう表現したらよいか迷いましたが、IOモナドの何もしないバージョンはreturn ()とのことでした。

ITP1_3_C - 2 つの数の交換

問題

可変の複数行に渡って2つの整数が与えられるので、それぞれを小さい順に出力していく問題です。

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

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
main = readAndDo

readAndDo = do
  line <- getLine
  if line == "0 0" then return ()
  else do
    let [a, b] = map (read :: String -> Int) $ words line
    let s | a <= b = fmt [a, b]
          | otherwise = fmt [b, a]
    putStrLn s
    readAndDo
    where fmt = unwords . map show

可変行数の入力については前回見たとおりです。
特に新しいものはありませんが、関数合成.の使い方が分かってきました。

以下2つのポイントを守ればコンパイルが通るようです。

  1. 引数と返り値は1つずつの関数のみ。
  2. 前の関数の返り値と次の関数の引数の型を一致させる。

今回は最後の行fmt = unwords . map showで関数合成を使っています。
map showはこれで1つの関数で、リスト型[a]を受け取って要素を文字列に変換して[String]を返します。
unwordsは文字列リスト型[String]を受け取って文字列Stringを返します。
[a][String]Stringと型が一致していることが分かります。

mapは本来は引数を2つ取る関数(第一引数が関数、第二引数がリスト[a])ですが、それではポイント1に反するため関数合成が出来ません。
そこで引数の部分適用というテクニックを使って、第一引数の関数に予め関数showを適用して、残り1つだけ引数をとる関数map showという新しい関数を作っています。

関数合成と引数の部分適用は見た目が似ているので混同しないように注意が必要です。
関数合成の場合は2つの関数の入出力は一致しており、実行の前後関係があるだけで対等な(兄弟)関係です。
一方で、引数の部分適用は入出力が一致している必要がありません。
1つの関数(show)がもう一方の関数(map)の引数になるので対等ではなく呼ぶ側と呼ばれる側という(親子)関係です。
呼ばれる側(子)は呼ぶ側(親)が求める型である必要があります。

ITP1_3_D - 約数の数

問題

整数の範囲が与えられてその中にある数の約数がいくつ含まれるかを答える問題です。
関数型で解くと楽しい問題です。

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

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
main = getLine >>= print . solve . input

-- 入力
input :: String -> [Int]
input = map read . words

-- 解答
solve [a, b, c] = count [a..b]
  where
    count = length . filter ok
    ok x = c `mod` x == 0
solve xs = -1

main関数を入力inputと解答solveに分けて分かりやすくしてみました。
getLine >>=inputに含める方法は分かりませんでした・・・。

新しく出てきた関数が2つと文法が1つあります。
1つ目は、超重要なfilterです。
条件となる関数とリストを渡して条件にマッチする要素だけをフィルタしたリストを返します。
ここでは条件の関数にokという名前を付けましたので、前回見たように部分適用テクニックを使ってfilter okという新しい関数を作っています。
これはcの約数のみをフィルタする関数です。

2つ目は、length関数でこれはリストの要素数を返します。
この2つを関数合成してcount関数を作っています。
これはcの約数のみをフィルタしてカウントします。

最後に[5..10]という文法は、[5, 6, 7, 8, 9, 10]というリストを生成します。