あどけない話

インターネットに関する技術的な話など

右も左も分かる再帰

函数プログラミングの集い」のチュートリアル資料を作成するためのメモ。リストに対する再帰を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 の方が効率がよくなる場合があるので、注意が必要である。