Algorithm Design with Haskell 読書会 #1 PART ONE BASICS
Chapter 1
Functional Programming
thinning に当たる日本語は?
細線化?
基本の型
自然数の型として type Nat = Int をよく使う
基本の関数
map, filter, foldr
使う
label xs = zip [0..] xs
length = foldr succ 0 where succ x n = n + 1
foldl
foldl (+) x [x, y, z] = ((e + x) + y) + z
foldr を使って実装できる
foldl f e = foldr (filp f) e . reverse
リスト処理
head = foldr (<<) undefined where x << y = x
リストを全部見るから遅い?
code:haskell
head (x:xs) = foldr (<<) undefined (x:xs)
= x << foldr (<<) undefined xs
= x
定数時間になる
リストの中身を走査する順番が重要になることもある
concat = foldr (++) []
concat = foldl (++) []
どちらも結果は同じだけど、foldrのほうが効率が良い
(x:xs) ++ ys = x : (xs ++ ys)
一番目の引数(左)が長いと結合に時間がかかる
右から結合したほうが早い
データが無限に入ってくるリストの場合は左から右に走査する必要がある
scanl :: (b -> a -> b) -> b -> [a] -> [b]
オンラインアルゴリズム
対比して、最初から全データが得られるものをオフラインアルゴリズムという
帰納的、再帰的定義
code:haskell
perms1 [] = [[]]
inserts x [] = x
inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)
帰納的定義: 初期値と、n→n+1という構造に対して定義する
帰納的に定義される関数のほとんどは foldr で書ける
code:haskell
perms1 = foldr step [[]] where step x xss = concatMap (inserts x) xss
再帰的定義: 与えられた構造を分解しながら定義する
code:haskell
perms2 [] = [[]]
picks [] = []
Q. perm1, 2 って順番は変わるの?
変わる
分割統治法は再帰的定義
貪欲法やthinningは帰納的
手続き型言語ではwhile や until でループするが、Haskellでは再帰が主に使われる
Fusion 融合則
2つの計算を1つの計算に融合できる
code:haskell
map f . map g = map (f . g)
concatMap f . map g = concatMap (f . g)
foldr f e . map g = foldr (f . g) e
foldr f e . concat = ???
Master fusion rule
code:haskell
h . foldr f e = foldr g (h e) s.t. h (f x y) = g x (h y)
s.t. のl部分を fusion conditon と言う
証明
foldrを使った帰納的定義毎に equation reasoning によって示す
f が strict な関数であることは暗黙の仮定となっている
foldr f e . concat = ??? に戻る
concat の定義に戻ろう
concat = foldr (++) []
Master fusion rule の証明で使った引数で場合分けするやり方を point-wise reasoningという
一方で引数を省略する point-free reasiong もある
累積とタプル
整数のリストのリストから合計が正の値になるまでリストを結合して返す collapse 関数
振る舞いとしては concat して 先頭からの累積値が0以上になるまでtakeする感じ
code:haskell
collapse = help [] xss
help xs xss = if sum xs > 0 || null xss
then xs
else help (xs ++ head xss) (tail xss)
徐々に大きくなる xs の sum を毎回計算していてもったいない
途中までの計算結果をタプルに乗っけてあげることで解決する
code:haskell
collapse xss = help (0, []) (labelsum xss)
labelsum xss = zip (map sum xss) xss
help (s, xs) xss = if s > 0 || null xs
then xs
else help (cat (s, xs) (head xss)) (tail xss)
cat (s, xs) (t, ys) = (s + t, xs ++ ys)