Haskell個人メモ :: 4.再帰

シリーズ :: [Qiita記事]

Haskell個人メモ :: 1.基本
Haskell個人メモ :: 2.型
Haskell個人メモ :: 3.関数の構文
Haskell個人メモ :: 4.再帰　←いまここ

再帰の必要性と考え方

• 命令形言語と違ってループが無いので、代わりに 再帰 を使う。
• どうやって ではなく、 どうあるべきか で考える。（数学的な定義のイメージ）
  • 例1) nの階乗の定義
    • 0! = 1
    • n! = n * (n - 1)!
  • 例2) n番目のフィボナッチ数
    • 1番目のフィボナッチ数は1
    • 2番目のフィボナッチ数も1
    • n番目のフィボナッチ数は(n - 2)番目のフィボナッチ数 + (n - 1)番目のフィボナッチ数
• 問題の 基底部 （これ以上分解できない実体の値）を考える。
  • 階乗の例では0! = 1
  • フィボナッチ数の例では、1番目の1と2番目の1
  • 一般的にリストであれば空のリスト（[]）、数値であれば0や1を考えると良いかも。
• 与えられた値を分解して、再帰によって結果を定義する ことを考える。

再帰コードの例

標準ライブラリの関数を自分で実装してみる例。
（「すごいHaskell楽しく学ぼう」に書かれているコードと殆ど同じです）

maximum

-- | 最大値を求める
maximum' :: (Ord a) => [a] -> a
maximum' []     = error "List is empty."
maximum' [x]    = x
maximum' (x:xs) = max x (maximum' xs)

• リスト内の要素は順序付けされている必要があるのでOrd型クラスを制約に追加
• 空のリストの場合はエラー
• 【基底部】要素数が1のリストであれば（当然ながら）それが最大値
• 先頭要素とそれ以外でリストを分解し、「先頭要素」と「残りのリストの最大値（再帰）」のうち大きい方（max）が最大値

「先頭要素」と「それ以外のリスト」に分解して、「それ以外のリスト」に対して再帰的に関数を適用するのはリストの再帰における黄金パターン。

replicate

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

パターンマッチで0を基底部としても良いけれど、ガードにすることで負のケースも処理できる。

take

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

reverse

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

末尾への要素追加は出来ないので++で連結している。
連結はリスト同士なので、[x]としてリストにしている。

repeat

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

基底部が無い例。（無限リスト）

zip

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

基底部が2つあるケース。（1つ目のリストが空、2つ目のリストが空）

elem

elem' :: (Eq a) => a -> [a] -> Bool
elem' _ [] = False
elem' a (x:xs)
  | (a == x)  = True
  | otherwise = elem' a xs

要素は比較可能でなければならないのでEq型クラス制約をつけている。

クイックソート

qsort :: (Ord a) => [a] -> [a]
qsort []     = []
qsort (x:xs) = (qsort lt) ++ [x] ++ (qsort gt)
  where
    lt = filter (<= x) xs
    gt = filter (>  x) xs

よく「世界一美しいクイックソート」として紹介される例。（書き方は人によって少し異なったりしますが）
filterは述語を使用してリストをフィルタリングする処理。

最後に（再帰に慣れるまで苦労しての感想）

少なくとも私は、再帰的な考え方に慣れるまでかなり時間がかかりました。
（C言語のポインタのように、人によってはすぐに理解できてしまうのかもしれませんが）

再帰的にコードを書くポイントは冒頭で記載しましたが、やはり多くのHaskellの記事で「基底部」と「それ以外の再帰部」に分解することが コツ とされています。

最初の頃は、それは分かるけど「基底部」ってどうやって考えたら良いのだろう、と非常に苦心しました。

個人的には関数プログラミングの本質である、 問題を定義する という考え方がポイントかな、と思いました。
答えをどのように求めるか、ではなく どうあるべきか で考えるということです。

再帰コードの例を見ても、どれもが論理的な 定義 に過ぎないことが分かります。
その定義を元に実際の値を計算するのはコンピュータであって、プログラマではないのです。

あとはとにかく練習として再帰コードをたくさん書くのが良いかと思います。
たくさん書いているうちに、ある日になって突然見えてくるものがあります。