データ構造の中のすべての要素にアクセスする高階関数には，個々の要素ごとに関数を適用するmapと，すべての要素を使って計算を行うfoldの大きく二つがあります（参考リンク1，参考リンク2）。第3回で説明したように，mapは様々なデータ構造で利用できるようFunctorクラスを使って一般化されています。実は，foldも様々なデータ型に対して扱えるよう型クラスを使って一般化されています。
foldを一般化するFoldableクラスは，baseパッケージのData.Foldableモジュールで用意されています。今回はFoldableクラスについて説明します。
Foldableクラスで定義されているメソッド
foldには，第7回で紹介したfoldrと第9回で説明したfoldlの二つがあります。Foldableクラスには，foldrメソッドとfoldlメソッドの両方が存在します。加えて，様々なfold*メソッドを組み立てる基になるfoldMap，「Foldableクラスのインスタンスである型」の要素から「Monoidクラスのインスタンスである型」の値を求めるfold，foldrの初期値を省略できるfoldr1，foldlの初期値を省略できるfoldl1の計六つのメソッドが用意されています。
fold*メソッドには注意点があります。fmapの場合には，Functorクラスにしかないため，fmapと書けばメソッドを一意に特定できました。ところが，foldr，foldl，foldr1，foldl1はPreludeの関数としても用意されています。今回，単にfoldrやfoldlなどと表記している場合は，Foldableクラスのメソッドを指すと思ってください。
さて，Foldableクラスのインスタンスを提供するにはどうすればよいでしょうか？ それを知るために，Foldableクラスのメソッドのデフォルト定義を見てみましょう。
class Foldable t where
-- | Combine the elements of a structure using a monoid.
fold :: Monoid m => t m -> m
fold = foldMap id
-- | Map each element of the structure to a monoid,
-- and combine the results.
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
-- | Right-associative fold of a structure.
--
-- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z
-- | Left-associative fold of a structure.
--
-- @'foldl' f z = 'Prelude.foldl' f z . 'toList'@
foldl :: (a -> b -> a) -> a -> t b -> a
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
-- | A variant of 'foldr' that has no base case,
-- and thus may only be applied to non-empty structures.
--
-- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@
foldr1 :: (a -> a -> a) -> t a -> a
foldr1 f xs = fromMaybe (error "foldr1: empty structure")
(foldr mf Nothing xs)
where mf x Nothing = Just x
mf x (Just y) = Just (f x y)
-- | A variant of 'foldl' that has no base case,
-- and thus may only be applied to non-empty structures.
--
-- @'foldl1' f = 'Prelude.foldl1' f . 'toList'@
foldl1 :: (a -> a -> a) -> t a -> a
foldl1 f xs = fromMaybe (error "foldl1: empty structure")
(foldl mf Nothing xs)
where mf Nothing y = Just y
mf (Just x) y = Just (f x y)Foldableクラスのメソッドにはすべてデフォルトの定義が存在し，それらの定義はすべてFoldableクラスの別のメソッドを使って実装されています。例えば，foldr1はfoldrを使って実装されています。同様に，foldl1はfoldl，foldrおよびfoldlはfoldMap，foldもfoldMap，foldMapはfoldrを使って実装されています。foldrとfoldMapのデフォルト定義の間には循環関係があります。つまり，foldrかfoldMapのいずれかを実装すれば，新しいFoldableクラスのインスタンスを定義することが可能です。
インスタンスの例を見ましょう。Data.Foldableモジュールでは，Maybeやリスト，配列といったHaskell 98で定義されているデータ構造に対するインスタンスが定義されています。
-- instances for Prelude types
instance Foldable Maybe where
foldr _ z Nothing = z
foldr f z (Just x) = f x z
foldl _ z Nothing = z
foldl f z (Just x) = f z x
instance Foldable [] where
foldr = Prelude.foldr
foldl = Prelude.foldl
foldr1 = Prelude.foldr1
foldl1 = Prelude.foldl1
instance Ix i => Foldable (Array i) where
foldr f z = Prelude.foldr f z . elemsいずれのデータ構造でも，foldrは必ず定義されているのがわかります。配列であるArray型では，Foldableクラスのインスタンスを定義するのに最低限必要であるfoldrしか定義されていません。一方リストでは，foldrを通して各メソッドを定義すると効率が悪いので，foldとfoldMapを除くすべてのメソッドが定義されています。
自分でFoldableクラスのインスタンスを定義する場合，注意すべき点があります。Foldalbeクラスのインスタンスのメソッドは，自由に定義できるわけではありません。デフォルト定義のコメントに示してあるように，インスタンスで定義されるメソッドは，Preludeにある同名の関数との間で以下の法則を満たす必要があります。
- foldr f z = Prelude.foldr f z . toList
- foldl f z = Prelude.foldl f z . toList
- foldr1 f = Prelude.foldr1 f . toList
- foldl1 f = Prelude.foldl1 f . toList
ここで使われているtoList関数の定義は，基本的には以下の通りです。
toList = foldr (:) []
foldrの初期値として空リストである「[ ]」，関数としてデータ構成子「:」を与えています。このことから，toListは「Foldableクラスのインスタンスとして定義されたデータ構造から順番に要素を取り出し，その要素を使ってリストを構成する」という処理であることがわかります。
上の法則の中にあるPreludeのfold*は，リストに対する関数です。これらの法則は「Foldableクラスのfold*メソッドは，一度リストに変換してPreludeの同名の関数を使った場合と同じように振る舞う必要がある」という制約を表しています。
なお，GHC向けのtoListは，実際には最適化のために以下のように定義されています。こうした最適化については，この連載の後の回で改めて取り上げる予定です。
-- | List of elements of a structure. toList :: Foldable t => t a -> [a] #ifdef __GLASGOW_HASKELL__ toList t = build (\ c n -> foldr c n t) #else toList = foldr (:) [] #endif
