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

lotzさんのData.Foldableの正体に迫るに触発されてこの記事を書きました。

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

lotzさんの記事にによると「Crushと呼ばれるものが原型になっているようです」とのことで、論文をいざ読んでみたのですが、記号の意味を理解するのが精いっぱいでした…　そこで、この記事では概念というよりは「GHCとFoldableの関係」についてまとめました。

畳み込みとは?

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

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

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

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

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

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

  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

さらに単純にすると、

  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で定義されています。

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の最も古い3.0.3.1にはすでに載っていて、ソースコードにも特に由来などの言及はされていません。

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

...

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

レポートを読む

Haskell 98のレポートには、foldlなどの関数はリストの関数として定義されており、Foldableという型クラスはありません。

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

Haskell 2010にもFoldableという型クラスはなく、fold系の関数は全てリストへの関数になっています。

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

GitHubに、baseパッケージのリポジトリのミラーがあったので、タグを見てみます。

すると、2006年1月13日につけられた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、

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などです。

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)

後のコミットによると、始めはData.Foldableの関数はPreludeと重複していたようで、曖昧さを避けるためにアドバイスが追加されています。

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

The current Haskell standard, Haskell 2010, was announced at November 24th 2009; GHC supports it since revision 7.0.1.

- Haskell 2010 - Haskwll Wiki

まとめ

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

感想

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