"Difference containers" is a name of this implementation of difference lists. This library is usable with both Data.List
and Data.List.Lazy
(and potentially can be used with any listlike structure with mempty
value and append
operation).
Suppose there is a container type cnt :: * > *
with associative operation append :: ∀ a. cnt a > cnt a > cnt a
, the time complexity of which is dependent on the first argument's size and is constant for any size of the second.
Then, a structure of form append (append a b) c
is equivalent to the one of form append a (append b c)
, but the latter requires less computations, because the size of a
plus the size of b
is generally less than the size of a
plus the size of append a b
.
This observation can be utilized for performance optimisation. It is possible to delay a computation that intensively appends to the right, and "rebalance the parentheses" before computing the final value.
See also: R. John Muir Hughes, A novel representation of lists and its application to the function ``reverse''.

Instead of providing two types for strict and lazy difference lists, this library defines the
Difference
type, which is parametrised by the inner container type.Difference List
is thus equivalent toDList
in Haskell. 
For convenience, instances of
Functor
,Apply
,Bind
,Monad
,Foldable
,Unfoldable
andTraversable
type classes are provided forDifference cnt
type ifcnt
is also an instance of the corresponding type class. However, their methods convertDifference cnt
tocnt
under the hood, so the benefits of employing this library may be defeated by their use. 
To avoid stack safety issues, purescriptstacksafefunction is used. It allows accumulating large number of functions using
compose
without hitting the stack size limit when actually running the resulting function.
Module documentation is published on Pursuit.