《Real World Haskell》书中Logger monad示例的渐进复杂度

Question

我刚刚阅读了《Real World Haskell》的第14章，昨天对此有些疑问。

在Logger单子例子中，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)

在注射器函数中，第二个元素包含我们的日志消息，使用++不断追加。(阅读此处以获取更多上下文信息。)

我的问题是...这样做会使得使用Logger时运行时复杂度与消息数量成二次关系吗？

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

如果我是对的，我希望有更多经验/见解的Haskell和该书作者能告诉我为什么选择这种实现方式，并且为什么可以接受。 在该书的前一章中，有一节说这种列表追加方式很糟糕，并教我们区别列表技术。为什么这里没有使用它？

顺便说一句，我喜欢这本书，它将是我长期以来阅读的一本书。

- ryaner

---

是的，我相信它具有二次复杂度。 - Robin Green

Answer 1

这是标准的（天真的）写作者单子编码，专门用于列表输出。对于大多数用途来说，它已经足够好了，使用列表的幺半群实例：

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

更好复杂度的替代方法涉及到对 dlists 的逻辑，甚至更高效的文本或构建器单子。

- Don Stewart

Answer 2

根据计算的结合性，是的，这将具有二次复杂度。例如，如果您的计算向右结合：

log 0 >> (log 1 >> (log 2 >> log 3))

如果它向左结合，则复杂度是线性的。

((log 0 >> log 1) >> log 2) >> log 3

如果复杂度是二次方的，那么就是将基础幺半群的属性向前传递，这里的幺半群是[]，(++)。

我想之所以这样陈述是为了简单明了。虽然可能不太高效，但完全可以明白正在发生的事情。然而，正如其他答案所述，这只是列表幺半群上的写作器（Writer）幺半群。您可以用mempty替换[]，用`mappend`替换++，然后使用[]或DList或您想要的任何东西来实例化它。因此，在我的看法中，使用具体形式并没有更加清晰明了。

- luqui

Answer 3

作为比较，Haskell平台的monad库包“mtl”从“transformers”包中获取Writer。所有Monoid类型的Writer实现都在这里附近的源代码中。该实例使用mappend而不是(++):

instance (Monoid w, Monad m) => Monad (WriterT w m) where
    return a = WriterT $ return (a, mempty)
    m >>= k  = WriterT $ do
        ~(a, w)  <- runWriterT m
        ~(b, w') <- runWriterT (k a)
        return (b, w `mappend` w')
    fail msg = WriterT $ fail msg

- Chris Kuklewicz