HaskellのFoldableはどこから来たのか?

lotzさんの[Data.Foldableの正体に迫る](https://qiita.com/lotz/items/424abee02fe598c60247)に触発されてこの記事を書きました。

Haskellで、リストなどへの畳み込み操作(ステップごとに結果を累積する計算)を一般化したものが`Foldable`クラスです。今回はそんな`Foldable`がどこからHaskellにやってきたのか、について焦点を絞りました。

lotzさんの記事にによると「*Crush*と呼ばれるものが原型になっているようです」とのことで、[論文](https://www.semanticscholar.org/paper/Calculate-Polytypically!-Meertens/dc0b060866747ee68b3c2d6bbe9f6b8510ee498e)をいざ読んでみたのですが、記号の意味を理解するのが精いっぱいでした…　そこで、この記事では概念というよりは「GHCとFoldableの関係」についてまとめました。

## 畳み込みとは?

前提知識として、畳み込みと`Foldable`型クラスについてある程度知っている必要があるので、軽く紹介します。

畳み込みの単純な例として、1~100までの総和を求める問題があります。数式ではこうです。
$$
\sum_{k=1}^{100}k = 1 + 2 + 3 + \dots + 99 + 100
$$
手続き型言語などではループを作って求めたりしますが、Haskellでは高階関数を使って畳み込みというアプローチを用います。プログラムとしては、

```haskell
sum [1..100] = 1 + 2 + 3 + ... + 99 + 100
```

Preludeには`sum`という関数がありますが、ここでは`foldl`を使ってリストを左から畳み込みます。

```haskell
Prelude> foldl (+) 0 [1..100]
5050
```

以上です。計算を分解すると、

```haskell
  foldl (+) 0 [1..100]
= foldl (+) (0 + 1) [2,3..100]
= foldl (+) ((0 + 1) + 2) [3,4..100]
= foldl (+) (((0 + 1) + 2) + 3) [4,5..100]
...
= (...(((0 + 1) + 2) + 3) + ...)
= 5050
```

さらに単純にすると、

```haskell
  0                  1,2,3,4,5, ... ,100
= (0 + 1)              2,3,4,5, ... ,100
= ((0 + 1) + 2)          3,4,5, ... ,100
= (((0 + 1) + 2) + 3)      4,5, ... ,100
...
= 5050
```

2引数関数をアキュムレータと呼ばれる最初の値と、リストの先頭に適用して値を得ます。これをリストの次の要素とともに再び関数に与えて…というのを繰り返して計算します。

このように、`foldl`はリストの左側から畳み込むので左畳み込み、逆に右側から畳み込む操作は右畳み込みと呼ばれます。

そして、`foldl`や`foldr`などが使える型をリストから一般化したのが`Foldable`です。

## Foldableクラス

`Foldable`は`Data.Foldable`で定義されています。

```haskell
class Foldable (t :: * -> *) where
  fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldMap' :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  foldr' :: (a -> b -> b) -> b -> t a -> b
  foldl :: (b -> a -> b) -> b -> t a -> b
  foldl' :: (b -> a -> b) -> b -> t a -> b
  foldr1 :: (a -> a -> a) -> t a -> a
  foldl1 :: (a -> a -> a) -> t a -> a
  toList :: t a -> [a]
  null :: t a -> Bool
  length :: t a -> Int
  elem :: Eq a => a -> t a -> Bool
  maximum :: Ord a => t a -> a
  minimum :: Ord a => t a -> a
  sum :: Num a => t a -> a
  product :: Num a => t a -> a
  {-# MINIMAL foldMap | foldr #-}
```

何やら関数がたくさんありますが、インスタンスにする際に必要なのは`foldMap`か`foldr`だけです。リストから累積する計算へ、数値演算からモノイドへと一般化されたのが畳み込みに特化した`Foldable`クラスです。

## Foldableはどこから来たのか?

ようやく本題です。`Data.Foldable`は、Ross Patersonという方が2005年にGHCに追加したそうなのですが、[HackageのbaseのVersions](https://hackage.haskell.org/package/base-4.14.0.0)の最も古い3.0.3.1にはすでに載っていて、ソースコードにも特に由来などの言及はされていません。

> -- Module      :  Data.Foldable
> -- Copyright   :  Ross Paterson 2005
>
> ...

そこで、まずはHaskellのレポート(98、2010)を調べました。

### レポートを読む

[Haskell 98のレポート](https://www.haskell.org/onlinereport/index98.html)には、`foldl`などの関数はリストの関数として定義されており、`Foldable`という型クラスはありません。

<img src="https://www.sampou.org/haskell/report-revised-j/classes.gif" alt="Diagram of standard Haskell classes"  />

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

[Haskell 2010](https://www.haskell.org/definition/haskell2010.pdf)にも`Foldable`という型クラスはなく、`fold`系の関数は全てリストへの関数になっています。

### baseパッケージのコミットログを見る

GitHubに、[baseパッケージのリポジトリのミラー](https://github.com/ghc/packages-base)があったので、タグを見てみます。

すると、2006年1月13日につけられた[`Initial_conversion_from_CVS_complete`というタグ](https://github.com/ghc/packages-base/releases/tag/Initial_conversion_from_CVS_complete)が初めて`Data.Foldable`が追加されたものであることが分かりました。さらに、`Data/Foldable.hs`のコミット履歴を探ると、`ross`というユーザの方が2005年11月にファイルを追加したことが判明しました。これのコメントによると、

> ​      [project @ 2005-11-29 14:31:59 by ross]    
>
> ```
> As foreshadowed on the libraries list, introduce new classes:
> 
> Applicative (formerly known as Idiom): generalizes (but does not replace)
> both Monad and Monoid.
> 
> Traversable: containers that can be traversed, executing actions and
> re-assembling the results.  This class generalizes and replaces FunctorM,
> because it requires Applicative instead of Monad.
> 
> Foldable: containers that can be folded over a Monoid.  Traversable
> supplies a default definition, but some structures, e.g. Set, are Foldable
> but not Traversable.
> ```

> ```
> ライブラリリストに予告されているように、新しいクラスを導入した:
> 
> Applicative (以前はIdiomとして知られていた): MonadとMonoidの両方を一般化する(置き換えはしない)
> 
> Traversable: 走査可能なコンテナ、アクションを実行して結果を累積する。このクラスはMonadの代わりにApplicativeが必要なため、FunctorMを一般化して置き換える。
> 
> Foldable: Monoidで畳み込めるコンテナ。Traversableのデフォルトの定義を提供するが、いくつかの構造、例えばSetはFoldableだがTraversableではない。
> ```

さらに、`ross`さんはこのコミットでいくつかのファンクタのインスタンス定義をFoldableで置き換えています。

例えば、`Map`、

```haskell
instance Foldable (Map k) where
  foldMap _f Tip = mempty
  foldMap f (Bin _s _k v l r)
    = foldMap f l `mappend` f v `mappend` foldMap f r
```

`Seq`などです。

```haskell
instance Foldable Seq where
	foldr f z (Seq xs) = foldr (flip (foldr f)) z xs
	foldl f z (Seq xs) = foldl (foldl f) z xs

	foldr1 f (Seq xs) = getElem (foldr1 f' xs)
	  where f' (Elem x) (Elem y) = Elem (f x y)

	foldl1 f (Seq xs) = getElem (foldl1 f' xs)
	  where f' (Elem x) (Elem y) = Elem (f x y)
```

[後のコミット](https://github.com/ghc/packages-base/commit/48ab7572ca03a4db931698d0e49d93e74c9f092e#diff-11f7638734143659a5baf609b39e9c16)によると、始めは`Data.Foldable`の関数は`Prelude`と重複していたようで、曖昧さを避けるためにアドバイスが追加されています。

実は、Haskell 2010はGHC7.0.1についてのレポートなので、`Foldable`が標準に追加されるのはその後のバージョンになるため、載っていませんでした。

> The current Haskell standard, Haskell 2010, was [announced](http://www.haskell.org/pipermail/haskell/2009-November/021750.html) at November 24th 2009; GHC supports it since revision 7.0.1. 
>
> \- [Haskell 2010 - Haskwll Wiki](https://wiki.haskell.org/Haskell_2010)

## まとめ

- `Foldable`クラスはGHCにHaskell 2010のあとに追加された比較的新しい型クラス

## 感想

GHCのコミットログを漁ったりして、ライブラリなどのツールを探るのも意外と興味深い体験でした。`Foldable`と`Monoid`には深い関係があるんだなと改めて感じました。