foldr
fold right
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b 定義
1.hsfoldr :: (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 より一般化されているhsfoldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z型の意味合い
hsEndo :: (a -> a) -> Endo a
(Endo .) :: (a -> b -> b) -> a -> Endo b
End . f :: a -> Endo b
foldMap (Endo . f) t :: Endo bfoldMapの型は、
(Monoid m, Foldable t) => (a -> m) -> t a -> m なので第1引数の
a -> m には、Monoidの制約が必要だが、 End . f の型を見れば分かる通り、Monoid制約は含まれていないすごい
例
hsfoldr (+) 0 [1,2,3] -- > 6以下のように考えると良い
hs1 : (2 : (3 : []))) -- 通常のリスト
1 + (2 + (3 + 0))) -- foldr (+) 0 [1,2,3]参考
Foldableのmethodのfoldrについて、丁寧に解説されている
>#WIP
末尾再帰ではない
Call Stackへに積むやつが必要になる
リストから、同じ個数のリストを生成する関数と相性が良い ref
パフォーマンス的に
例えば、mapとかfilterとか
無限リストを扱える
最後の方の章
ちゃんと理解していない #??