可折叠的默认方法的性能
我一直在探索Foldable类和Monoid类。
首先，让我们说我想折叠Monoid First的列表。 像这样：
x :: [First a]
fold? mappend mempty x
那么，我想在这种情况下，最合适的折将foldr ，作为mappend为First是懒惰的，在它的第二个参数。
相反，对于Last我们想foldl' （或只是foldl我不知道）。
现在从列表中移除，我定义了一个简单的二叉树，如下所示：
{-# LANGUAGE GADTs #-}
data BinaryTree a where
BinaryTree :: BinaryTree a -> BinaryTree a -> BinaryTree a
Leaf :: a -> BinaryTree a
我用最直接的定义将它Foldable起来：
instance Foldable BinaryTree where
foldMap f (BinaryTree left right) =
(foldMap f left) `mappend` (foldMap f right)
foldMap f (Leaf x) = f x
由于Foldable将fold定义为简单的foldMap id我们现在可以这样做：
x1 :: BinaryTree (First a)
fold x1
x2 :: BinaryTree (Last a)
fold x2
假设我们的BinaryTree是平衡的，并且没有很多Nothing值，这些操作应该花O(log(n))时间，我相信。
但是Foldable也基于foldMap定义了很多默认方法，如foldl ， foldl' ， foldr和foldr' 。
这些默认定义似乎是通过组合一系列函数来实现的，这些函数包装在一个称为Endo的Monoid中，集合中的每个元素都包含一个，然后将它们全部组成。
为了讨论的目的，我没有修改这些默认定义。
现在让我们考虑一下：
x1 :: BinaryTree (First a)
foldr mappend mempty x1
x2 :: BinaryTree (Last a)
foldl mappend mempty x2
运行这些保留了O(log(n))的普通fold性能吗？ （我不担心目前的不变因素）。 懒惰是否导致树不需要完全遍历？ 或者foldl和foldr的缺省定义需要整个树的遍历吗？
我试图一步一步地去研究算法（很像他们在Foldr Foldl Foldl的文章中做的那样），但是我最终完全迷惑了自己，因为这涉及到Foldable ， Monoid和Endo之间的交互，这有点复杂。
所以我在寻找的是解释为什么（或者为什么）没有说foldr的默认定义，在上面的平衡二叉树上只需要O(log(n))时间。 像Foldr Foldl Foldl的文章那样，一步一步的例子会非常有帮助，但我明白如果这太困难了，因为我完全搞不清楚自己在尝试它。
是的，它具有O（log（n））最佳案例表现。
Endo是一个包装（a - > a）类型的函数：
instance Monoid (Endo a) where
mempty = Endo id
Endo f `mappend` Endo g = Endo (f . g)
Data.Foldable中的foldr的默认实现：
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z
的定义. （功能组合）的情况下：
(.) f g = x -> f (g x)
Endo由newtype构造函数定义，所以它只存在于编译阶段，而不是运行时。 #. 运算符更改它的第二个操作数的类型并丢弃第一个操作数。 newtype构造函数和#. 操作员保证在考虑性能问题时可以忽略包装器。
所以foldr的默认实现可以简化为：
-- mappend = (.), mempty = id from instance Monoid (Endo a)
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = foldMap f t z
对于您的Foldable BinaryTree ：
foldr f z t
= foldMap f t z
= case t of
Leaf a -> f a z
-- what we care
BinaryTree l r -> ((foldMap f l) . (foldMap f r)) z
Haskell中的默认懒惰评估最终很简单，只有两条规则：
这样可以很容易地跟踪上面代码的最后一行的评估：
((foldMap f l) . (foldMap f r)) z
= (z -> foldMap f l (foldMap f r z)) z
= foldMap f l (foldMap f r z)
-- let z' = foldMap f r z
= foldMap f l z' -- height 1
-- if the branch l is still not a Leaf node
= ((foldMap f ll) . (foldMap f lr)) z'
= (z -> foldMap f ll (foldMap f lr)) z'
= foldMap f ll (foldMap f lr z')
-- let z'' = foldMap f lr z'
= foldMap f ll z'' -- height 2
在左侧完全展开之前，树的右侧分支从不展开，并且在函数展开和应用程序的O（1）操作之后，树的右侧分支高一级，因此当它到达最左侧的Leaf节点时：
= foldMap f leaf@(Leaf a) z'heightOfLeftMostLeaf
= f a z'heightOfLeftMostLeaf
然后， f查看值a并决定忽略它的第二个参数（比如mappend对First值所做的操作），评估短路，结果O（最左边叶子的高度）或O（log（n） ）当树平衡时的性能。
foldl都是一样的，它只是foldr与mappend翻转即O（日志（n））的最好的情况下性能Last 。
foldl'和foldr'是不同的。
foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
where f' x k z = k $! f z x
在每一个缩减步骤中，首先评估参数，然后是函数应用程序，该树将被遍历，即O（n）最佳情况下的性能。
链接地址: http://www.djcxy.com/p/63635.html