Hatena::Grouphaskell

猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 このページをアンテナに追加 RSSフィード

2011-05-05

第6章 再帰関数

01:03 | 第6章 再帰関数 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

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

基本概念

繰り返し簡約することで値が求まる。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

再帰の秘訣

他のプログラミング言語で再帰に馴染んでいる人にしてみれば、何を今更な内容かも。

  1. 型を定義する
  2. 場合分けをする
  3. 簡単な方を定義する
  4. 複雑な方を定義する
  5. 一般化し単純化する

第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

ここまでのまとめ:ライブラリ関数

19:05 | ここまでのまとめ:ライブラリ関数 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

ここまで教科書に出てきたライブラリ関数(演算子も含める)をまとめてみる。

教科書の付録Aにはもっと多くの関数が載っている。(付録Aを読んでみたら、ガードのotherwiseはキーワードではなくTrueと評価される定数だった。新しい発見。)

  • (+) :: Num a => a -> a -> a
  • (-) :: Num a => a -> a -> a
  • (*) :: Num a => a -> a -> a
  • negate :: Num a => a -> a
  • abs :: Num a => a -> a
  • signum :: Num a => a -> a
  • mod :: Integral a => a -> a -> a
  • div :: Integral a => a -> a -> a
  • even :: Integral a => a -> Bool
  • odd :: Integral a => a -> Bool
  • (/) :: Fractional a => a -> a -> a
  • recip :: Fractional a => a -> a
  • (^) :: (Num a, Integral b) => a -> b -> a
  • sum :: Num a => [a] -> a
  • product :: Num a => [a] -> a
  • (++) :: [a] -> [a] -> [a]
  • head :: [a] -> a
  • tail :: [a] -> [a]
  • (!!) :: [a] -> Int -> a
  • take :: Int -> [a] -> [a]
  • drop :: Int -> [a] -> [a]
  • length :: [a] -> Int
  • null :: [a] -> Bool
  • reverse :: [a] -> [a]
  • init :: [a] -> [a]
  • not :: Bool -> Bool
  • (&&) :: Bool -> Bool -> Bool
  • (||) :: Bool -> Bool -> Bool
  • fst :: (a,b) -> a
  • snd :: (a,b) -> b
  • zip :: [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 -> Bool
  • min :: Ord a => a -> a -> a
  • max :: Ord a => a -> a -> a
  • show :: Show a => a -> String
  • read :: Read a => String -> a
  • const :: a -> b -> a
  • map :: (a -> b) -> [a] -> [b]
  • and :: [Bool] -> Bool
  • or :: [Bool] -> Bool
  • concat :: [ [a] ] -> [a]
  • fromIntegral :: (Integral a, Num b) => a -> b
  • replicate :: Int -> a -> [a]

Data.Char

第5章 リスト内包表記

12:11 | 第5章 リスト内包表記 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

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)