@hackage vector-rotcev0.1.0.2

Vectors with O(1) reverse

vector-rotcev Hackage Stackage LTS Stackage Nightly

A wrapper for an arbitrary Vector with O(1) reverse. Instead of creating a copy, it just flips a flag, which inverts indexing. Imagine it as a vector with a switch between little-endianness and big-endianness.

Let us have a vector of data vec :: Vector Int, which is manipulated via Data.Vector.Generic-based API. You can wrap it into Forward vec :: Rotcev Vector Int and leave everything else unchanged, because Rotcev Vector Int still has all Vector instances. Then apply reverse (Forward vec) :: Rotcev Vector Int, which effectively reverses the vector in O(1) time and space. Internally instead of actual reversing, reverse just provides a view (or a lens) with an inverted order of indexing, which affects all Data.Vector.Generic API.

For example,

> vec = Data.Vector.Generic.fromList [0..100] :: Data.Vector.Vector Int
> cev = reverse (Forward vec) :: Rotcev Data.Vector.Vector Int
> cev Data.Vector.Generic.! 10
90

In a mutable setting you can freely manipulate original and reversed vectors simultaneously, using mreverse function:

> Control.Monad.ST.runST $ do
    vec <- Data.Vector.Generic.Mutable.replicate 3 0.0
    let cev = mreverse vec
    Data.Vector.Generic.Mutable.write vec 0 1.0
    Data.Vector.Generic.Mutable.write cev 0 2.0
    unRotcev <$> Data.Vector.Generic.freeze vec
    :: Data.Vector.Vector Double
[1.0,0.0,2.0]

This library works for any flavor of Vector: boxed, unboxed, storable, whatever.