PR

concatMapを一般化するfoldMapメソッド

 では,それぞれのメソッドがどのように定義されているかを詳しく見ていきましょう。

 各メソッドのデフォルト定義からわかるように,foldMapメソッドは様々なfold*メソッドを組み立てる基になるものです。このメソッドは,foldrに「mappend . f」と「mempty」を引数として渡すように定義されています。mappendとmemptyはいずれも第29回で説明したMonoidクラスのメソッドです。

 「mappend . f」は何を意味しているのでしょうか。

 foldrが行うたたみこみ演算は,「Monoidクラスのインスタンスである型」を保証しません。このため,何も考えずにfoldrを使ってたたみこみ演算を行うと,「Monoidクラスのインスタンスである型」の値同士を結合するときとは異なる動作になる可能性があります。そこで「Monoidクラスのインスタンスである型」であることを保証するために,たたみこみ演算に「Monoidクラスのインスタンスである型」同士を結合する関数であるmappendを何らかの形で組み込む必要があります。mappendは「(Monoid b) => a -> a -> a」型の関数であるため,foldrにmappendを引数として渡すことが可能です。

 foldrを使ったたたみこみ演算は,引数としてmappendのような関数を渡すだけでは行えません。foldrはもう一つの引数として,たたみこみ演算の初期値を必要とします。Monoidクラスには空の値を表現するためのmemptyというメソッドが用意されているので,第2引数で渡す初期値としてmemptyを利用できます。

Prelude Data.Monoid> :t mappend
mappend :: (Monoid a) => a -> a -> a
Prelude Data.Monoid> :t Data.Foldable.foldr mappend
Data.Foldable.foldr mappend
  :: (Monoid a, Data.Foldable.Foldable t) => a -> t a -> a
Prelude Data.Monoid> :t Data.Foldable.foldr mappend mempty
Data.Foldable.foldr mappend mempty
  :: (Monoid a, Data.Foldable.Foldable t) => t a -> a

 foldrにmappendと初期値memptyを与えることで,「Foldableクラスのインスタンスである型」の要素から「Monoidクラスのインスタンスである型」を求めるメソッド,すなわちfoldを作れます。

Prelude Data.Monoid> :t Data.Foldable.fold
Data.Foldable.fold
  :: (Data.Foldable.Foldable t, Monoid m) => t m -> m

 foldがどんな演算であるかを考えるために,foldを具体的な型に対して適用した場合を考えてみましょう。先ほど説明したように,リストはFoldableクラスのインスタンスの一つとして定義されています。また,第29回で説明したように,リストはMonoidクラスのインスタンスとしても定義されています。

instance Foldable [] where
~ 略 ~

instance Monoid [a] where
        mempty  = []
        mappend = (++)

 そこで「foldr mappend mempty」のfoldrをPreludeのfoldr,mappendとmemptyをそれぞれリストに対するインスタンスの定義に用いられている「++」と[ ]に置き換えてみましょう。結果は以下のような型になります。

Prelude> :t foldr (++) []
foldr (++) [] :: [[a]] -> [a]

 これは実はリストを結合するconcat関数と同じ定義となっています。

concat :: [[a]] -> [a]
concat = foldr (++) []

 このことから,foldはconcatを「Foldableクラスのインスタンスである型」と「Monoidクラスのインスタンスである型」に一般化することがわかります。

 foldMapのデフォルト定義である「foldr (mappend . f) mempty」の説明に戻りましょう。

 「foldr mappend mempty」という式が行う演算には問題が一つあります。このような定義では,foldrやfoldMapの目的である「関数fを使ったたたみこみ演算」を行うことはできません。そこでfoldMapでは「関数fを適用した結果」を利用するために,関数fを適用してその後mappendを適用するという順で関数fとmappendを合成します。

 関数合成演算子「.」の型は「(b -> c) -> (a -> b) -> a -> c」です。

Prelude Data.Monoid> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

 「.」の第1引数に「(Monoid b) => a -> a -> a」型の関数であるmappendを与えると,型は以下のように単一化されます。

    (b -> c) -> (a -> b) -> a -> c
==> { 第1引数に(Monoid a) => a -> a -> a型の関数を与えたため,
      Monoid bの文脈を付けて cにb->bを代入 }
    (Monoid b) => (b -> (b -> b)) -> (a -> b) -> a -> (b -> b)
==> (Monoid b) => (b -> b -> b) -> (a -> b) -> a -> b -> b
==> { 第1引数の関数b -> b -> bを取り除く }
    (Monoid b) => (a -> b) -> a -> b -> b

 この結果,「mappend .」の型は「(Monoid b) => (a -> b) -> a -> b -> b」になり,「(Monoid b) => (a -> b) 」型の関数fと合成できるようになります。

Prelude Data.Monoid> :t (mappend .)
(mappend .) :: (Monoid b) => (a -> b) -> a -> b -> b
Prelude Data.Monoid> :t (\f -> mappend . f)
(\f -> mappend . f) :: (Monoid b) => (a -> b) -> a -> b -> b

 このようにして,関数fを適用した結果同士をmappendを使って結合する式「mappend . f」ができあがります。

 「\f -> Data.Foldable.foldr (mappend . f)」に初期値memptyを与えることで,最終的に「Monoidクラスのインスタンスである型」を返す関数であるfoldMapを定義できます。

Prelude Data.Monoid> :t \f -> Data.Foldable.foldr (mappend . f)
\f -> Data.Foldable.foldr (mappend . f)
  :: (Monoid b, Data.Foldable.Foldable t) =>
     (a -> b) -> b -> t a -> b
Prelude Data.Monoid> :t \f -> Data.Foldable.foldr (mappend . f) mempty
\f -> Data.Foldable.foldr (mappend . f) mempty
  :: (Monoid b, Data.Foldable.Foldable t) => (a -> b) -> t a -> b

 ここでfoldMapとconcatとの関係を考えてみましょう。「\f -> Data.Foldable.foldr (mappend . f)」のfoldrをPreludeのfoldr,mappendを「++」,memptyを[ ]に書き換えると,結果は以下のようになります。

Prelude> :t \f -> foldr ((++) . f) []
\f -> foldr ((++) . f) [] :: (a1 -> [a]) -> [a1] -> [a]

 リスト内の各要素に対して「a1 -> [a]」型の関数fを適用した後,concatを行う,という定義になっています。これを一般的なconcatとmapの関数合成で書けば,第4回で紹介したconcatMapの定義になります。

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = concat . map f

 foldがconcatを一般化するように,foldMapはconcatMapを一般化する関数なのです。実際にGHCのconcatMapは,関数合成ではなく,上に示したようにfoldrを利用する形で定義されています(参考リンク)。

concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

 foldMapをconcatMapに変換したのとは逆に,GHCのconcatMapの定義をfoldrとmappend,memptyを使って一般化すれば,foldMapになります。foldMapは単に他のfold*を定義するための関数ではなく,concatMapを「Foldableクラスのインスタンスである型」と「Monoidクラスのインスタンスである型」に一般化したものだったのです。

 今度はfoldのデフォルト定義を考えてみましょう。

 先ほどはfoldrを使ってfoldを定義しましたが,抽象化を考えると様々なfoldの基礎になるfoldMapを使ってfoldを定義するほうがよいでしょう。

 しかし,foldMapを使ってfoldを定義するには問題が一つあります。concatを一般化する方法では,foldは「foldr mappend mempty」と定義されていました。一方,concatMapを一般化したfoldMapの定義は「foldr (mappend . f) mempty」です。したがって,foldMapからfoldを求めるには余分な関数fを何らかの形で消去する必要があります。

 この用途に適しているのが,恒等関数であるidです。idは引数をそのまま返すため,関数とidを合成しても,結果はその関数そのものです。

Prelude> id 2
2
Prelude> (+) 2 9
11
Prelude> (id . (+)) 2 9
11
Prelude> ((+) . id) 2 9
11

 したがって,mappendと合成する関数fとしてidを渡すことで,fを消去できます。

Prelude Data.Monoid> :t (mappend . id)
(mappend . id) :: (Monoid a) => a -> a -> a
Prelude Data.Monoid> :t Data.Foldable.foldr (mappend . id) mempty
Data.Foldable.foldr (mappend . id) mempty
  :: (Monoid a, Data.Foldable.Foldable t) => t a -> a

 foldMapでは,mappendと合成する関数fを引数として与えます。つまり,foldMapにidを与えれば「mappend . f」の部分がmappendだけになり,foldMapを使ってfoldを定義できます。

fold :: (Foldable t, Monoid m) => t m -> m
fold = foldMap id