Foldable型クラス

すべての要素を使って計算を行う

foldrをListだけでなく他の型に対しても適用できるようにする

hs

code:hs

class Foldable t where

foldMap :: Monoid m => (a -> m) -> t a -> m

foldr :: (a -> b -> b) -> b -> t a -> b

6つのmethodを持つ

foldMapかfoldrのいずれかを定義すればあとは自動的に決まる

purs

code:purs(hs)

class Foldable f where

foldMap :: forall a m. Monoid m => (a -> m) -> f a -> m

foldr :: forall a b. (a -> b -> b) -> b -> f a -> b

foldl :: forall a b. (b -> a -> b) -> b -> f a -> b

6つのmethodを理解するのに良さそうな順序

引数の意味と使い方をまず知っておく

定義はあとで見るのでいったん無視していい

foldMapを少し具体化する

foldMapを理解してれば簡単

foldrの定義の意味を理解する

foldrを少し拡張したものと捉える

pursのListってなんでFoldableのinstanceじゃないの？

Arrayはなってる

参考

論文

table:具体例

Listでの具体例

fold concat

foldMap concatMap

code:hs

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

補足

code:hs

toList = foldr (:) []