すごいH本読んだからまとめ 5 「再帰」

はじめに

• すごいHaskellたのしく学ぼうを読んだのでちょっとずつまとめていきたい。まとめていきたい。

• シリーズ

  • すごいH本読んだからまとめ 1 「関数の呼び方、関数の定義の仕方」
  • すごいH本読んだからまとめ 2 「リスト,タプル」
  • すごいH本読んだからまとめ 3 「型」
  • すごいH本読んだからまとめ 4 「関数の構文」

再帰

• Haskellにfor文はない模様（基本的には変数の状態変更を扱わないんだからいらないよねって感じ）
• for文っぽいことやりたかったら再帰, fold, 内包表記を使えば大抵のことは実現できる
• 今回は再帰について

そもそも再帰とは

• 関数定義のときにある条件で自分自身を呼び出すこと。
• 関数内で自分自身が関数としてよばれると再帰的呼び出しとかいう

例

-- 再帰の話になるとよく例題にされる関数
-- factorialは階乗
-- 5の階乗は 「 5! = 5 * 4 * 3 * 2 * 1 = 120 」となる
factorial' :: (Integral n) => n -> n
factorial' 0 = 1
factorial' x = x * factorial' (x-1) -- 自分自身を呼び出す。

*Main> factorial' 5
120

基底部と再帰部

• 再帰関数には基底部と再帰部がある
• 再帰部は繰り返し自分自身を呼び出す部分
• 基底部はこれ以上再帰しないで一定の値を返す部分

例

-- さっきの関数で基底部と再帰部を確認

factorial' :: (Integral n) => n -> n
factorial' 0 = 1 -- 基底部
factorial' x = x * factorial' (x-1) -- 再帰部

*Main> factorial' 5
120

• 下記の通り再帰関数の値は決まる
  1. 再帰部を積み重ねる
  2. 基底部が決定する
  3. 再帰部の値積み重なった再帰部の値が決定していく
• 複数の再帰部が存在する関数があったとしてそれは変わらない

再帰関数を作ってみる

replicate

ある数の分だけ、同じ値のリスト作成

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

take

与えられたリストから指定した数の分だけ取り出した新しいリスト作成

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

zip

２つのリストをタプルでまとめたものにする。リストの長さが違う場合は長い方の余ったリストは無視される

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

quicksort

クイックソート、先頭の値より大きいものと小さいもので分けていく計算を再帰的に行う

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

*Main> quicksort　[1, 3, 2, 5, 1, 9, 4, 7, 3]
[1,1,2,3,3,4,5,7,9]
*Main> quicksort　"vfdaiogfygrhyahvghakfhjhsgaf"
"aaaadffffgggghhhhhijkorsvvyy"