algorithm - Foldable 默认方法的性能

Question

我一直在探索 Foldable类和Monoid类(class)。

首先，假设我想折叠 Monoid First 的列表.像这样:

x :: [First a]

fold? mappend mempty x

然后我假设在这种情况下最合适的折叠是foldr，因为mappend for 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

假设我们的二叉树是平衡的，并且没有很多 Nothing 值，我相信这些操作应该花费 O(log(n)) 时间。

但是Foldable还基于 定义了很多默认方法，如 foldl、foldl'、foldr 和 foldr' >折叠 map 。

这些默认定义似乎是通过组合一堆函数来实现的，包裹在一个名为 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 .

所以我正在寻找的是解释为什么(或为什么不)say 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 constructor 定义的，所以它只存在于编译阶段，不存在于运行时。#. 运算符更改其第二个操作数的类型并丢弃第一个。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

对于您的可折叠二叉树:

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 中默认的惰性求值非常简单，只有两条规则:

1. 功能应用优先
2. 如果值很重要，则从左到右评估参数

这使得跟踪上面代码最后一行的评估变得容易:

  ((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< 做的一样 values)，评估短路，结果 O(最左边的叶子的高度)，或当树平衡时的 O(log(n))性能。

foldl 都是一样的，它只是 foldr 和 mappend 翻转，即 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) 最佳情况性能。