Why are difference lists more efficient than regular concatenation?
- by Craig Innes
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?
