アルゴ式 「標準入出力」の練習問題をHaskellで解いて、その復習
Haskellに興味を持ち、「始めてみよう！」と思い立ったものの、初学者が理解できるくらい易しく、かつ実践的で参考になるコードを見つけるのは簡単ではありません。特に初心者が直感的に学べるお手本となるコードの例が不足しているように感じます。
そこで、初学者向けのプログラミング問題と解説を提供している「アルゴ式」の問題を実際に解いたコードを紹介し、それをもとにHaskell的な解法の考え方を、自分の復習も兼ねて記録していきたいと思います。
これにより、初学者による、初学者のための、おしゃれなHaskellコード集がここに爆誕します！ぜひ一緒に楽しみながらHaskellを学んでいきましょう。
アルゴ式「標準入出力」について
アルゴ式の「コーディングによる問題解決」にある「ロジック実装初級」の「標準入出力」の中の各問題を解いたときの復習ノートを以前書きました。
今回は、その問題の最後にある「練習問題」の解答を実践していきたいと思います。
問題「中央の文字」
リストの要素を取り出す!!演算子
Haskellにおいて、文字列は文字のリストです。なので、文字列の任意番目の文字を取り出すには、任意番目のリストの要素を取り出すことになります。
Haskellのリストで任意番目の要素を取り出すのは!!演算子を使います。書式は次の通り。
リスト !! インデックス（０始まり）
具体例を見ると次のようになります。
ghci> [1,2,3,4] !! 0
1
ghci> [1,2,3,4] !! 1
2
文字列に対して適用すると次の通り
ghci> "abcd" !! 0
'a'
解答例
入力は５文字と決まっているので、取り出すインデックスは固定。
!!を使う場合は要素が文字になるので、表示の仕方に注意。
解答例１
main = do
s <- getLine
putStrLn [s !! 2]
リストを操作する:演算子
Haskellではデータをリストとして持つことが多いです。
そして、このリストを操作するもっとも基本的な処理がリストの先頭に要素を追加するという処理です。この時に利用される演算子が:演算子です。
:演算子の使い方の基本は次の通り。
追加する要素 : リスト
左側に追加する要素を置き、右側に追加されるリストを置きます。
具体的は使い方はは次の通りです。
ghci> 5 : [1,2,3]
[5,1,2,3]
ghci> 'x' : "abc"
"xabc"
ghci> 'x' : ['a','b','c']
"xabc"
この演算子を使い文字を空のリストに追加することで、文字を文字列に変換できます。
ghci> 'a' : []
"a"
そして、ユニットという構文で、演算子と一つの引数を固定することで、一つの引数をとる関数を作ることが出来ますし、更には、関数の形式にしてしまえば、関数合成することも出来ます。上手に$演算子も組み合わせましょう。
ghci> (:[]) 'a'
"a"
ghci> putStrLn . (:[]) $ 'a'
a
解答例２
main = do
s <- getLine
putStrLn . (:[]) $ s !! 2
問題「残り時間」
コード的には標準入力から数値として値をえる処理が出来れば解答できます。
解答例
数値が得られるのが分かっているので基本は数値として値を得てみましょう。
解答例１
main = do
s <- readLn :: IO Int
print $ 24 - s
実は、一気にreadLn関数を使わなくても、getLine関数を使って文字列として入力を受け取り、それをread関数で数値に変換することだって出来ます。その場合、一旦変数を解す場合、let式というものを使います。
main = do
s <- getLine
let n = read s :: Int
print n
一方、getLineのIO Stringの中身に関数を適用する<$>演算子を使うことも出来ます。
main = do
n <- read <$> getLine :: IO Int
-- 別の型注釈
-- s <- (read :: String -> Int) <$> getLine
print n
解答例２
main = do
n <- read <$> getLine :: IO Int
print $ 24 - n
問題「税込価格」
実際には問題の入力に制限があるため、整数の範囲で計算できますが、一般的な同じ様な税率を使った問題では実数の演算が必要な場合もあります。
解答例
問題の条件として入力が１０の倍数である点から税金は必ず整数として求まることを利用します。
解答例１
main = do
n <- readLn :: IO Int
print $ n + n `div` 10
一方、以下は、金額計算で率計算の後、答えを整数で求める一般的なものの考え方です。
少数部分を無くして整数で計算し、後で商を求めるパターン
一般に百分率程度の税率から金額を求めて１円未満を切り捨てるような場合、先に整数で掛け算してから、少数部分が合うように除算して商を求めれば１円未満の切り捨てになります。
main = do
n <- readLn :: IO Int
print $ n * 110 `div` 100
実数計算の後、整数にするパターン
実数として扱うならば、計算部分は実数で計算し、最終的にfloor関数を利用することで、少数点以下を切り捨てた整数の答えを得ることが出来ます。
main = do
n <- readLn :: IO Double
print . (floor :: Double -> Int) $ n * 1.1
-- 意味的には以下のコードが素直
-- print (floor $ n * 1.1 :: Int)
問題「一の位比較」
ある数字の１の位の数を求める問題は、数学的なアプローチと文字列的アプローチが考えられます。
数学的
10で割った余りが１の位の数になります。
ghci> 123 `mod` 10
3
文字列的
文字列として、最後尾の文字を取り出す例として次のような処理があります。
ghci> read . (:[]) . last . show $ 123 :: Int
3
但し、本文の場合、大小関係を比べるだけであり、文字でも大小関係が比べられるので数値まで変換する必要はありません。また、入力時に文字列として受け取っておけば、数値から文字列にする処理もいりません。
解答例
１０で割った余りを使う方法
解答例１
import Data.Bool
main = do
[a,b] <- map read . words <$> getLine :: IO [Int]
print . bool a b $ a `mod` 10 > b `mod` 10
文字列の最後を取る方法
データを取り込む際に、数値に変換しないようにします。
bool関数での３つめの引数となるbool計算では、文字そのものの大小で求められます。
解答例２
import Data.Bool
main = do
[a,b] <- words <$> getLine
putStrLn . bool a b $ last a > last b
問題「N 番目の文字」
文字列は文字のリストであるので、!!演算子を利用して解きます。インデックスは０から始まることに注意しましょう。また、文字を文字列にするのも[]を使って１文字のリストを作ればOKです。
解答例
解答例
main = do
s <- getLine
n <- readLn
putStrLn [s !! (n-1)]
問題「4 つの最大」
リストの要素から最大のものを見つけてくれるmaximum関数を利用すると簡単に解くことが出来ます。
foldlで畳み込め！
複数の要素（リスト）を順に処理して一つの答えを求める演算を畳み込みと言います。他の言語では、ループ処理を使って処理するようなことを、Haskellではこの畳み込みを使って処理することを得意としています。そして、本文のように、「４つの値から最大の値を求める」という問題は、まさに畳み込みのためのような問題になります。
畳み込みにはfoldl関数を利用しますが、まずは、実際のコードを見ましょう。
ghci> foldl max 0 [31, 41, 59, 26]
59
foldl関数は、３つの引数を取り、それぞれ以下のようになっています。
- ２つの引数をとる関数
- 初期値
- リスト
以上がfoldl関数の形になります。
foldlとアキュミュレーターacc
畳み込みの処理には、まず、アキュミュレーターというものが登場するということを覚えましょう。アキュミュレーターは計算の途中経過を保存しておく入れ物で、accという略字で示されることが多いです。
ここで、本問の処理を考えてみましょう。[31, 41, 59, 26]の中の最大値を探します。大小関係を調べるための関数としてmax関数を利用します。最大値の初期値として、与えられる可能性のある数字より小さい０を準備しておきます。ここから、リストの要素を順に調べていきます。
１番始めにmax関数で初期値の0とリストの初めの要素31を比べて、大きい方である31という結果を得ます。次に、max関数でそれまでの結果31とリストの次の要素41を比べて、大きい方である41という結果を得ます。更に、max関数でそれまでの結果41とリストの次の要素59を比べて、、、と続き、最終的にそれまでの結果がこの処理の結果となります。
さて、ここで、それまでの結果を保持してくれるのがaccなのです。そして、このacc自体は、foldl関数を利用する場合に、式の中には具体的に現れません。畳み込みという処理の中で自動的に行われているのです。
畳み込みの考え方
畳み込みの主な登場人物をもう一度確認します。
1.処理すべきリスト
2.引数を２つ取る関数
このうち、引数を２つ取る関数に着目しましょう。この関数は１つ目の引数にアキュミュレーターを取り、２つ目の引数に処理すべきリストの要素を一つとります。そして、畳み込みの処理では、アキュミュレーターの値として、初期値、若しくは、その前にこの関数を実行した結果を自動的に入れて、この処理を繰り返してくれるのです。
つまり、畳み込みを実現するfoldl関数は、この関数部分を自分で好きなものに入れ替えるだけで、途中経過を記録しながらリストを順次処理して最終的な結果を得ることが出来るのです。
ですから、例えば、上記のように関数の部分にmax関数を使えば、結果として一番大きな数が得られます。また、他の畳み込み処理の典型例としては、リストの要素の総和を求める場合、関数の部分に(+)を用いることで実現できます。
ここで比較のために、Pythonでリストの総和を求める一般的な処理をみてみましょう。Python等、一般的に処理すればループと計算結果を保持するための変数を使って以下のようになります。
#Python的コード
total_sum = 0
numbers = [1,2,3]
for num in numbers:
total_sum += num
print(total_sum)
しかし、Haskellでは、foldl関数を使って以下のようになります。
ghci> foldl (+) 0 [1,2,3]
6
どうですか？？めちゃCoooolですよね!!
foldlとかfoldrとか
foldl関数の最後の文字lはleftのlで、引数に取るリストを左側から順に処理していきます。そして、実は、foldr関数というのがあり、最後の文字rはrightのrで、引数に取るリストを右側から処理していきます。
本問の場合には、リストをどちらから処理しても特に問題ないので、どちらを使っても構いません。処理していく方向に注目しなければならない場合には、これら関数を使い分けましょう。
解答例
maximum関数を利用して簡単に解答するパターン
解答例 maximum
main = do
a <- map read . words <$> getLine :: IO [Int]
print . maximum $ a
foldl関数を利用してCoolに解答するパターン
解答例 foldl
main = do
a <- map read . words <$> getLine :: IO [Int]
print . foldl max 0 $ a
問題「文字の交換」
アルゴ式の解説では、文字列を文字の配列として捉え指定の位置にある文字を入れ替えることでこの問題を解くという方向性が示されています。しかし、Haskellの場合、基本的にリストを定義した後、そのリスト自体の任意番目の要素を書き換えることが出来ないため、他のアプローチが必要になります。
リストの一部を取り出す関数takeとdrop
リストの一部を取り出す関数を利用して組み合わせることで、文字列を自由自在に操作してみましょう。
take関数はリストの初めからn番目までを抜き出す関数で、一方drop関数は逆にリストの初めからn番目までを削除する関数です。
ghci> take 2 [1..5]
[1,2]
ghci> drop 2 [1..5]
[3,4,5]
take,dropを使った方針
これを利用して"abcdefg"の2番目と5番目の文字を入れ替えるとすると、まず、文字列を以下の様な部分で分割することを考えます。
1.２番目より前の部分"a"
2.２番目は５番目の"e"
3.２番目より後ろで５番目より前の部分"cd"
4.５番目は２番目の"b"
6.５番目より後ろの部分"fg"
このように上手く分割できさえすれば、次にそれぞれの文字列を++演算子で繋げることで、問題を解くことが出来ます。
解答例
解答例
main :: IO ()
main = do
s <- getLine
[n,m] <- map read . words <$> getLine :: IO [Int]
let a = take (n-1) s
b = [s !! (m - 1)]
c = drop n $ take (m-1) s
d = [s !! (n - 1)]
e = drop m s
putStrLn $ a ++ b ++ c ++ d ++ e
問題「労働時間」
受け取る要素の個数が決まっている場合、リストとして受け取って各要素をパターンマッチで変数名に割り振ることが出来ます。そして、その変数名をつかって処理のコードが書けるので、わかりやすくなります。
解答例
解答例
main = do
[a,b,c,d] <- map (read :: String -> Int) . words <$> getLine
print $ (b-a) - (d-c)
Discussion