bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskell ドリル8 パターン照合

1.概略

関数型プログラミングでは自分で自分を呼び出す関数は、これは再帰関数と呼ばれるが、好んで使われる。好んで使われる理由は、例題や問題を解くうちにだんだんに理解してもらえると思うが、主な理由は計算しようとする対象の姿がはっきりと見えることにある。JavaやCなどの手続き型言語では計算の手順を記述するが、Haskellでは計算の手順は示さない。Hasekllは姿を示すだけである。JavaやCに慣れている人は、計算の手順がどのようになっているのかを理解しようとするため、Hasekllのプログラムを見たときは分かりにくい。そこには、対象の姿あるいは論理が描かれているだけなので、手順を探すことに苦労する。

Haskell再帰関数で威力を発揮するのがパターン照合である。計算の対象がいくつかのパターンに分かれている場合が多いが、その場合には、パターンに分けてプログラムすると分かりやすいプログラムとなる。

Haskellドリルも前回までは基礎的な事項であったが、ここからは少し難しくて、少し長いプログラムを書くようになるので、これまでのようにWinGHCiに直接プログラムを打ち込むことは難しくなる。そこで、今回からはプログラムのファイルを作成してそれをWinGHCiにロードすることとする。また、Haskellのプログラムには.hsというファイル名拡張子をつける。プログラムを作成するためのエディタは使い慣れているものでよい。ここでは、Windowsアクセサリにあるメモ帳を使用した。

2.例題

問題:リストlstの中にある要素xが含まれているかを調べる関数elem'を用意せよ。

パターンわけをすると次のようになる。
1)リストが空である時は一致しないので、Falseである。
2)リストが空でないときはリストを先頭の要素yと残りのリストysに分ける。もし、yがxと一致していればTrueである。そうでなければ、残りのリストysに対して関数elem'を施す。これを素直にプログラム化すると次のようになる(なお、ファイルに書き込む場合には、関数の前にletをつける必要はない。つける必要があるのは、WinGHCiの画面で関数を打ち込むときだけである)。

なお、下のプログラムで、縦棒 | はガードと呼ぶ。ガードの右横にはガードを越えるための条件がある。最初のガードに対しては x == yである。従って、xがyと一致していればこのガードを越えることができ、=以降のプログラムを実行する。

最後のガードはotherwiseである。これはいかなる場合でも、ガードは越えられる。ガードを用いるプログラムでは、最後に必ずotherwiseのガードを用意する。そうでないと、すべてのガードが越えられなかったとき行く先がなくなる。

elem' x [] = False
elem' x (y:ys)
 | x == y  = True
 | otherwise = elem' x ys 

このプログラムを、例えばelem.hsというファイルに書き込み、WinGHCiからFile->Loadでこのファイルを読み込むと利用できるようになる。読み込んだ時にOkと出ていれば、プログラムに文法的なエラーはない。もし、Okでなければ、:eと打ち込むとエディタが開かれるので、修正してファイルを閉じればよい。

いくつかの例について実行してみる。その結果を下図に示す。
f:id:bitterharvest:20141210095520p:plain

3.問題

問題1:リストから先頭の要素を散り除く関数tail'を作成せよ。

問題2:リストから最後の要素を散り除く関数init'を作成せよ。

問題3:リストの長さを求める関数length'を作成せよ。

問題4:リストからn番目の要素を取り出す関数nthを作成せよ。

問題5:リストからn番目までの要素からなる部分リストを得る関数take'を作成せよ。

問題6:文字列からブランクを取り除く関数removeBlankを作成せよ。

問題7:リストから要素xと要素yを取り除く関数remove'を作成せよ。

問題8:数列から偶数を取り除く関数removeEvenを作成せよ。

問題9:リストを反転させる関数reverse'を作成せよ。

問題10:リストが与えられた時、両端の要素を除いた部分リストを反転させる関数reverse1を作成せよ。