第6章 再帰関数

考え方は難しくないけど、パターンマッチがおもしろい。

基本概念

繰り返し簡約することで値が求まる。n+kパターンは再帰に便利。

factorial 0       = 1
factorial (n + 1) = (n + 1) * factorial n

リストに対する再帰

これこれ。このパターンマッチを忘れていた。

product [] = 1
product (n : ns) = n * product ns

これがないと、headとかtailを無駄に書いてしまう。

ついでに、isortを写経。

insert x [] = [x]
insert x (y : ys) | x <= y = x : y : ys
                  | otherwise = y : insert x ys

isort []       = []
isort (x : xs) = insert x (isort xs)

複数の引数

第5章にzip'の自分定義をしたけど、リストパターンを使えばもっとすっきり。

zip' _ [] = []
zip' [] _ = []
zip' (x : xs) (y : ys) = (x, y) : zip' xs ys

多重再帰

フィボナッチ数が典型例。

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci (n + 2) = fibonacci n + fibonacci (n + 1)

相互再帰

例は人工的すぎるけど。

even' 0 = True
even' (n + 1) = odd' n
odd' 0 = False
odd' (n + 1) = even' n

再帰の秘訣

他のプログラミング言語で再帰に馴染んでいる人にしてみれば、何を今更な内容かも。 +型を定義する +場合分けをする +簡単な方を定義する +複雑な方を定義する +一般化し単純化する 第5段階がミソかな。

ここの写経はいいや。

練習問題

問題1

m ^ 0 = 1
m ^ (n + 1) = m * (m ^ n)

2 ^ 3 = 2 * (2 ^ 2)
      = 2 * (2 * (2 ^ 1))
      = 2 * (2 * (2 * (2 ^ 0)))
      = 2 * (2 * (2 * 1))
      = 8

問題2

length [1, 2, 3] = length (1: (2: (3: [])))
                 = 1 + length (2: (3: []))
                 = 1 + (1 + length (3: []))
                 = 1 + (1 + (1 + length []))
                 = 1 + (1 + (1 + 0))
                 = 3

drop 3 [1, 2, 3, 4, 5] = drop 3 (1: (2: (3: (4: (5: [])))))
                       = drop 2 (2: (3: (4: (5: []))))
                       = drop 1 (3: (4: (5: [])))
                       = drop 0 (4: (5: []))
                       = 4: (5: [])
                       = [4, 5]

init [1, 2, 3] = init (1: (2: (3: [])))
               = 1: init (2: (3: []))
               = 1: (2: init (3: []))
               = 1: (2: [])
               = [1, 2]

問題3

and [] = True
and (x : xs) | x == False = False
             | otherwise = and xs

concat [] = []
concat (xs : xss) = xs ++ concat' xss

concat、最初は間違えた。Hugsで実行しながら修正した。引数の型をちゃんと意識したらできた。

replicate 0 _ = []
replicate (n + 1) x = x : replicate n x

(x: _) !! 0 = x
(x: xs) !! (n + 1) = xs !! n

elem _ [] = False
elem x (y: ys) | x == y    = True
               | otherwise = elem x ys

問題4

merge [] xs = xs
merge xs [] = xs
merge (x: xs) (y: ys) | x <= y    = x : merge xs (y: ys)
                      | otherwise = y : merge (x : xs) ys

問題5

halve xs = splitAt (length xs `div` 2) xs

msort [] = []
msort [x] = [x]
msort xs = merge (msort fs) (msort ss)
           where (fs, ss) = halve xs

問題6

5段階の工程は面倒だから省略するけど、型は明示しよう。

sum :: Num a => [a] -> a
sum [] = 0
sum (x: xs) = x + sum xs

take :: Integral a => a -> [b] -> [b]
take 0 _ = []
take n [] = []
take (n + 1) (x: xs) = x : take n xs

last :: [a] -> a
last [x] = x
last (x: xs) = last xs