fleet-array: Fleet arrays are pure, but support fast updates if used linearly

Updating a pure array in Haskell usually requires copying the whole array, which takes linear time. For constant-time array updates, you would need to use a monadic interface, manually specifying the order of evaluation. Fleet arrays strike a balance between these two extremes. In common usage patterns, where old versions of arrays not reused after they are updated, fleet arrays support constant time indexing and updates. Accessing old versions does incur performance overhead. We hope this package can form the basis of a pure and performant array library.

Fleet arrays can be more than 10x faster than IntMap if used densly and linearly.

The ideas behind fleet arrays are due to Baker in 1991, who called them shallow arrays. These ideas were first implemented in Haskell by Simon Marlow as part of GHC (now moved to the diffarray package). Fleet arrays provide a simpler vector-like interface and offer better performance.