algorithm - 可折叠默认方法的性能

我一直在探索Foldable课程和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也定义了很多默认方法，比如基于foldl的foldl'、foldr、foldr'和foldMap。
这些默认定义似乎是通过组合一组函数来实现的，这些函数包装在一个称为Endo的monoid中，集合中的每个元素对应一个函数，然后组合它们。
出于讨论的目的，我不会修改这些默认定义。
现在让我们考虑一下：

x1 :: BinaryTree (First a)
foldr mappend mempty x1

x2 :: BinaryTree (Last a)
foldl mappend mempty x2

运行这些程序是否能保持普通程序的性能（我暂时不担心固定因素）懒惰是否会导致树不需要完全遍历或者，O(log(n))和fold的默认定义需要遍历整个树吗？
我试着一步一步地研究这个算法（就像他们在Foldr Foldl Foldl'文章中所做的那样），但我最终完全搞糊涂了，因为这涉及到foldl、foldr和Foldable之间的交互，所以有点复杂。
所以我要找的是一个解释，为什么（或者为什么不）sayMonoid的默认定义在上面这样的平衡二叉树上只需要Endo时间。一个一步一步的例子，比如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)

以及数据中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)

NEDO是由NeXType构造函数定义的，所以它只存在于编译阶段，而不是运行时。
#.运算符更改第二个操作数的类型并放弃第一个操作数。
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）操作之后会更高一级，因此当它到达最左边的叶节点时：

= foldMap f leaf@(Leaf a) z'heightOfLeftMostLeaf
= f a z'heightOfLeftMostLeaf

然后f查看值a并决定忽略它的第二个参数（比如mappend将对First值做什么）、评估短路、结果O（最左边叶的高度）或O（log（n））在树平衡时的性能。
foldl是一样的，它只是foldr与mappend翻转，即O（log（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）best case performance。

关于algorithm - 可折叠默认方法的性能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34901907/