purescript-difference-containers

Difference containers are a generalization of difference lists for any Monoid.

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.

• 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 to DList in Haskell.

• For convenience, instances of Functor, Apply, Bind, Monad, Foldable, Unfoldable and Traversable type classes are provided for Difference cnt type if cnt is also an instance of the corresponding type class. However, their methods convert Difference cnt to cnt under the hood, so the benefits of employing this library may be defeated by their use.

• To avoid stack safety issues, purescript-stacksafe-function is used. It allows accumulating large number of functions using compose without hitting the stack size limit.

• There may exist useful applications of difference containers other than amortization of linked list's append. They are still to be found.

Module documentation is published on Pursuit.