Learn You a Haskell demonstrates the DiffList concept:
*Main Control.Monad.Writer> let f = \xs -> "dog" ++ ("meat" ++ xs)
*Main Control.Monad.Writer> f "foo"
"dogmeatfoo"
Is the primary benefit of the DiffList
that the list gets constructed from left to right?
Data.Sequence
is that it has very high constant factors relative to nearly every other commonly-used data structure. The big advantage it has overDiffList
is that you can view it directly, whereas aDiffList
must be converted to a regular list first (the 'Reflection Without Remorse' paper covers this well). If you don't need to view/deconstruct the list until it's fully created,DiffList
will outperformData.Sequence
.