すごいHaskell 第４章 再帰 メモ

Hello 再帰

この章では再帰関数について書いてある。

• 再帰とは関数定義の中で自分自身を呼び出す関数

• 関数を再帰的に定義するには問題の基底部（これ以上分解できない、 解を明示的に定義しなければならない場合）と、それ以外に分ける。

• フィボナッチ数列の例。定義通り実装すると以下のようになる

fibo :: Int -> Int
fibo 0 = 0 -- 基底部
fibo 1 = 1 -- 基底部
fibo x = fibo (x - 1) + fibo (x - 2)  -- ここで再帰

• Ord型クラスのインスタンスのリストからmaxを返す関数maximum'の例

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list!"
maximum' [x] = x -- 基底部
maximum' (x:xs) = max x (maximum' xs) -- 再帰

すでにHaskellで実装されている関数を再度実装していく。

• replicate関数：Int と値を受け取り、値ぶん繰り返したリストを 返す。

replicate' :: Int -> a -> [a]
replicate' n x
    | n <= 0 = []
    | otherwise = x : replicate' (n - 1) x

• take関数：指定されたリストから指定された数の要素を返す。

take' :: Int -> [a] -> [a]
take' n _
    | n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n - 1) xs

• reverse関数：逆順にしたリストを返す。

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

• repeat関数：要素を受け取り、無限リストを返す。

repeat' :: a -> [a]
repeat' x = x : repeat' x

• zip関数：２つのリストを受け取り、綴じ合わせたリストを返す。 （例えば、zip [1, 2, 3] [4, 5] は [(1, 4), (2, 5)] を返す。長い方の リストは短い方のリストに切り詰められる。）

zip' :: [a] -> [b] -> [(a, b)]
zip' [] _ = [] -- 基底部
zip' _ [] = [] -- 基底部
zip' (x:xs) (y:ys) = (x, y) : zip' xs ys

• elem関数：値とリストを受け取り、その値がリストに含まれるかを判定する

elem' :: (Eq a) => a -> [a] -> Bool
elem' n [] = False -- 基底部
elem' n (x:xs)
 | n == x = True
 | otherwise = n elem' xs

クイック、ソート

リストの再帰的なソート方法の中で最もクールなソートとして、この章では クリックソートが紹介されている。クリックソートの内容については省略する。

qsort :: (Ord a) => [a] -> [a]
qsort [] = [] -- 基底部
qsort (x:xs) =
  let smallerOrEqual = [a | a <- xs, a <= x] -- ピボット以下のリスト
      larger = [a | a <- xs, a > x]  -- ピボットより大きいリスト
  in qsort smallerOrEqual ++ [x] ++ qsort larger

余談

この章にでてきたわからなかった漢字 - 綴じ合わせ(とじあわせ) - 綴る(つづる) - 定跡(じょうせき)、定石も"じょうせき"と読む