「函数プログラミングの集い」のチュートリアル資料を作成するためのメモ。リストに対する再帰を2つに分類することで理解する。
再帰
関数プログラミングでは、繰り返しを再帰で実現する。入力がリストである関数を実装するとする。この種の関数は、出力の種類により以下の2つに分類できる。
- 同じ順番のリストを作る
- 数値などを作る。あるいは逆順のリストを作る。
リストからリストを作る再帰
例として、(++)、concat、map、filter の利用例と実装を示す。
(++)
(++) は連結(append)関数。
[1,2] ++ [3,4,5] → [1,2,3,4,5]
実装はこう。
(++) :: [a] -> [a] -> [a] (++) [] ys = ys (++) (x:xs) ys = x : (xs ++ ys)
concat
concat は、リストのリストをリストに平坦化する。
concat [[1,2],[3,4,5],[6]] → [1,2,3,4,5,6]
実装はこう。
concat :: [[a]] -> [a] concat [] = [] concat (xs:xss) = xs ++ concat xss
map
map は射影関数。リストのそれぞれの要素に関数を適用する。
map (+1) [1,2,3] → [2,3,4]
実装はこう。
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs
filter
filter は名前の通りフィルター。
filter even [1,2,3] → [2]
実装はこう。
filter :: (a -> Bool) -> [a] -> [a] filter _ [] = [] filter prd (x:xs) | prd x = x : filter prd xs | otherwise = filter pred xs
リストから数値など作る再帰
例として、sum、and、length、reverse の利用例と実装を示す。
sum
sum は和を計算する。
sum [1,2,3,4] → 10
実装はこう。
sum :: Num a => [a] -> a sum xs = sum' xs 0 where sum' [] r = r sum' (y:ys) r = sum' ys (y+r)
and
and は、要素がすべて True なら True、それ以外なら False
and [True,True,True] → True and [True,False,True] → False
実装はこう。
and :: [Bool] -> Bool and xs = and' xs True where and' [] r = r and' (y:ys) r = and' ys (y && r)
length
length はリストの長さを測る。
length [1,2,3,4] → 4
実装はこう。
length :: [a] -> Int length xs = length' xs 0 where length' [] r = r length' (_:ys) r = length' ys (1+ r)
reverse
reverse は、逆順のリストを生成する。
reverse [1,2,3,4] → [4,3,2,1]
実装はこう。
reverse :: [a] -> [a] reverse xs = rev xs [] where rev [] rs = rs rev (y:ys) rs = rev ys (y:rs)
普通の再帰と末尾再帰
「リストから数値など作る再帰」では、= の後に値か、自分自身が来ていた。もう一度 sum を掲載する。
sum :: Num a => [a] -> a sum xs = sum' xs 0 where sum' [] r = r sum' (y:ys) r = sum' ys (y+r)
sum' がそういう形をしている。このような再帰を「末尾再帰」という。sum を末尾再帰でない再帰で実装するとコードは簡潔になる。
sum :: Num a => [a] -> a sum [] = 0 sum (x:xs) = (+) x (sum xs)
これを普通の再帰と呼ぶことにしよう。
末尾再帰の最適化がある言語では、末尾再帰の再帰部分はジャンプに置き換えられるので、スタックを消費しない。sum のように数値を返す場合は、結果の領域の大きさが固定長なのでヒープも消費しない。(今は遅延評価のせいでサンクがヒープを消費することは無視する。)
よって、数値などを返す場合には、末尾再帰で実装することが望ましい。普通の再帰を末尾再帰に変更するには、引数を一つ増やすのが常套手段である。(いつも変換できるとは限らないが。たとえば、両替問題を解決する普通の再帰の実装を末尾再帰に直すのは困難である。)
リストを生成する関数では、普通の再帰が使われていた。concat を少し変形して再掲してみよう。
concat :: [[a]] -> [a] concat [] = [] concat (xs:xss) = (++) xs (concat xss)
concat ではなく (++) が = の後にあるので、普通の再帰だと分かる。生成されるリストは遅延データであり、遅延評価の下ではヒープを消費せず効率がよい。(自信はないが、スタックも消費しないと思う。)
concat を末尾再帰で実装するとこうなる。
concat :: [[a]] -> [a] concat xs = concat' xs [] where concat' [] rs = rs concat' (ys:yss) rs = concat' yss (rs ++ ys)
これはヒープを消費するし、遅延評価とも相性が悪い。(さらに悪いことに、(++) を何度も使うので、計算量は O(log N^2) となる。)
ここまでのまとめ：
畳み込み
リストの要素を畳み込む方法には二つある。
一つ目は、右からの畳み込み foldr である。
foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ ini [] = ini foldr op ini (x:xs) = x `op` foldr op ini xs
右からの畳み込みの理解で分かりやすいのは、[] を初期値に変え、(:) を演算子に変えるという覚え方だ。たとえば、[1,2,3,4] を初期値 0、演算子は + で畳み込むと、以下のようになる。
foldr (+) 0 [1,2,3,4] → 10
[1,2,3,4] は 1:2:3:4:[] のことだから、foldr は以下のような計算をする。
foldr (+) 0 (1:2:3:4:[]) -- [] を 0 に、: を + に変える 1 + (2 + (3 + (4 + 0)))
二つ目は、左からの畳み込み foldl である。
foldl :: (a -> b -> a) -> a -> [b] -> a foldl _ acc [] = acc foldl op acc (x:xs) = foldl op (acc `op` x) xs
左からの畳み込みでは、蓄積変数に結果を蓄えていき、最後にその蓄積結果を返す。
右からの畳み込み
foldr の定義をもう一度見てほしい。
foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ ini [] = ini foldr op ini (x:xs) = op x (foldr op ini xs)
これは普通の再帰である。よって、リストを生成する関数と相性がよい。(++)、concat、map、filter を foldr で実装すると以下のようになる。
(++) :: [a] -> [a] -> [a] (++) xs ys = foldr (:) ys xs concat :: [[a]] -> [a] concat xss = foldr (++) [] xss map :: (a -> b) -> [a] -> [b] map f xs = foldr (\y ys -> f y : ys) [] xs filter :: (a -> Bool) -> [a] -> [a] filter prd xs = foldr filter' [] xs where filter' y ys | prd y = y : ys | otherwise = ys
左からの畳み込み
foldl の定義をもう一度見てほしい。
foldl :: (a -> b -> a) -> a -> [b] -> a foldl _ acc [] = acc foldl op acc (x:xs) = foldl op (acc `op` x) xs
これは末尾再帰である。よって数値などを出力する関数と相性がよい。sum、and、length、reverse を foldl で実装すると以下のようになる。
sum :: Num a => [a] -> a sum xs = foldl (+) 0 xs and :: [Bool] -> Bool and xs = foldl (&&) True xs length :: [a] -> Int length xs = foldl (\n _ -> n + 1) 0 xs reverse :: [a] -> [a] reverse xs = foldl (\ys y -> y:ys) [] xs
力の階層
foldr と foldl は再帰で実現できた。また、map や filter は foldr で実現できた。これは、以下のような力の階層があることを意味する。
- 再帰
- 畳み込み：foldr や foldl など
- map や filter など
上に行くほど力が強い。
プログラムを書く場合は、できる限り弱い力の手法を使うべきである。たとえば、reverse の再帰による実装と畳み込みによる実装を見比べてほしい。畳み込みの方が、簡潔で意味が分かりやすい。
納得できない人のために一つ例題を挙げよう。次のような問題を解くプログラムを書いてほしい：「数値のリストを取り、偶数のみを足し合わせて返す」
再帰で実装するとこうなる：
sumEven :: [Int] -> Int sumEven xs = sumEven' xs 0 where sumEven' [] r = r sumEven' (y:ys) r | even y = sumEven' ys (y + r) | otherwise = sumEven' ys r
パッと見て意味が分かるだろうか？
適切な手法を用いればこうなる：
sumEven :: [Int] -> Int sumEven xs = foldr (+) 0 (filter even xs) {- あるいは sum を知っているなら sumEven xs = sum (filter even xs) -}
意味が断然読み取りやすくなったのが分かると思う。
本当は恐いfoldl(1)
Haskell の foldl は、蓄積変数の計算が遅延してしまう。
foldl (+) 0 [1,2,3] = foldl (+) (0+1) [2,3] = foldl (+) ((0+1)+2) [3] = foldl (+) (((0+1)+2)+3) [] = (((0+1)+2)+3) = (1+2)+3 = 3+3 = 6
この問題を解決するには、Data.List の foldl' を使うとよい。
foldl' (+) 0 [1,2,3] = foldl' (+) 1 [2,3] = foldl' (+) 3 [3] = foldl' (+) 6 [] = 6
本当は恐いfoldl(2)
「数値を出力する関数には末尾再帰の foldl」と書いたが、and は例外である。and の定義を foldl' で書いてみよう。
and :: [Bool] -> Bool and xs = foldl' (&&) True xs
簡約例を以下に示す。
foldl' (&&) True [True,False,False] = foldl' (&&) True [False,False] = foldl' (&&) False [False] = foldl' (&&) False [] = False
末尾再帰なのでスタックは消費しないが、False を見付けたところでリストの走査を中止できない。
一方、and を foldr で定義してみよう。
and :: [Bool] -> Bool and xs = foldr (&&) True xs
簡約例を以下に示す。
foldr (&&) True [True,False,False] = True && foldr (&&) True [False,False] = foldr (&&) True [False,False] = False && foldr (&&) True [False] = False
(+) の場合とは違い、(&&) は第一式数のみを見て簡約することができるから、結局末尾再帰と同じになっている。しかも、False を見付けた時点でリストの走査を中止できる。
このように真理値を返す関数は、foldr の方が効率がよくなる場合があるので、注意が必要である。
