PR

foldMapでfoldrとfoldlを定義する

 次にfoldMapメソッドを使って実装されるfoldrメソッドとfoldlメソッドのデフォルト定義を説明します。

foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

~ 略 ~

foldl :: (a -> b -> a) -> a -> t b -> a
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

 foldlのデフォルト定義は,foldrのデフォルト定義に関数の適用をいくつか追加した形になっています。foldrとfoldlのデフォルト定義は似ているので,どちらかを理解すればもう片方も容易に理解できます。まず,より単純なfoldrの定義を説明しましょう。

 foldrのデフォルト定義で使われているEndoは,「自己射(endomorphism)」と呼ばれる「a -> a」型の関数を表現します。Monoidクラスのインスタンスで,Endo型は「a -> a」型の関数同士を合成する役割を果たします(参考リンク1参考リンク2)。

-- | The monoid of endomorphisms under composition.
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

 この連載では明確には示していませんでしたが,Haskellではデータ構成子も「引数を取って型を返す関数」として扱います(参考リンク1参考リンク2)。このため,Endo型のデータ構成子も関数合成の対象にできます。

 Endoデータ構成子と関数合成を行う場合の型を見てみましょう。Endoデータ構成子の型は以下の通りです。

Prelude Data.Monoid> :t Endo
Endo :: (a -> a) -> Endo a

 「.」の第1引数にEndoデータ構成子を「(a -> a) -> Endo a」型の関数として与えると,型は以下のように単一化されます。

    (b -> c) -> (a -> b) -> a -> c
==> { 第1引数に(a -> a) -> Endo aが与えられたため,
     bにb->bを代入,cにEndo bを代入 }
    ((b -> b) -> Endo b) -> (a -> (b -> b)) -> (a -> Endo b)
==> ((b -> b) -> Endo b) -> (a -> b -> b) -> (a -> Endo b)
==> { 第1引数に渡したEndoデータ構成子関数の型「(b -> b) -> Endo b」を取り除く }
    (a -> b -> b) -> a -> Endo b

 結果の型からわかるように,Endoを「.」の第1引数として与えた場合,「.」の第2引数して要求される関数fは「a -> b -> b」という型を持つものになります。これはfoldrが要求する関数fの型「a -> b -> b」と同じです。また,Endoデータ構成子との関数合成は,関数fだけではなく,b型の値を追加の引数として要求することになります。このb型の引数が,foldrで行うたたみこみ演算の初期値になります。

Prelude Data.Monoid> :t (Endo .)
(Endo .) :: (a -> a1 -> a1) -> a -> Endo a1
Prelude Data.Monoid> :t \f -> Endo . f
\f -> Endo . f :: (a1 -> a -> a) -> a1 -> Endo a

 では,Endoデータ構成子と合成した関数「Endo . f」をfoldMapに与えてみましょう。EndoはMonoidクラスのインスタンスなので,「Endo . f」はfoldMapが要求する「Monoid m => (a -> m)」型の関数として渡せます。Endoデータ構成子関数はfoldMapが要求する制約を満たすので,Endoと合成する関数fにはMonoidクラスのインスタンスであるという文脈は必要ありません。この結果,foldMapに「Endo . f」を与えて作成した関数は,foldrが要求する関数と同じように制約のない「a -> b -> b」型の関数を引数として取ります。

Prelude Data.Monoid Data.Foldable> :t foldMap (Endo .)
foldMap (Endo .)
  :: (Foldable t) => t (a -> a1 -> a1) -> a -> Endo a1
Prelude Data.Monoid Data.Foldable> :t \f -> foldMap (Endo . f)
\f -> foldMap (Endo . f)
  :: (Foldable t) => (a1 -> a -> a) -> t a1 -> Endo a
Prelude Data.Monoid Data.Foldable> :t \f t -> foldMap (Endo . f) t
\f t -> foldMap (Endo . f) t
  :: (Foldable t) => (a1 -> a -> a) -> t a1 -> Endo a

 appEndoフィールドを使ってEndo型から値を引き出し,引数の順序を入れ替えれば,最終的にfoldr関数ができあがります。

Prelude Data.Monoid Data.Foldable> :t \f t -> appEndo (foldMap (Endo . f) t)
\f t -> appEndo (foldMap (Endo . f) t)
  :: (Foldable t) => (a1 -> a -> a) -> t a1 -> a -> a
Prelude Data.Monoid Data.Foldable> :t \f z t -> appEndo (foldMap (Endo . f) t) z
\f z t -> appEndo (foldMap (Endo . f) t) z
  :: (Foldable t) => (a1 -> a -> a) -> a -> t a1 -> a

 次にfoldlのメソッドの定義を見ましょう。

foldl :: (a -> b -> a) -> a -> t b -> a
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

 foldlではflipを使って関数fの引数を入れ替えています。これにより,関数fはfoldlで求められる「a -> b -> a」型になります。

Prelude Data.Monoid Data.Foldable> :t \f -> foldMap (Endo . flip f)
\f -> foldMap (Endo . flip f)
  :: (Foldable t) => (c -> a -> c) -> t a -> Endo c
Prelude Data.Monoid Data.Foldable> :t \f z t -> appEndo (foldMap (Endo . flip f) t) z
\f z t -> appEndo (foldMap (Endo . flip f) t) z
  :: (Foldable t) => (c -> a -> c) -> c -> t a -> c

 ただし,引数を入れ替えるだけでは,foldrからfoldlに変換することはできません。式の評価順序が違うからです。そこでfoldrとfoldlの間に成り立つ双対定理(duality theorem)を利用します。定理は以下の通りです。

  1. foldr f a xs == foldr (flip f) a (reverse xs)

 この定理を詳しく知りたい方は,「Introduction to Functional Programming using Haskell second edition」の4.6.1節,あるいは初版の訳書である「関数プログラミング」の3.5.1節を読んでください。

 ここで使用しているreverseは,リストやSeq型に対するreverseと同様に,データ構造内の要素を逆順にする関数です。

 上の双対定理から「foldMapの対象であるデータ構造内の要素を逆順にする操作」または「データ構造の要素を逆順に取り出す操作」があればfoldlを作成できることがわかります。しかし,すべてのデータ構造に対してこうした操作が提供されている保証はありません。そこで,要素を逆順にする代わりに,関数fに値を適用する順序を入れ替えて逆順にすることにします。このために用いるのが「Dual型」です。

 Dual型は,Monoidクラスで「双対(dual,duality)」を表現するものです(参考リンク)。双対には様々な意味がありますが,ここでは「Monoidクラスでの双対とは何か」を考える必要があります。その解答はDual型のMonoidクラスに対するインスタンスの定義にあります。

-- | The dual of a monoid, obtained by swapping the arguments of 'mappend'.
newtype Dual a = Dual { getDual :: a }
        deriving (Eq, Ord, Read, Show, Bounded)
instance Monoid a => Monoid (Dual a) where
        mempty = Dual mempty
        Dual x `mappend` Dual y = Dual (y `mappend` x)

 Dual型のインスタンスは,Monoid型のインスタンスである型aに対してmappendを逆順に適用するよう定義されています。すなわち,Dual型が表す双対は「mappendを使った演算の順番を逆にするよう変換するもの」です。

 Dual型でEndo型を包むようにDualデータ構成子関数を使って関数合成することで,foldMapの中でmappendによって行う処理の順番が逆になります。これにより,関数fを逆順に適用する処理を記述できるのです。

Prelude Data.Monoid Data.Foldable> :t \f -> foldMap (Dual . Endo . flip f)
\f -> foldMap (Dual . Endo . flip f)
  :: (Foldable t) => (c -> a -> c) -> t a -> Dual (Endo c)
Prelude Data.Monoid Data.Foldable> :t \f t -> foldMap (Dual . Endo . flip f) t
\f t -> foldMap (Dual . Endo . flip f) t
  :: (Foldable t) => (c -> a -> c) -> t a -> Dual (Endo c)

 最後にgetDualを使ってDualからEndoを取り出し,appEndoを使ってEndoから値を取り出して,foldrと同様に引数の順序を入れ替えます。これによりfoldlが完成します。

Prelude Data.Monoid Data.Foldable> :t \f t -> getDual (foldMap (Dual . Endo . flip f) t)
\f t -> getDual (foldMap (Dual . Endo . flip f) t)
  :: (Foldable t) => (c -> a -> c) -> t a -> Endo c
Prelude Data.Monoid Data.Foldable> :t \f t -> appEndo (getDual (foldMap (Dual . Endo . flip f) t))
\f t -> appEndo (getDual (foldMap (Dual . Endo . flip f) t))
  :: (Foldable t) => (c -> a -> c) -> t a -> c -> c
Prelude Data.Monoid Data.Foldable> :t \f z t -> appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
\f z t -> appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
  :: (Foldable t) => (c -> a -> c) -> c -> t a -> c

 このように,foldlの定義には「foldrとfoldlの間にある双対定理」と「Dual型によって定義されるmappendの双対」の二つの双対が使われています。双対という概念は,一般に「二つの対象の裏返し関係」を意味します。様々な分野で使われる概念なので,覚えておくとよいでしょう。