相关疑难解决方法(0)

我目前正在通过在线学习你的Haskell书籍的方式,并且已经到了一个章节,作者正在解释一些列表连接可能效率低下:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下.作者提出的解决方案是使用定义为的"差异列表"

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么DiffList在某些情况下比简单串联更具计算效率.有人可以用简单的语言向我解释为什么上面的例子是如此低效,以及DiffList以什么方式解决了这个问题？