Foldable默认方法的性能

Question

我一直在研究Foldable类和Monoid类。

首先，假设我想折叠一下Monoid First的列表。如下所示：

x :: [First a]

fold? mappend mempty x

然后我假设在这种情况下最合适的文件夹应该是foldr，因为First的mappend在第二个参数中是惰性的。

相反，对于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和基于foldMap的foldr'。

这些默认定义似乎是通过组合一组函数来实现的，这些函数包装在一个名为Endo的Monoid中，集合中的每个元素一个函数，然后将它们组合在一起。

出于本文讨论的目的，我不会修改这些默认定义。

因此，现在让我们考虑一下：

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

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

运行这些能保持普通fold的O(log(n))性能吗？(我目前并不担心恒定的因素)。懒惰会导致树不需要被完全遍历吗？或者，foldl和foldr的默认定义是否需要遍历整个树？

我试图一步一步地介绍算法(就像他们在Foldr Foldl Foldl'文章中所做的那样)，但我最终完全把自己搞糊涂了，因为这有点复杂，因为它涉及到Foldable、Monoid和Endo之间的交互。

所以我想要的是解释为什么(或者为什么不) foldr的默认定义只会在上面这样的平衡二叉树上占用O(log(n))时间。一步一步的例子，比如Foldr Foldl Foldl'文章中的内容，将会非常有帮助，但我理解这是不是太难了，因为我在尝试它时完全迷惑了自己。

Answer 1

是的，它有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

. (函数组合)在case中的定义：

(.) 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中的默认惰性评估最终很简单，只有两个规则：

如果值很重要，则函数应用程序从左到右对参数进行first

• evaluate

这使得跟踪上面代码的最后一行的求值变得很容易：

  ((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对log值所做的那样)、评估短路、结果O(最左侧叶子的高度)或树平衡时的O( First (N))性能。

foldl也是一样的，只是foldr的mappend翻转了，即Last的最佳性能为O(log(n))。

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)最佳情况下的性能。