読者です 読者をやめる 読者になる 読者になる

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

FoldableクラスがfoldMapからfoldrを構成する流れ

某所の「すごいHaskell本」輪読会で「第12章モノイド」を読む予定があり、予習しています。第12章の中で、「Foldableクラスでは、foldMapを用意すれば、foldl/foldrが使えるようになる」との説明があるのですが、foldMapからfoldl/foldrを構成する具体的な方法が記載されておらず、ひじょーに気持ち悪かったので、自分なりの解説を用意しました。(foldlも本質的には同じはず・・・ですが、説明が簡単なfoldrの方で解説しています。)

事前の考察

Foldableクラスのインスタンスは、リストやTreeなど、一般に「値」の集合と考えることができます。若干、荒っぽい書き方で、

xs :: t a
xs = {xi | i = 1,...,n}

は、「x1,...,xn」という値の集合からなるFoldableなデータとします。

この時、関数「f :: a -> (b -> b)」に対して、foldrは、次のように理解できます。

foldr f z xs = f x1 ( f x2 ( f x3 ... f xn z )...)
            = (f x1) . (f x2) . (f x3) ... . (f xn) z

すなわち、初期値「z :: b」をxsの各要素から生成される関数(f xi)で次々に変換していきます。この時、xiを並べる順番の決定ルールが、データの種類(リストなのかTreeなのか)に依存して決まります。

ここで、(f xi)の関数合成の列を抽象化するために、次のMonoidを導入します。

newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
    mempty = id
    mappend = (.)

これは、特定の型の上の関数について、関数合成を「和(mappend)」とするMonoidを構成しています。

すると、関数「f xi :: b -> b」をEndoに包んでMonoid化したもの「Endo (f xi) :: Endo b」を使うと、先の関数合成が「mappend」に抽象化されます。

foldr f z xs = f x1 ( f x2 ( f x3 ... f xn z )...)
            = (f x1) . (f x2) . (f x3) ... . (f xn) z
            = appEndo ( (Endo (f x1)) `mappend` (Endo (f x2)) `mappend` ... (Endo (f xn)) ) z
            = appEndo ( ((Endo . f) x1) `mappend` ((Endo . f) x2) `mappend` ... ((Endo . f) xn) ) z

言い換えると、xs = {xi} の各要素をMonoid化した集合 { (Endo . f) xi } を `mappend` で連結しています。この時、連結する順番がデータの種類(リストなのかTreeなのか)に依存して決まります。

foldMapからfoldrを構成する

ここでおもむろに、Foldableクラスのインスタンスが持つ、foldMapメソッドを思い出します。

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m

Treeの場合は、次のように定義されます。

instance Foldable Tree where
  foldMap f EmtpyTree    = mempty
  foldMap f (Node x l r) = (foldMap f l) `mappend` (f x) `mappend` (fold Map f r)

これは、xsの各要素をMonoid化する手段「f :: a -> m」をfoldMapに与えると、xsの各要素をMonoid化したものを `mappend` で連結する方法を用意しているとみなせます。

・・・

えーと。。。

・・・・・・そう。

先のセクションの最後の式が、foldMapにぴったり適合しますね。

xsの各要素をMonoid化する手段として、「(Endo . f) xi」をfoldMapに与えると、ちょうど同じことになります。

foldr f z xs = f x1 ( f x2 ( f x3 ... f xn z )...)
            = (f x1) . (f x2) . (f x3) ... . (f xn) z
            = appEndo ( (Endo (f x1)) `mappend` (Endo (f x2)) `mappend` ... (Endo (f xn)) ) z
            = appEndo ( ((Endo . f) x1) `mappend` ((Endo . f) x2) `mappend` ... ((Endo . f) xn) ) z
            = appEdno (foldMap (Endo . f) xs) z

というわけで、一般にfoldMapが用意されているインスタンスというのは、foldMapによって、各要素を並べる順番決めのルールが用意されてるとみなせて、次の式で、自然にfoldrを定義することができるというわけです。

foldr f z xs = appEnd (foldMap (Endo . f) xs) z