プログラミングHaskellを読む(6)
ここのところ何故か非常に忙しいのですが、なけなしの時間を捻出して読みました。ふぅ。
第6章 再帰関数
この章は、真新しいことはあまりなく、そんなに難しくないです。次の章もかな？
I/Oはまだが～
基本
Haskellでは関数を関数自身を使って定義することが出来る。
そのように定義された関数を再帰的な関数という。
Haskellの場合、関数の引数によるパターンマッチが使用可能なので、CやJavaScriptなどの言語の再帰関数とは違った風合いになる。
-- 階乗 factorial :: Int -> Int factorial 0 = 1 -- 基底部 factorial n = n * factorial (n-1) -- 再帰部 {- 再帰を使わない場合 factorial :: Int -> Int factorial n = product [1..n] -} -- 演算子* mul :: Int -> Int -> Int m `mul` 0 = 0 m `mul` n = m + (m `mul` (n - 1)) -- リスト内の要素の積を算出するproduct product' :: Num a => [a] -> a product' [] = 1 product' (n : ns) = n * product ns -- length length' :: [a] -> Int length' [] = 0 length' (_ : xs) = 1 + length xs -- 連結演算子++ combine :: [a] -> [a] -> [a] [] `combine` ys = ys (x : xs) `combine` ys = x : (xs `combine` ys) -- 反転 reverse' :: [a] -> [a] reverse' [] = [] reverse' (x : xs) = reverse xs `combine` [x] -- 最初から比較し、初めて小さくなった時に挿入 insert :: Ord a => a -> [a] -> [a] insert x [] = [x] insert x (y : ys) | x <= y = x : y : ys | otherwise = y : (insert x ys) -- 挿入ソート isort :: Ord a => [a] -> [a] isort [] = [] isort (x : xs) = insert x (isort xs) -- フィボナッチ数列（効率は悪い気がする） fibonacci :: Int -> Int fibonacci 0 = 0 fibonacci 1 = 1 fibonacci n = fibonacci (n-2) + fibonacci (n-1) -- 相互再帰 even' :: Int -> Bool even' 0 = True even' n = odd' (n - 1) odd' :: Int -> Bool odd' 0 = False odd' n = even (n - 1)
再帰の秘訣
以下の「五段階の工程」に則れば、再帰はマスターできるらしい。
- 型を定義する
- 場合分けをする
- 簡単な方を定義する
- 複雑な方を定義する
- 一般化し単純にする
例は練習問題にて。
練習問題
1. 累乗演算子^
power :: Num a => a -> Int -> a 0 `power` _ = 0 x `power` 1 = x x `power` y = x * (x `power` (y - 1))
簡約は
2 `power` 3 = 2 * (2 `power` (3 - 1)) = 2 * (2 `power` 2) = 2 * (2 * (2 `power` (2 - 1))) = 2 * (2 * (2 `power` 1)) = 2 * (2 * 2) = 2 * 4 = 8
2. length, drop, initの簡約
length [1, 2, 3] = 1 + length [2, 3] = 1 + 1 + length [3] = 1 + 1 + 1 = 1 + 2 = 3 drop 3 [1, 2, 3, 4, 5] = drop 2 [2, 3, 4, 5] = drop 1 [3, 4, 5] = drop 0 [4, 5] = [4, 5] init [1, 2, 3] = 1 : init [2, 3] = 1 : 2 : init [3] = 1 : 2 : [] = 1 : [2] = [1, 2]
3. and, concat, replicate, (!!), elem
and' :: [Bool] -> Bool and' [] = True and' (x : xs) = x && (and' xs) concat' :: [[a]] -> [a] concat' [] = [] concat' (x : xs) = x ++ (concat' xs) replicate' :: Int -> a -> [a] replicate' 0 _ = [] replicate' n x = [x] ++ (replicate' (n - 1) x) index :: [a] -> Int -> a (x : _) `index` 0 = x (x : xs) `index` n = xs `index` (n - 1) elem' :: Eq a => a -> [a] -> Bool elem' x [y] = x == y elem' x (y : ys) | x == y = True | otherwise = elem' x ys
4. ソート済みリストを結合するmerge
一見では思いつかなかったので、まず簡約を考えました。
-- insert的な方法 merge [2, 5, 6] [1, 3, 4] = merge [5, 6] [1, 2, 3, 4] = merge [6] [1, 2, 3, 4, 5] = merge [] [1, 2, 3, 4, 5, 6] = [1, 2, 3, 4, 5, 6] -- 小さい方を取る方法 merge [2, 5, 6] [1, 3, 4] = 1 : (merge [2, 5, 6] [3, 4]) = 1 : 2 : (merge [5, 6] [3, 4]) = 1 : 2 : 3 : (merge [5, 6] [4]) = 1 : 2 : 3 : 4 : (merge [5, 6] []) = 1 : 2 : 3 : 4 : [5, 6] = [1, 2, 3, 4, 5, 6]
内、insert使うの禁止ーと書いてあったので、下の方法を取ることにします。
merge :: Ord a => [a] -> [a] -> [a] merge [] ys = ys merge xs [] = xs merge (x : xs) (y : ys) | x < y = x : merge xs (y : ys) | otherwise = y : merge (x : xs) ys
5. マージソートmsort
halve :: [a] -> ([a], [a]) halve xs = (take n xs, drop n xs) where n = (length xs) `div` 2 msort :: Ord a => [a] -> [a] msort [x] = [x] msort xs = merge (msort xs1) (msort xs2) where (xs1, xs2) = halve xs
6. 五段回の工程
◎まずはsum。
1. 型を定義する
sum :: Num a => [a] -> a
2. 場合分けをする
sum [] = sum (x : xs) =
3. 簡単な方を定義する
sum [] = 0 sum (x : xs) =
4. 複雑な方を定義する
sum [] = 0 sum (x : xs) = x + (sum xs)
5. 一般化し単純にする
得にすることなし。
◎take
1. 型を定義する
take :: Int -> [a] -> [a]
2. 場合分けをする
take 0 xs = take n (x : xs) =
3. 簡単な方を定義する
take 0 xs = [] take n (x : xs) =
4. 複雑な方を定義する
take 0 xs = [] take n (x : xs) = x : (take (n - 1) xs)
5. 一般化し単純にする
take 0 _ = [] take n (x : xs) = x : (take (n - 1) xs)
◎last
1. 型を定義する
last :: [a] -> a
2. 場合分けをする
last [x] = last (x : xs) =
3. 簡単な方を定義する
last [x] = x last (x : xs) =
4. 複雑な方を定義する
last [x] = x last (x : xs) = last xs
5. 一般化し単純にする
last [x] = x last (_ : xs) = last xs
もっとも、2の段階で、大体のビジョンが見えていないとダメな気はします。
まぁとにかく慣れるしかないでしょうね。
