PR

 データ構造の中のすべての要素にアクセスする高階関数には,個々の要素ごとに関数を適用する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にある同名の関数との間で以下の法則を満たす必要があります。

  1. foldr f z = Prelude.foldr f z . toList
  2. foldl f z = Prelude.foldl f z . toList
  3. foldr1 f = Prelude.foldr1 f . toList
  4. 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