Haskell入門　再帰！ #Haskell

再帰とは？

関数の定義の中で自分自身を呼び出す、という定義のしかた。
解こうとする問題を、同じ種類のより小さな問題に分解し、それら部分問題を解くことを考える。分解していった結果、これ以上分解できなくて解を再帰を使わずに定義しなければならないケースにたどり着く。これを基底部という。

なぜ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

Haskell入門 再帰！