記事の内容 典型的な再帰関数の練習
再帰とは、関数の定義の中で自分自身を呼び出すことです。
この記事では、典型的な再帰関数の練習を実施します。
基底部について確認
解こうとする問題を同じ種類のより小さな問題に分解し、それら部分問題を解くことを考える。
分解していった結果、これ以上分解できず、解を再帰を使わずに定義しなければならないケースにたどり着く。これを基底部という。
なぜHaskellで再帰が重要か
Haskellの目的は、ほしい結果が何であるかを直接定義することです。
Haskellの特徴の一つで、副作用がないというものがあります。これは値が変化しないということを意味します。普通のプログラミング（手続き型）では、値が変化しないなんて想像できません。しかし、Haskellでは、計算式、定義式をそのまま記述するため、副作用がありません。
実装
すごH本を写経します。
maximum関数
リストの中で一番大きな数を返す関数。
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "empty"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
再帰でよく使う共通のパターン x:xs
「基底部は空リストし、x:xsパターンで、リストの先頭要素をxに束縛し、残りをxsに束縛する」
replicate関数
値を指定された数だけ繰り返す。
replicate' :: Int -> a -> [a]
replicate' n x
| n <= 0 = []
| otherwise = x : replicate' (n-1) x
注意 :演算子 リストの先頭に要素を追加する
reverse関数
リストを逆順にする
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
elem関数
値とリストを受け取り、その値がリストにふくまれるか調べる。
elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
| a == x = True
| otherwise = a `elem` xs
探し物が先頭になければ、xsを調べ、空のリストにたどり着いたなら、結果はFalse。
クイックソートを再帰で！
xより小さいか等しい要素を左に置きたい。そのためにリスト内包表記を使う。大きいものも同様。
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
述語とリストを受け取り、述語を満たすものだけからなるリストを返すfilter関数を使うと、さらに読みやすくかけます。
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerOrEqual = filter (<= x) xs
larger = filter (> x) xs
in quicksort smallerOrEqual ++ [x] ++ quicksort larger