真实世界Haskell书 - Logger monad例子的渐近复杂性

Question

我刚刚到达真实世界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)

其中,注入器函数中的第二个元素包含我们的日志消息,这些消息是使用++连续添加的.(有关更多背景,请在此处在线阅读.)

我的问题是..不会使运行时的复杂性使用这个Logger二次到消息的数量？

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

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

顺便说一句,我喜欢这本书,这本书将成为一本书,我会在很长一段时间内阅读这本书.

Answer 1

这是Writer monad的标准(天真)编码,专门用于列出输出.它适用于大多数用途,使用monoid实例进行列表:

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

具有更好复杂性的替代方案涉及对dlists的逻辑,或甚至更有效,文本或构建器monoid.