Foldable.foldlはNum a => aでどのように動作するのですか

Question

LYAHには、次のようなコードがあります。

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

instance F.Foldable Tree where 
    foldMap f Empty = mempty 
    foldMap f (Node x l r) = F.foldMap f l `mappend` 
          f x   `mappend` 
          F.foldMap f r 

ghci> F.foldl (+) 0 testTree 
42 
ghci> F.foldl (*) 1 testTree 
64800 

私の知る限りでは、foldMapはタイプfoldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> mのですが、Num a => a自体はタイプMonoidではないので、私はFoldable.foldlは実際にここで働いんか疑問に思って？ foldMapは内部でFoldable.foldlと呼ばれているので、Monoidのタイプは何ですか？

Answer 1

foldr（(a -> b -> b) -> b -> t a -> b）と考えても分かりやすいです。 '代数'関数のタイプはa -> b -> bで、a -> (b -> b)と表示されます。すなわち、aを入力とし、出力としてb -> bを返します。

今、b -> bもモノイドである自己準同形、であり、そしてData.Monoidは確かに、あるタイプEndo a（またはここで、それはおそらくEndo bであるべき）、Monoidを定義します。

foldrは、単にfoldMapを呼び出すために内部Endoを使用しています。

foldr :: (a -> b -> b) -> b -> t a -> b 
foldr f z t = appEndo (foldMap (Endo #. f) t) z 

foldl基本的には同じトリックを行うために、周りの引数を反転します：明確にするため

foldl :: (b -> a -> b) -> b -> t a -> b 
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

を、私は文字通りこれらをコピーHaskellソースからの2つの関数の実装。 documentation of Data.Foldableに行くと、ソースを表示するためのさまざまなリンクがあります。それが私のしたことです。