6.4 すごいHaskellたのしく学ぼう！第4章

再帰について。

再帰

再帰（関数）とは、関数内で自身を参照する関数である。
たとえば、フィボナッチ数列は再帰関数の代表例である。フィボナッチ数列は以下のように定義されている。
　 $F(0) = 0,\ F(1) = 1$
　 $F(n) = F(n-1) + F(n-2)\ if\ n \geq 2$
2行目の式で、自己参照を行なっているのが分かるだろう？

再帰の利点

再帰で問題を考えることで、部分的に考えたものを全体の答えとすることが出来る。つまり、「どうやって(How)」解くか、ではなく、「どういう(What)」モノか、ということを考えることで、解を得ることが出来る。そもそもHaskellはそういう風に設計された言語なので、再帰と非常に相性が良い。
たとえば、フィボナッチ数列ではF(0) = 0、F(1) = 1と定義されている。これはどうしようもない。このように、最低限与えなければならない情報を基底と呼ぶ。基底さえ考えれば、あとはその関数が「どういうものか？」ということを考えれば良い。

再帰でいろいろ定義する

GHCiでデフォルトで使える関数を自分で定義する。
定義から自分で考えたものがほとんどなので、すごいH本に載っている内容とは異なる場合がある。まぁ、ほとんどの関数は全く同じ実装になっている。

maximum

引数

1つのリスト（ただし、要素は順序付けが可能）。

戻り値

引数リスト内の最大要素。

定義

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "This list is empty."
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
{-
*Main> maximum' [8,2,6,3,1,8,3,9,1]
9
*Main> maximum' [5]
5
*Main> maximum' []
*** Exception: This list is empty.
-}

replicate

引数

整数、要素。

戻り値

要素を整数回繰り返したリスト。

定義

replicate' :: Int -> a -> [a]
replicate' n x
  | n <= 0    = []
  | otherwise = x : replicate' (n-1) x
{-
*Main> replicate' 5 7
[7,7,7,7,7]
*Main> replicate' 0 7
[]
*Main> replicate' (-100) 7
[]
-}

take

引数

整数、リスト。

戻り値

リストから先頭整数個を取り出したリスト。

定義

take' :: Int -> [a] -> [a]  
take' n _
  | n <= 0     = []
take' _ []     = []
take' n (x:xs) = x : take' (n-1) xs
{-
*Main> take' 5 "Hello, World!"
"Hello"
*Main> take' (-8) "Hello, World!"
""
*Main> take' 100000 "Hello, World!"
"Hello, World!"
-}

reverse

引数

リスト。

戻り値

ひっくり返したリスト。

定義

reverse' :: [a] -> [a]
reverse' []     = []
reverse' (x:xs) = reverse' xs ++ [x] 
{-
*Main> reverse' "Hello, World!"
"!dlroW ,olleH"
*Main> reverse' []
[]
-}

repeat

引数

要素。

戻り値

要素の無限リスト。

定義

無限リストなので基底がない。

repeat' :: a -> [a]
repeat' x = x : repeat' x
{-
*Main> take' 10 (repeat' 'H')
"HHHHHHHHHH"
-}

zip

引数

リスト、リスト。

戻り値

同じインデックスの要素をペアとしたリスト。

定義

zip' :: [a] -> [b] -> [(a,b)]
zip' _ []          = []
zip' [] _          = []
zip' (x:xs) (y:ys) = (x, y) : zip' xs ys
{-
*Main> zip' [1,2,3,4,5] ['a','b','c']
[(1,'a'),(2,'b'),(3,'c')]
*Main> zip' [1,2,3,4,5] ['a','b','c','d','e']
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]
*Main> zip' [1,2,3,4,5] ['a','b','c','d','e','f']
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]
*Main> zip' [1,2,3,4,5] []
[]
-}

elem

引数

要素、リスト。

戻り値

要素がリスト内にあるならTrue、ないならFalse。

定義

elem' :: (Eq a) => a -> [a] -> Bool
elem' _ [] = False
elem' n (x:xs)
  | n == x    = True
  | otherwise = elem' n xs 
{-
*Main> elem' 'h' "Hello, World!"
False
*Main> elem' 'r' "Hello, World!"
True
*Main> elem' 'r' ""
False
-}

クイックソート

めっちゃ速いソート。ソートっていうのは、リストを与えられてリスト内のデータを昇順（あるいは降順）に並べ治すこと。Haskellの場合は破壊的代入ができないので、ソートしたリストを返すだけである。
ちなみに、私の頼りない記憶によると、たしか最悪計算量がO(n^2)でバブルソートと等しいが、平均計算量がO(nlogn)でめっちゃ速い、だったと思う。

アルゴリズム

昇順ソートの場合。

軸とする数字をリスト内から1つ選ぶ（ピボットと呼ぶ）。
ピボット以下のものをピボットの左に、ピボットより大きいものを右にリスト化して置く。これをsmallerOrEqualとlargerと名付ける。
smallerOrEqualとlargerに対して、1から同じ操作を行う。

定義

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
{-
*Main> quicksort [5,7,2,8,1,6,2,9,4,2,1,0,2,1,7]
[0,1,1,1,2,2,2,2,4,5,6,7,7,8,9]
*Main> quicksort "Hello, World!"
" !,HWdellloor"
*Main> quicksort []
[]
*Main> quicksort [4]
[4]
-}

めっちゃ簡単に実装できた！前期実験でCでクイックソート（動的配列で）実装したけど、割と苦労した覚えがある。

感想

箸休め的な第4章。特に難しい内容はない。
次からは本格的に関数型言語に斬り込んでいく感じ。

技術的なやつ