タコさんブログ

プログラミングメモと小言

すごいHaskell 第4章 再帰 メモ

Hello 再帰

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

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

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

fibo :: Int -> Int
fibo 0 = 0 -- 基底部
fibo 1 = 1 -- 基底部
fibo x = fibo (x - 1) + fibo (x - 2)  -- ここで再帰
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

余談

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

広告を非表示にする