すごいHaskell 第4章 再帰 メモ
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関数:2つのリストを受け取り、綴じ合わせたリストを返す。 (例えば、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
余談
この章にでてきたわからなかった漢字 - 綴じ合わせ(とじあわせ) - 綴る(つづる) - 定跡(じょうせき)、定石も"じょうせき"と読む