2011-05-05
第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
ここまでのまとめ：ライブラリ関数
|
ここまで教科書に出てきたライブラリ関数(演算子も含める)をまとめてみる。
教科書の付録Aにはもっと多くの関数が載っている。（付録Aを読んでみたら、ガードのotherwiseはキーワードではなくTrueと評価される定数だった。新しい発見。）
(+) :: Num a => a -> a -> a(-) :: Num a => a -> a -> a(*) :: Num a => a -> a -> anegate :: Num a => a -> aabs :: Num a => a -> asignum :: Num a => a -> amod :: Integral a => a -> a -> adiv :: Integral a => a -> a -> aeven :: Integral a => a -> Boolodd :: Integral a => a -> Bool(/) :: Fractional a => a -> a -> arecip :: Fractional a => a -> a(^) :: (Num a, Integral b) => a -> b -> asum :: Num a => [a] -> aproduct :: Num a => [a] -> a(++) :: [a] -> [a] -> [a]head :: [a] -> atail :: [a] -> [a](!!) :: [a] -> Int -> atake :: Int -> [a] -> [a]drop :: Int -> [a] -> [a]length :: [a] -> Intnull :: [a] -> Boolreverse :: [a] -> [a]init :: [a] -> [a]not :: Bool -> Bool(&&) :: Bool -> Bool -> Bool(||) :: Bool -> Bool -> Boolfst :: (a,b) -> asnd :: (a,b) -> bzip :: [a] -> [b] -> [(a,b)]splitAt :: Int -> [a] -> ([a],[a])(:) :: a -> [a] -> [a]id :: a -> a(==) :: Eq a => a -> a -> Bool(/=) :: Eq a => a -> a -> Bool(<) :: Ord a => a -> a -> Bool(<=) :: Ord a => a -> a -> Bool(>) :: Ord a => a -> a -> Bool(>=) :: Ord a => a -> a -> Boolmin :: Ord a => a -> a -> amax :: Ord a => a -> a -> ashow :: Show a => a -> Stringread :: Read a => String -> aconst :: a -> b -> amap :: (a -> b) -> [a] -> [b]and :: [Bool] -> Boolor :: [Bool] -> Boolconcat :: [ [a] ] -> [a]fromIntegral :: (Integral a, Num b) => a -> breplicate :: Int -> a -> [a]
Data.Char
第5章 リスト内包表記
|
C#だとLINQだけど、Haskellなどの関数型言語やPythonではリスト内包。これも書き方さえ覚えてしまえばそんなに難しい話じゃない。
Haskellではforとか書かないので、やっぱり数学っぽい。でもやってることはforと同じ。
[(x, y) | x <- [1, 2, 3], y <- [4, 5]]
と、リストの中にバー(|)を置いて、右側に生成器を書く。生成器を複数並べると、ネストしたforみたいになる。(最も右側の生成器が最も頻繁に変化するというあたりもforと同じ。)
リスト内包でもワイルドカード(_)が使える。
first ps = [x | (x, _) <- ps]
でもこれ、ワイルドカードである意味はあるのかな？
first ps = [x | (x, y) <- ps]
これでも同じじゃないかと思うけど……それとも遅延評価されるかどうかが変わるのだろうか？
ガード
リスト内包のガードはフィルタになる。LINQでいうところのwhere、Pythonのリスト内包で言うところのif。
Haskellだとカンマ(,)で区切って論理式を書くようだけど、分かりやすいのかこれ？関数定義のガードはバー(|)を伴うけど、リスト内包ではすでにバーを使ってしまっているからカンマ区切りって、なんだかなあ。
factors n = [x | x <- [1..n], n `mod` x == 0]
書いてしまえば、短くまとまっているけどね。
教科書では、factorsからprime、primeからprimesを作っているので、写経してみる。
factors n = [x | x <- [1..n], n `mod` x == 0] prime n = factors n == [1, n] primes n = [x | x <- [2..n], prime x]
zip関数
自分で書くとこんな感じか？（復習を兼ねて、cons演算子とパターンマッチで）
zip' _ [] = [] zip' [] _ = [] zip' xs ys = (head xs, head ys) : zip' (tail xs) (tail ys)
教科書では、zipからpairsを作り、pairsからsortedを作っているので、写経してみる。
pairs xs = zip xs (tail xs) sorted xs = and [x <= y | (x, y) <- pairs xs]
なるほど、and関数(とor関数)にはリストを食わせるのか。逆に言うとこいつらは2項演算子じゃないんだな。
文字列の内包表記
ここで、Stringは[Char]であることが示される。気づいてたけど。
ただし String is a [Char]なのはいいけど、逆はどうなんだろう。つまり、Stringと[Char]は同値なのか？というのが気になったので、試してみた。
abc :: a -> String abc _ = ['a', 'b', 'c']
という関数を書いてみたけど普通に使えたので、Stringは[Char]のエイリアスなんだろうと理解した。
シーザー暗号
これも写経する。
import Data.Char table = [8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1] let2int c = ord c - ord 'a' int2let n = chr (ord 'a' + n) shift n c | isLower c = int2let ((let2int c + n) `mod` 26) | otherwise = c encode n xs = [shift n x | x <- xs] lowers xs = length [x | x <- xs, isLower x] count x xs = length [x' | x' <- xs, x == x'] percent n m = (fromIntegral n / fromIntegral m) * 100 freqs xs = [percent (count x xs) n | x <- ['a'..'z']] where n = lowers xs chisqr os es = sum [((o - e) ^ 2) / e | (o, e) <- zip os es] rotate n xs = drop n xs ++ take n xs positions x xs = [i | (x', i) <- zip xs [0..n], x == x'] where n = length xs - 1 crack xs = encode (-factor) xs where factor = head (positions (minimum chitab) chitab) chitab = [chisqr (rotate n table') table | n <- [0..25]] table' = freqs xs
うわ、動いた。すごいけど気持ち悪っ！
演習問題
問題1
sum [n^2 | n <- [1..100]]
問題2
replicate n x = [x | _ <- [1..n]]
問題3
pyths n = [(x, y, z) | x <- [1..n], y <- [1..n], z <- [1..n], x^2 + y^2 == z^2]
問題4
factors n = [x | x <- [1..n], n `mod` x == 0] perfects n = [x | x <- [1..n], sum (factors x) == 2 * x]
問題5
concat [[(x,y) | y <- [4,5,6]] | x <- [1,2,3]]
問題6
find k t = [v | (k', v) <- t, k == k'] positions x xs = find x (zip xs [0..n]) where n = length xs - 1
問題7
scalarproduct xs ys = sum [x * y | (x, y) <- zip xs ys]
問題8
上記シーザー暗号の差分だけ。面倒だったからmap関数を使ったけど、いいよね。教科書にもさらっと出てきたし。
let2int' b c = ord c - ord b int2let' b n = chr (ord b + n) shift' b n c = int2let' b ((let2int' b c + n) `mod` 26) shift n c | isLower c = shift' 'a' n c | isUpper c = shift' 'A' n c | otherwise = c crack xs = encode (-factor) xs where factor = head (positions (minimum chitab) chitab) chitab = [chisqr (rotate n table') table | n <- [0..25]] table' = freqs (map toLower xs)
コメントを書く