adaptive-containers

Self optimizing container types

http://code.haskell.org/~dons/code/adaptive-containers

Latest on Hackage:

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD-3-Clause licensed by Don Stewart

Maintained by Don Stewart ([email protected])

Self optimizing polymorphic container types.

Adaptive containers are polymorphic container types that use class associated data types to specialize particular element types to a more efficient container representation. The resulting structures tend to be both more time and space efficient.

A self-optimizing pair, for example, will unpack the constructors, yielding a representation for (Int,Char) requiring 8 bytes, instead of 24.

This difference can be visualized. Consider the expression:

[ (x,y) | x <- [1..3], y <- [x..3] ]

[(Int,Int)]: A regular list of pairs http://code.haskell.org/~dons/images/vacuum/tuple-list.png
[Pair Int Int]: An adaptive list of pairs http://code.haskell.org/~dons/images/vacuum/pair-list.png
List (Pair Int Int): An adaptive list of adaptive pairs http://code.haskell.org/~dons/images/vacuum/list-pair.png

Currently supported adaptive containers: pairs, lists, maybes

Most unboxed element types are supported.