This is a Haskell (plus some extensions) implementation of a library for incremental computing. It closely follows the implementation in the nice POPL 2002 paper "Adaptive Functional Programming", by Umut Acar, Guy Blelloch and Bob Harper.
This is a Haskell (plus some extensions) implementation of a library for incremental computing. It closely follows the implementation in the nice POPL 2002 paper "Adaptive Functional Programming", by Umut Acar, Guy Blelloch and Bob Harper. This is a small fork of the original library named Adaptive, with the same interface but small adaptations to GHC 7.4.
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.
Self optimizing tuple types.
Adaptive tuples are tuple types in which the number of elements is determined at run-time. These structures are designed to combine the space-efficiency of tuples with the size flexibility of lists.
Adaptive tuples provide lazy and strict, unpacked data structures for all tuple sizes from 0 to 20 elements. Adaptive tuples of more than 20 elements are allowed, however they are stored in an ordinary list.