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