Haskell を使ってみる 8 (再帰)

前回の続き

再帰

関数を再帰的に定義する場合は問題を同じ種類のより小さな問題に分解する。再帰を使わずに定義できる問題を基底部と呼ぶ。再帰を実装する場合は基底部から考える。

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "empty list"
maximum' [x] = x -- 基底部 (単一要素のリストの最大値はその唯一の要素を返す)
maximum' (x:xs) = max x (maximum' xs)

replicate' :: Int -> a -> [a]
replicate' n x
    | n < 1 = [] -- 基底部 (繰り返しが0以下のときは空のリストを返す)
    | otherwise = x : replicate' (n-1) x

take' :: Int -> [a] -> [a]
take' n _
    | n < 1 = [] -- 基底部 (取り出す個数が0以下のときは空のリストを返す)
take' _ [] = [] -- 基底部 (空のリストからは要素を取り出せないので空のリストを返す)
take' n (x:xs) = x : take' (n-1) xs

reverse' :: [a] -> [a]
reverse' [] = [] -- 基底部 (空のリストの逆順は空のリスト)
reverse' (x:xs) = reverse' xs ++ [x] -- tail の逆順の後ろに head を付ける

-- 基底部のない再帰で無限リストを作成する
repeat' :: a -> [a]
repeat' x = x : repeat' x

zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = [] -- 基底部 (空のリストを zip したときは空のリストを返す)
zip' [] _ = [] -- 基底部 (同上)
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys -- head のペアの後ろに tail を zip したものを繋げる

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False -- 基底部 (空のリストは値を含まないので False を返す)
elem' a (x:xs)
    | a == x = True -- 渡された値と head が一致するか調べる
    | otherwise = a `elem'` xs -- head が一致しなければ tail を調べる

クイックソート

再帰を使ってクイックソートを実装する例。

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = [] -- 基底部 (空のリストをソートしたときは空のリストを返す)
quicksort (x:xs) =
    let smallerOrEqual = [a | a <- xs, a <= x]
        larger = [a | a <- xs, a > x]
    in quicksort smallerOrEqual ++ [x] ++ quicksort larger

リストの先頭要素をピボットとする。リスト内包表記でピボット以下の要素のリスト (a <= x) とピボットより大きい要素のリスト (a > x) を取り出す。取り出した要素のリストには let 束縛で名前を付ける。それぞれのリストに quicksort 関数を再帰的に適用する。

今回は再帰について。