Data.Foldableの正体

リストにおいて `foldr` は最も基本的な関数と言えるでしょう。例えば関数型プログラミングでは欠かせない`map`や`filter`といった関数は

```hs
map :: (a -> b) -> [a] -> [b]
map f = foldr (\a bs -> f a : bs) []

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\a as -> if p a then a : as else as) []
```

というように`foldr`を使って実装することができます。

この `foldr` をリストだけではなく他のデータ構造にも一般化しようという試みの一つにRecursion Schemesがあります。Recursion Schemesの一つであるCatamorphismはF始代数から伸びる唯一の射であり、特に `foldr` は

```hs
data ListF a r = Nil | Cons a r
               deriving Functor
```

というような Functor `ListF` の Catamorphism とみなすことができます[^4]。

もう一つ、`foldr`を一般化する方法としてHaskellの標準ライブラリであるbaseに実装されている型クラス`Foldable`があります。

```hs
class Foldable t where
    {-# MINIMAL foldMap | foldr #-}

    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

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

`{-# MINIMAL foldMap | foldr #-}` は `foldMap`[^7] もしくは `foldr` のいずれかを定義すれば `Foldable` のインスタンスを作ることが出来るということを示すためのプラグマです。つまり `Foldable` はデータ型ごとにアドホックな `foldr` を定義できるようにした一般化といえるでしょう。

僕は今まで `Foldable` に関して２つの疑問を抱いていました。1つは `Foldable` のインスタンスは `foldr` ではなく `foldMap` を実装することで定義することが出来るが[^8]、こっちは型に `Monoid` の制約が現れていて気持ち悪い。もう一つはCatamorphismも `Data.Foldable` も `foldr` の一般化ですが両者はどういう関係なのか。特にRecursion Schemesがある関手の始代数・終余代数と特徴づけられる一方で`Data.Foldable`に数学的な背景が存在するのか。

Data.Foldableの正体に迫る
-----------------------

`Data.Foldable`について歴史的な背景を探ろうとしましたがGHCのコミット履歴を見ても`Foldable`がどこから来たのかを示す記録はありませんでした[^1]。しかし以下の記事を見つけて僕の疑問が一気に解決しました。

[The Comonad.Reader » Free Monoids in Haskell](http://comonad.com/reader/2015/free-monoids-in-haskell/)

曰く

* Haskellにおいてリストは厳密には自由モノイドではない
* Haskellでは等式制約や商集合を扱うことができないので自由モノイドを実装することはできない
* しかしもし `a` の自由モノイド `FM a` が存在すれば任意のモノイド `m` への埋め込み `a -> m` に対してモノイド準同型 `FM a -> m` が存在するということをモデル化することができる
* `Foldable` の最も基本的な関数は `toFreeMonoid` 

3つ目の条件は `FM` に対して

```hs
forall m. Monoid m => (a -> m) -> FM a -> m
```

という型の関数を定義することでモデル化することができるということです。

ここで手元のAwodey（赤青色の圏論の本ですね）をめくってみると数学的な自由モノイドの定義は

集合 $A$ が与えられた時に$M(A)$ が $A$ の自由モノイドであるとは、 $A$ から $M(A)$ の台集合[^2] $|M(A)|$ への写像 $i : A \rightarrow |M(A)|$ が存在して、任意のモノイド $N$ と $A$ から $N$ の台集合 $|N|$ への写像 $f : A \rightarrow |N|$ が与えられた時に、 $M(A)$ から $N$ へのモノイド準同型 ${\bar f}$ が唯一つ存在して、その台集合上の写像 $\left|{\bar f}\right|$ に対して $\left|{\bar f}\right| \circ i = f$ が成り立つようなものである。

と大体書いてあります。つまり（ざっくりいうと）集合 $A$ から任意のモノイド $N$ への写像 $f$ が与えられた時に、 $A$ の自由モノイド $M(A)$ から $N$ へのモノイド準同型で以下の可換図式を可換にするようなもの $|{\bar f}|$ が唯一つ存在するということです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/9b49d555-c1a0-a62b-c2ea-516058fd150c.png" width=300 />

この性質をHaskellの関数（の型）として書き下すと

```hs
forall m. (a -> m) -> FM a -> m
```

となります。ここで `FM` は `a` の自由モノイドを対応付ける関手（Functor）と考えることができます。この型は

```hs
forall m. FM a -> (a -> m) -> m
```

と同型であり、ここから

```hs
newtype FM a = FM { unFM :: forall m. Monoid m => (a -> m) -> m }
```

というように `FM` の型の定義を考えることができます（ちなみに`unFM`の型が `forall m. FM a -> (a -> m) -> m` となります）。この `FM a` が自由モノイドであることを確かめるために `a` から `FM a` への関数 `embed` [^6]と `Monoid` のインスタンスを定義してみましょう。

```hs
embed :: a -> FM a
embed x = FM $ \k -> k x
 
instance Monoid (FM a) where
  mempty = FM $ \_ -> mempty
  mappend (FM e1) (FM e2) = FM $ \k -> e1 k <> e2 k
```

以上より `FM a` $\cong$ `Monoid m => (a -> m) -> m` が `a` の自由モノイドの型であることが大体分かりました。（2019/04/21追記: [コメントい](https://qiita.com/lotz/items/424abee02fe598c60247#comment-1b7a7d0f25c9662d6555)ただいたように自由モノイドであることを主張するためにはモノイドであることを確かめるだけでは不十分で`flip unFM f`の唯一性を証明する必要があります。）

さて `Data.Foldable` に戻りましょう。 `foldMap` の型は

```hs
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
```

であり、引数の順番を入れ替えると、

```hs
foldMap :: (Foldable t, Monoid m) => t a -> (a -> m) -> m
```

これはまさに`Foldable`のインスタンスから自由モノイドに変換する関数に他なりません。つまり`Foldable`とは自由モノイドに変換できるような型のことだったのです[^3]。

まとめ
-----
僕が`Foldable`に対して抱いていた疑問は解決しました。今となっては `foldr` よりもむしろ `Monoid` 制約のついた `foldMap` のほうが `Foldable` にとって本質的な関数に見えます。そして`Foldable`は自由モノイドへの自然変換を備えた関手であるという数学的な見方もできるようになりました[^8]。これで明日から自身を持って `Foldable` に向き合えるようになり、夜もぐっすりと眠れるようになりそうです :relaxed:

追記: 2019/04/18
---------------
[Haskell-jp](https://haskell.jp/)のSlackで @kazu_yamamoto さんより、 [Programming in Haskell 2nd Edition](https://www.amazon.co.jp/dp/B01JGMEA3U) にFoldableの起源についての言及が載っていると教えていただきました。どうやら["Calculate Polytypically!"](https://www.semanticscholar.org/paper/Calculate-Polytypically!-Meertens/dc0b060866747ee68b3c2d6bbe9f6b8510ee498e)という論文の _Crush_ と呼ばれるものが Foldableの原型となっているようです。さらに読んでみると"9 Crush compared to cata"という章があり、Catamorphismとの関係が議論されていました。ただどうもFoldableの抽象化はGeneric Programmingに近いものでCatamorphismとの関係はあまり無さそうです。

[^1]: `Data.Foldable`がどこからどういう経緯でGHCに取り込まれたのか知ってる人がいたら教えてください :pray:
[^2]: モノイド $M$ の台集合 $|M|$ とは $M$ から単純にモノイドの構造を忘れ去った集合です。なので演算が忘れられただけで要素は元のモノイドと等しい集合になります。
[^3]: つまり`Foldable`とは自由モノイドを与える関手への自然変換を備えた関手のことだったのです[^9]。
[^4]: http://hackage.haskell.org/package/recursion-schemes-5.1.2/docs/Data-Functor-Foldable.html#t:ListF
[^6]: 元々 $i : A \rightarrow |M(A)|$ と書いてたやつです
[^7]: `foldMap` についてはこちらが分かりやすいです。 [圏論勉強会第2回@ワークスアプリケーションズ#プログラミングにおけるモノイド](http://nineties.github.io/category-seminar/2.html#/19)
[^8]: `foldr` と `foldMap` の関係についてはこちらが分かりやすいです。 [FoldableクラスがfoldMapからfoldrを構成する流れ](http://enakai00.hatenablog.com/entry/20131105/1383714391)
[^9]: 追記: 2019/4/22 あれ、でも `Foldable` は `Functor` を要請していないので自由モノイドに変換できる型という理解が正しいですね。 `toFreeMonoid` を備えた型ということで。