Haskell part5

part5は再帰について。

ここまでもサンプルコードにもよく出てきたようにHaskellでは割と重要な要素らしい。数学ではフィボナッチ数列なんかが再帰的な構造を持っている。

F(3) = F(2) + F(1)
     = (f(1) + f(0)) + f(1)

F(1)やF(0)のようなこれ以上入れ子にできない要素をedge conditionと呼ぶ。再帰を無限回繰り返さない意味で大事。Haskellではwhile/forループでどのように値を得るか記述する代わりに再帰的な表現でそれがどのようなものかを宣言する。哲学的だなorz

ぱねぇMaximun

再帰の一例としてmaximumを取り上げる。これはOrdタイプクラスのリストの中から最大のものを返す関数。これを再帰的に定義していく。

edge conditionは単一の要素しか持たないリストであり、この最大は選択の余地がない。次にもうちょっと長いリスト。headとtailに分けて考えると、tailの最大値よりheadの値が大きければheadが最大値。tailの最大値が大きければ、それが最大値。

Haskellで表現する。

mymaximum :: (Ord a) => [a] -> a
mymaximum [] = error "maximum of empty list."
mymaximum [x] = x
mymaximum (x:xs)
    | x > maxTail = x
    | otherwise = maxTail
    where maxTail = mymaximum xs

whereで再帰が定義されているのが地味に分かりにくい。パターンマッチのおかげで一切if/elseがなくクールだろ？みたいな内容。maxを使うともっとシンプルに書ける。

nicemaximum :: (Ord a) => [a] -> a
nicemaximum [] = error "my heart is empty."
nicemaximum [x] = x
nicemaximum (x:xs) = max x (nicemaximum xs)

replicate, take

指定した要素を指定した回数、列挙する関数。edge conditionは繰り返し数が0以下になった場合。この状態では空のリストを返せばいい。

myreplicate :: (Num i, Ord i) => i -> a -> [a]
myreplicate n x
    | n <= 0    = []
    | otherwise = x:myreplicate (n-1) x

実行サンプル。

*Main> myreplicate 3 5
[5,5,5]
*Main> myreplicate 0 5
[]
*Main> myreplicate (-3) 5
[]

負の数を与えるときは()で括らないと- 3て感じに解釈されて怒られる。

take。これはリストから指定した数分の要素を取得する関数。0個の要素を取り出した結果は[]、空行列からは何も取り出せないので結果は常に[]。この当たりがedge conditionかなー？

mytake :: (Num i, Ord i) => i -> [a] -> [a]
mytake n _
    | n <= 0     = []
mytake _ []      = []
mytake n (x:xs) = x : mytake (n-1) xs

先ほどのものよりedge conditionが2つある分、若干複雑。どちらも再帰の度に数・要素を1つ減らしていく。otherwiseが無いのでn <= 0に合致しない場合は次のパターンが評価される。

reverse。リストの並び順を逆にする関数。edge conditionは空行列。あとは(x:xs)を(xs ++ [x])という感じに並び替えていけばいい。

myreverse :: [a] -> [a]
myreverse [] = []
myreverse (x:xs) = myreverse xs ++ [x]

myreverse xsのxsはいずれ空になるからこの関数は止まる。

edge conditionが無い止まらないタイプの関数もhaskellでは実装できる。この手の関数を使うときは途中で再帰を打ち切るほうがいい。repeartを題材に考えてみる。

myrepeat :: a -> [a]
myrepeat x = x:myrepeat x

単純にmyrepeat 5とやると無限に5が並ぶリストを作り続ける。パターンに実際の数字を入れると、5:myrepeat 5>5:(5:myrepeat 5)> …。take 5 (myrepeat 5)とすれば5を5回リストに追加して止まる。本質的にはreplicate 5 3と変わらない。

zip。これは2つのリストの要素を順番にペア（タプル）にしたリストを生成する。edge conditionは2つのリストどちらかが空になった時になる。

myzip :: [a] -> [b] -> [(a, b)]
myzip _ [] = []
myzip [] _ = []
myzip (x:xs) (y:ys) = (x, y):myzip xs ys

実行結果。

*Main> myzip [1,4,5] ["yukarin", "makky"]
[(1,"yukarin"),(4,"makky")]

うむ。期待通りの結果。

elem。これはリストの中に指定した要素があるかどうかをチェックする関数。edge conditionはリストが空になった時。要素が見つからなかった事を意味するのでFalseを返せばいい。空になるまではリストから先頭要素を取り出して比較を繰り返す。

myelem :: (Eq a) => a -> [a] -> Bool
myelem a [] = False
myelem a (x:xs)
    | a == x    = True
    | otherwise = a `myelem` xs

実行結果。

*Main> myelem 3 [4,6,5,1]
False
*Main> myelem 3 [4,6,3,1]
True

うむ、動いたぜ。

Quick Sort

ソート可能なリストがあって、その要素のがOrdtypeclassだったとする。これを実際にソートしたい。クイックソートをhaskellで実装するとどうなるか？他の多くの言語と比べてもかなり短い行数で実装できる。

type signatureはquicksort :: (Ord a) => [a] -> [a]で決まりだ。edge conditionはリストが空になった時だ。メイン処理はコードを読んだほうが早い。

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smaller = quicksort [a | a <- xs, a <= x]
        bigger  = quicksort [a | a <- xs, a > x]
    in  smaller ++ [x] ++ bigger

コードでアルゴリズムそのものを表現していてちょっと感動した。最後の再帰についてのまとめは流し読み。

• 再帰にはパターンがある。
• リストをheadとtailに分割する。
• edge conditonはたいてい…
  
  • リストが空になったとき。
  • 木構造のリーフに到達したとき。

再帰的な方法で問題を解きたい場合は、再帰が適用されないケースを見つけるところから始める。それがedge conditionになる。

Written with StackEdit.