第34回　様々なデータ構造でfoldを使えるようにするFoldableクラス

foldの派生系を定義する

　残るはfoldr1メソッドとfoldl1メソッドです。それぞれfoldrとfoldlを使って以下のように定義されています。

foldr1 :: (a -> a -> a) -> t a -> a
foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                (foldr mf Nothing xs)
  where mf x Nothing = Just x
        mf x (Just y) = Just (f x y)

～ 略 ～

foldl1 :: (a -> a -> a) -> t a -> a
foldl1 f xs = fromMaybe (error "foldl1: empty structure")
                (foldl mf Nothing xs)
  where mf Nothing y = Just y
        mf (Just x) y = Just (f x y)

　foldr1やfoldl1は，foldrやfoldlで必要な初期値を与えなくても済むようにするために，mf関数を定義して利用しています。mfは，計算された値をJustに包んで返すだけの関数です。mf関数は，データ構造から要素を取り出す前の「何も要素を取り出していない状態」をNothingで表現しています。mf関数は「何も要素を取り出していない状態」から「1番目の要素を取り出した状態」に遷移する場合には，1番目の要素を単にJustに包んで返します。mfとNothingを用いることで，foldr1やfoldl1は初期値を省略できるのです。

　ただし，mfの結果はMaybe型なので，foldr1やfoldl1に求められる処理を行うためにはMaybe型から要素を取り出す必要があります。これを行うのがData.MaybeモジュールのfromMaybe関数です。

fromMaybe     :: a -> Maybe a -> a
fromMaybe d x = case x of {Nothing -> d;Just v  -> v}

　fromMaybeは，第2引数として渡された値がNothingである場合には第1引数，第2引数として渡された値がJustである場合にはその中身を取り出して返します。foldr1やfoldl1は，第2引数がNothingである場合にはerror関数を使うことで，データ構造が空であることを示すメッセージとともに例外を発生します。

　Data.Foldableモジュールには，Foldableクラスのメソッドとして定義されているもののほかに，foldlとfoldrの派生系の関数がいくつか定義されています。

　その一つが，第9回で紹介したfoldlの正格評価版であるfoldl'です。同様にfoldrの正格評価版であるfoldr'もあります。

　第9回で紹介したfoldl'では，foldlの中身を直接書き換えて，関数fを評価した後に再帰をたどるようにしていました。しかし，Data.Foldableモジュールのfoldr'やfoldl'はFoldableクラスのメソッドではないので、内部の操作を直接書き換えることはできません。そこで，関数fを正格適用させるための関数f'をfoldrやfoldlに渡すことにします。このような考えに基づくと，foldr'とfoldl'の定義は以下のようになります。

-- | Fold over the elements of a structure,
-- associating to the right, but strictly.
foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr' f z0 xs = foldl f' id xs z0
  where f' k x z = k $! f x z

～ 略 ～

-- | Fold over the elements of a structure,
-- associating to the left, but strictly.
foldl' :: Foldable t => (a -> b -> a) -> a -> t b -> a
foldl' f z0 xs = foldr f' id xs z0
  where f' x k z = k $! f z x

　foldr'やfoldl'では，関数fを正格に適用させるために三つのしかけを使っています。最初のしかけは，f'の定義に使われている正格適用演算子$!です。二つ目に，恒等関数idを使ってf'をid $! f ...と直接定義するのではなく，k $! f ...と定義して後からidを渡すことで，再帰的にid $! f ...が展開されるようにしています。

　三つ目に，foldr'をfoldl，foldl'をfoldrで定義しています。関数fを正格に適用しても，関数fが呼ばれるタイミングが適切でなければ正格評価を行うfoldrやfoldlを作ることはできません。正格評価版のfoldlを作ろうとした場合，通常の遅延評価を行うfoldlはこの問題のために利用できません。リストなどの具体的なデータ構造を使って評価してみればわかりますが，遅延評価版のfoldlと正格評価版のfoldlとでは関数fを呼ぶタイミングが異なります。

　リストに対して遅延評価版のfoldlと正格評価版のfoldlを適用し，実際に比べてみましょう。遅延評価を行うPreludeのfoldlと，正格評価を行うData.Listのfoldl'の定義はそれぞれ以下の通りです。

foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs

foldl'           :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

　Preludeのfoldlでは「foldlを呼び出してその中で関数fを呼んでいる」のに対し，Data.Listのfoldl'では「foldl'の外側で関数fを呼び出している」のがわかります。foldlの内側で関数fを呼び出す遅延評価版のfoldlでは，関数fの呼び出しはfoldlが展開されるまで持ち越されます。関数fにいくら正格適用のための仕組みを組み込んでも，関数f自体が呼び出されなければ評価は始まりません。一方，foldl'ではfoldl'の外側で関数fを呼び出しているため，foldlを展開する前に関数fが呼ばれて評価されます。

　このように遅延評価版のfoldlと正格評価版のfoldlでは関数fを呼ぶタイミングが異なっているため，評価順序に決定的な違いが生じます。結果として，遅延評価を行う通常のfoldlを使って正格評価版のfoldlを作成することはできないのです。

　では，どうすればよいでしょうか？

　実は，遅延評価版のfoldrと正格評価版のfoldlの振る舞いはよく似ています。リストに対して定義されたPreludeのfoldrを見てみましょう。

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

　foldrの外側で関数fが呼ばれているため，foldrを展開しなくても関数fが評価されます。

　このように，正格評価版のfoldlが関数fを呼び出すタイミングは，遅延評価版のfoldrと同じです。これを利用してData.Foldableでは遅延評価版のfoldrを使って正格評価を行うfoldl'を定義しているのです（参考リンク1，参考リンク2）。

　こうした事実から，正格評価版のfoldr'と遅延評価版のfoldl，正格評価版のfoldl'と遅延評価版のfoldrは，それぞれ双対の関係になっていると考えられます（参考リンク）。

　都合のよいことに，f'をfoldrやfoldlに渡す際にはflipを使用する必要はありません。f'は元の関数fとは引数の順番が入れ替わるからです。foldr'で使われているf'の型を見てみましょう。

Prelude> let f x y = y
Prelude> :t f
f :: t -> t1 -> t1
Prelude> let f' k x z = k $! f x z
Prelude> :t f'
f' :: (t1 -> b) -> t -> t1 -> b

　型は右結合なので，f'の型は「(t1 -> b) -> t -> (t1 -> b)」とも表せます。（t1 -> b）を型変数aで置き換えれば，f'の型は「a -> t -> a」になります。fの型である「t -> t1 -> t1」を「t -> a -> a」と考えると，引数の順序が逆になっていることがわかります。

　foldl'で使われているf'も同様です。

Prelude> let f x y = x
Prelude> :t f
f :: t -> t1 -> t
Prelude> let f' x k z = k $! f z x
Prelude> :t f'
f' :: t1 -> (t -> b) -> t -> b

　Data.Foldableモジュールには，foldrやfoldlをモナド上で行うfoldrMとfoldlMも用意されています。これらもfoldr'やfoldl'と同様の方法で実装されています。

-- | Monadic fold over the elements of a structure,
-- associating to the right, i.e. from right to left.
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
foldrM f z0 xs = foldl f' return xs z0
  where f' k x z = f x z >>= k

～ 略 ～

-- | Monadic fold over the elements of a structure,
-- associating to the left, i.e. from left to right.
foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m a
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

　これらの関数のf'では，>>=を使って計算をつないていくことで，foldrやfoldlをモナド上の計算として展開しています。ただし，f'の定義は「f x z >>= k」のように「関数fを実行した後，kを実行する」という形式になっています。関数f'が関数fを使用したときと実行内容や結果が変わらないことを保証するには，何も実行せずに前に実行した式と同じ結果を返す「k」を与える必要があります。

　ただし，foldr'やfoldl'で使ったidは，この場合のkとしては不適切です。「>>=」の第2引数の型は「(Monad m) => a -> m b」であり，idの型である「a -> a」とは異なるからです。idではなくモナド上でidに相当する関数をkとして与えなければなりません。

　モナド上でidに相当する関数は，第3回で説明したモナド則にあります。モナド則ではMonoadクラスのインスタンスは「m >>= return == m」になるように定められています。したがって，関数f'を関数fと同じように振る舞わせるには，kとしてreturnを渡せばよいことになります。