4

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?

3
  • 4
    Pretty much, yeah, in that diff lists are more efficient for prepending values, and in certain circumstances that can give you quite the performance boost.
    – bheklilr
    Aug 12, 2014 at 2:06
  • 1
    To be more specific, concatenation of normal lists is O(n) in its first argument; for difflists this is not the case. There are often better alternatives to DiffLists for many use cases, however; see Data.Sequence for an example. Aug 12, 2014 at 2:53
  • @MarkWhitfield: the big problem with Data.Sequence is that it has very high constant factors relative to nearly every other commonly-used data structure. The big advantage it has over DiffList is that you can view it directly, whereas a DiffList 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 outperform Data.Sequence.
    – John L
    Aug 13, 2014 at 5:38

1 Answer 1

0

The DList package lists some of the asymptotics: https://hackage.haskell.org/package/dlist-0.5/docs/Data-DList.html

You'll note lots of things only take O(1), including cons, snoc, and append. However, note that inspecting the list needs to force lots of operations each time, so if you are doing more inspecting than construction, or interleaving the two, the DList approach won't necessarily be a win.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.