foldr - mrsekut-p

foldr

fold right

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

定義

code:1.hs

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

foldr f e [] = e

foldr f e (x : xs) = f x (foldr f e xs)

Foldable型クラスのmethodのfoldrの定義

1.hsより一般化されているmrsekut.icon

code:hs

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

foldr f z t = appEndo (foldMap (Endo . f) t) z

型の意味合い

code:hs

Endo :: (a -> a) -> Endo a

(Endo .) :: (a -> b -> b) -> a -> Endo b

End . f :: a -> Endo b

foldMap (Endo . f) t :: Endo b

foldMapの型は、(Monoid m, Foldable t) => (a -> m) -> t a -> mなので

第1引数のa -> mには、Monoidの制約が必要だが、

End . fの型を見れば分かる通り、Monoid制約は含まれていない

これは、Endo型がMonoidのinstanceになっているため、b(foldrの第1引数の返り値などの型)は、Monoidではなくても使える

すごいmrsekut.icon

例

code:hs

foldr (+) 0 1,2,3 -- > 6

以下のように考えると良い

code:hs

1 : (2 : (3 : []))) -- 通常のリスト

1 + (2 + (3 + 0))) -- foldr (+) 0 1,2,3

参考

Foldableのmethodのfoldrについて、丁寧に解説されている

Call Stackへに積むやつが必要になる

リストから、同じ個数のリストを生成する関数と相性が良い ref

パフォーマンス的に

例えば、mapとかfilterとか

無限リストを扱える

最後の方の章

ちゃんと理解していない #??