algorithm - Real World Haskell book - Logger monad 示例的渐近复杂性

Question

我刚刚读到 Real World Haskell 的第 14 章，昨天还在想这个问题。

在Logger monad例子中，bind函数实现如下:

-- (>>=) :: Logger a -> (a -> Logger b) -> Logger b
    m >>= k = let (a, w) = execLogger m
                  n      = k a
                  (b, x) = execLogger n
              in Logger (b, w ++ x)

注入(inject)器函数中的第二个元素包含我们的日志消息，这些消息不断地使用++ 附加。 (在线阅读 here 了解更多信息。)

我的问题是……这不会使使用此 Logger 的运行时复杂度与消息数量呈二次方关系吗？

如果我错了，请帮助提供正确的分析和大哦符号。

如果我是对的，我希望对 Haskell 和这本书有更多经验/见解的人可以告诉我选择该实现的一些原因，以及为什么它可以。在本书的前一章中有 a section这说明这种添加列表的方式很糟糕，并教会了我们差异列表技术。为什么这里不使用它？

顺便说一句，我喜欢这本书，很长一段时间以来我都会从头到尾读完这本书。

Answer 1

这是 Writer monad 的标准(朴素)编码, 专门列出输出。它适用于大多数用途，对列表使用 monoid 实例:

instance Monoid [a] where
        mempty  = []
        mappend = (++)

具有更好复杂性的替代方案涉及到 dlists 的逻辑，或者更有效地，文本或 builder monoid .