Why are difference lists more efficient than regular concatenation?

Posted by Craig Innes on Stack Overflow See other posts from Stack Overflow or by Craig Innes
Published on 2012-12-14T13:04:34Z Indexed on 2012/12/14 17:03 UTC
Read the original article Hit count: 249

I am currently working my way through the Learn you a haskell book online, and have come to a chapter where the author is explaining that some list concatenations can be ineffiecient: For example

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

Is supposedly inefficient. The solution the author comes up with is to use 'difference lists' defined as

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))

I am struggling to understand why DiffList is more computationally efficient than a simple concatenation in some cases. Could someone explain to me in simple terms why the above example is so inefficient, and in what way the DiffList solves this problem?

© Stack Overflow or respective owner

Related posts about Performance

Related posts about list