-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Efficient multidimensional arrays -- @package PrimitiveArray @version 0.6.0.0 module Data.PrimitiveArray.Index.Class -- | Strict pairs -- as in repa. data (:.) a b (:.) :: !a -> !b -> (:.) a b -- | A different version of strict pairs. Makes for simpler type inference -- in multi-tape grammars. We use :> when we have special -- needs, like non-recursive instances on inductives tuples, as used for -- set indices. data (:>) a b (:>) :: !a -> !b -> (:>) a b -- | Base data constructor for multi-dimensional indices. data Z Z :: Z -- | Index structures for complex, heterogeneous indexing. Mostly designed -- for indexing in DP grammars, where the indices work for linear and -- context-free grammars on one or more tapes, for strings, sets, later -- on tree structures. class Index i linearIndex :: Index i => i -> i -> i -> Int smallestLinearIndex :: Index i => i -> Int largestLinearIndex :: Index i => i -> Int size :: Index i => i -> i -> Int inBounds :: Index i => i -> i -> i -> Bool -- | Generate a stream of indices in correct order for dynamic programming. -- Since the stream generators require concatMap / -- flatten we have to write more specialized code for -- (z:.IX) stuff. class IndexStream i where streamUp l h = map (\ (Z :. i) -> i) $ streamUp (Z :. l) (Z :. h) streamDown l h = map (\ (Z :. i) -> i) $ streamDown (Z :. l) (Z :. h) streamUp :: (IndexStream i, Monad m) => i -> i -> Stream m i streamDown :: (IndexStream i, Monad m) => i -> i -> Stream m i instance (Index zs, Index z) => Index (zs :> z) instance (Index zs, Index z) => Index (zs :. z) instance IndexStream Z instance Index Z instance NFData Z instance Arbitrary Z instance FromJSON Z instance ToJSON Z instance Serialize Z instance Binary Z instance Vector Vector Z instance MVector MVector Z instance Unbox Z instance (Read a, Read b) => Read (a :> b) instance Eq Z instance Ord Z instance Read Z instance Show Z instance Generic Z instance Datatype D1Z instance Constructor C1_0Z instance (NFData a, NFData b) => NFData (a :> b) instance (FromJSON a, FromJSON b) => FromJSON (a :> b) instance (ToJSON a, ToJSON b) => ToJSON (a :> b) instance (Serialize a, Serialize b) => Serialize (a :> b) instance (Binary a, Binary b) => Binary (a :> b) instance (Unbox a0, Unbox b0) => Vector Vector (a0 :> b0) instance (Unbox a0, Unbox b0) => MVector MVector (a0 :> b0) instance (Unbox a0, Unbox b0) => Unbox (a0 :> b0) instance (Read a, Read b) => Read (a :. b) instance (Eq a, Eq b) => Eq (a :> b) instance (Ord a, Ord b) => Ord (a :> b) instance (Show a, Show b) => Show (a :> b) instance Generic (a :> b) instance Datatype D1:> instance Constructor C1_0:> instance (Arbitrary a, Arbitrary b) => Arbitrary (a :. b) instance (NFData a, NFData b) => NFData (a :. b) instance (FromJSON a, FromJSON b) => FromJSON (a :. b) instance (ToJSON a, ToJSON b) => ToJSON (a :. b) instance (Serialize a, Serialize b) => Serialize (a :. b) instance (Binary a, Binary b) => Binary (a :. b) instance (Unbox a0, Unbox b0) => Vector Vector (a0 :. b0) instance (Unbox a0, Unbox b0) => MVector MVector (a0 :. b0) instance (Unbox a0, Unbox b0) => Unbox (a0 :. b0) instance (Eq a, Eq b) => Eq (a :. b) instance (Ord a, Ord b) => Ord (a :. b) instance (Show a, Show b) => Show (a :. b) instance Generic (a :. b) instance Datatype D1:. instance Constructor C1_0:. module Data.PrimitiveArray.Index.Complement -- | A special index wrapper -- like Outside. Complement -- allows combining inside and outside symbols which complement each -- other. This then yields ensemble results for each index (you need -- ADPfusion for this). newtype Complement z C :: z -> Complement z unC :: Complement z -> z instance Arbitrary z => Arbitrary (Complement z) instance IndexStream i => IndexStream (Complement i) instance Index i => Index (Complement i) instance NFData z => NFData (Complement z) instance FromJSON z => FromJSON (Complement z) instance ToJSON z => ToJSON (Complement z) instance Serialize z => Serialize (Complement z) instance Binary z => Binary (Complement z) instance Unbox z0 => Vector Vector (Complement z0) instance Unbox z0 => MVector MVector (Complement z0) instance Unbox z0 => Unbox (Complement z0) instance Eq z => Eq (Complement z) instance Ord z => Ord (Complement z) instance Read z => Read (Complement z) instance Show z => Show (Complement z) instance Generic (Complement z) instance Datatype D1Complement instance Constructor C1_0Complement instance Selector S1_0_0Complement module Data.PrimitiveArray.Index.Int instance IndexStream Int instance IndexStream z => IndexStream (z :. Int) instance Index Int module Data.PrimitiveArray.Index.Outside -- | The Outside wrapper takes an index structure, and provides -- IndexStream functions streamUp and streamDown -- that work the other way around. In particular, for Outside z -- streamUp (Outside z) = fmap Outside $ streamDown z and vice -- versa. Index functions are unwrapped but otherwise work as -- before. newtype Outside z O :: z -> Outside z unO :: Outside z -> z instance Arbitrary z => Arbitrary (Outside z) instance IndexStream i => IndexStream (Outside i) instance Index i => Index (Outside i) instance NFData z => NFData (Outside z) instance FromJSON z => FromJSON (Outside z) instance ToJSON z => ToJSON (Outside z) instance Serialize z => Serialize (Outside z) instance Binary z => Binary (Outside z) instance Unbox z0 => Vector Vector (Outside z0) instance Unbox z0 => MVector MVector (Outside z0) instance Unbox z0 => Unbox (Outside z0) instance Eq z => Eq (Outside z) instance Ord z => Ord (Outside z) instance Read z => Read (Outside z) instance Show z => Show (Outside z) instance Generic (Outside z) instance Datatype D1Outside instance Constructor C1_0Outside instance Selector S1_0_0Outside -- | Point index structures are used for left- and right-linear -- grammars. Such grammars have at most one syntactic symbol on each -- r.h.s. of a rule. The syntactic symbol needs to be in an outermost -- position. module Data.PrimitiveArray.Index.Point -- | A point in a left-linear grammar. The syntactic symbol is in left-most -- position. newtype PointL PointL :: Int -> PointL fromPointL :: PointL -> Int -- | A point in a right-linear grammars. newtype PointR PointR :: Int -> PointR fromPointR :: PointR -> Int instance Index PointR instance NFData PointR instance ToJSON PointR instance FromJSON PointR instance Serialize PointR instance Binary PointR instance Vector Vector PointR instance MVector MVector PointR instance Unbox PointR instance Arbitrary PointL instance IndexStream PointL instance IndexStream z => IndexStream (z :. PointL) instance Index PointL instance NFData PointL instance ToJSON PointL instance FromJSON PointL instance Serialize PointL instance Binary PointL instance Vector Vector PointL instance MVector MVector PointL instance Unbox PointL instance Eq PointL instance Read PointL instance Show PointL instance Generic PointL instance Eq PointR instance Read PointR instance Show PointR instance Generic PointR instance Datatype D1PointL instance Constructor C1_0PointL instance Selector S1_0_0PointL instance Datatype D1PointR instance Constructor C1_0PointR instance Selector S1_0_0PointR -- | Set with and without interfaces. We provide instances for sets, and -- sets with one or two interfaces. The First and Last -- annotation is purely cosmetical (apart from introducing type safety). module Data.PrimitiveArray.Index.Set -- | Certain sets have an interface, a particular element with special -- meaning. In this module, certain ``meanings'' are already provided. -- These include a First element and a Last element. We -- phantom-type these to reduce programming overhead. newtype Interface t Iter :: Int -> Interface t getIter :: Interface t -> Int -- | Declare the interface to be the start of a path. data First -- | Declare the interface to be the end of a path. data Last -- | Declare the interface to match anything. -- -- TODO needed? want to use later in ADPfusion data Any -- | Newtype for a bitset. We'd use Words but that requires more -- shape instances. -- -- TODO can we use Words now? newtype BitSet BitSet :: Int -> BitSet getBitSet :: BitSet -> Int -- | A bitset with one interface. type BS1I i = BitSet :> Interface i -- | A bitset with two interfaces. type BS2I i j = (BitSet :> Interface i) :> Interface j -- | Successor and Predecessor for sets. Designed as a class to accomodate -- sets with interfaces and without interfaces with one function. -- -- The functions are not written recursively, as we currently only have -- three cases, and we do not want to "reset" while generating successors -- and predecessors. -- -- Note that sets have a partial order. Within the group of element with -- the same popCount, we use popPermutation which has -- the same stepping order for both, setSucc and -- setPred. class SetPredSucc s setSucc :: SetPredSucc s => s -> s -> s -> Maybe s setPred :: SetPredSucc s => s -> s -> s -> Maybe s -- | Masks are used quite often for different types of bitsets. We liberate -- them as a type family. -- | Fixed allows us to fix some or all bits of a bitset, thereby -- providing succ/pred operations which are only partially free. -- -- The mask is lazy, this allows us to have undefined for -- l and h. -- -- f = getFixedMask .&. getFixed are the fixed bits. n = -- getFixed .&. complement getFixedMask are the free bits. -- to = complement getFixed is the to move mask n' = -- popShiftR to n yields the population after the move p = -- popPermutation undefined n' yields the new population permutation -- p' = popShiftL to p yields the population moved back -- final = p' .|. f data Fixed t Fixed :: (Mask t) -> !t -> Fixed t getFixedMask :: Fixed t -> (Mask t) getFixed :: Fixed t -> !t -- | Assuming a bitset on bits [0 .. highbit], we can apply a mask -- that stretches out those bits over [0 .. higherBit] with -- highbit <= higherBit. Any active interfaces are correctly -- set as well. class ApplyMask s applyMask :: ApplyMask s => Mask s -> s -> s testBsS :: BitSet -> Maybe (Fixed BitSet) arbitraryBitSetMax :: Integer instance (Generic t, Generic (Mask t)) => Generic (Fixed t) instance (Show t, Show (Mask t)) => Show (Fixed t) instance (Read t, Read (Mask t)) => Read (Fixed t) instance (Ord t, Ord (Mask t)) => Ord (Fixed t) instance (Eq t, Eq (Mask t)) => Eq (Fixed t) instance Datatype D1Fixed instance Constructor C1_0Fixed instance Selector S1_0_0Fixed instance Selector S1_0_1Fixed instance Arbitrary ((BitSet :> Interface i) :> Interface j) instance Arbitrary (BitSet :> Interface i) instance Arbitrary BitSet instance (Arbitrary t, Arbitrary (Mask t)) => Arbitrary (Fixed t) instance ApplyMask ((BitSet :> Interface i) :> Interface j) instance ApplyMask (BitSet :> Interface i) instance ApplyMask BitSet instance SetPredSucc (Fixed ((BitSet :> Interface i) :> Interface j)) instance SetPredSucc (Fixed (BitSet :> Interface i)) instance SetPredSucc (Fixed BitSet) instance NFData (Fixed t) instance (Generic t, Generic (Mask t), Serialize t, Serialize (Mask t)) => Serialize (Fixed t) instance (Generic t, Generic (Mask t), Binary t, Binary (Mask t)) => Binary (Fixed t) instance (Unbox t0, Unbox (Mask t0)) => Vector Vector (Fixed t0) instance (Unbox t0, Unbox (Mask t0)) => MVector MVector (Fixed t0) instance (Unbox t0, Unbox (Mask t0)) => Unbox (Fixed t0) instance SetPredSucc ((BitSet :> Interface i) :> Interface j) instance SetPredSucc (BitSet :> Interface i) instance SetPredSucc BitSet instance IndexStream z => IndexStream (z :. ((BitSet :> Interface i) :> Interface j)) instance IndexStream z => IndexStream (z :. (BitSet :> Interface i)) instance IndexStream z => IndexStream (z :. BitSet) instance Index BitSet instance NFData BitSet instance FromJSON BitSet instance ToJSON BitSet instance Serialize BitSet instance Binary BitSet instance Show BitSet instance Vector Vector BitSet instance MVector MVector BitSet instance Unbox BitSet instance Index (Interface i) instance NFData (Interface t) instance FromJSON (Interface t) instance ToJSON (Interface t) instance Serialize (Interface t) instance Binary (Interface t) instance Vector Vector (Interface t0) instance MVector MVector (Interface t0) instance Unbox (Interface t0) instance Eq (Interface t) instance Ord (Interface t) instance Read (Interface t) instance Show (Interface t) instance Generic (Interface t) instance Num (Interface t) instance Eq BitSet instance Ord BitSet instance Read BitSet instance Generic BitSet instance FiniteBits BitSet instance Ranked BitSet instance Num BitSet instance Bits BitSet instance Datatype D1Interface instance Constructor C1_0Interface instance Selector S1_0_0Interface instance Datatype D1BitSet instance Constructor C1_0BitSet instance Selector S1_0_0BitSet module Data.PrimitiveArray.QuickCheck.Index.Set prop_Fixed_BitSet_setSucc :: (Word, Fixed BitSet) -> Bool -- | Index structure for context-free grammars on strings. A -- Subword captures a pair (i,j) with i<=j. module Data.PrimitiveArray.Index.Subword -- | A subword wraps a pair of Int indices i,j with -- i<=j. -- -- Subwords always yield the upper-triangular part of a rect-angular -- array. This gives the quite curious effect that (0,N) points -- to the ``largest'' index, while (0,0) ... (1,1) ... (k,k) ... -- (N,N) point to the smallest. We do, however, use (0,0) as the -- smallest as (0,k) gives successively smaller upper triangular parts. newtype Subword Subword :: (Int :. Int) -> Subword fromSubword :: Subword -> (Int :. Int) subword :: Int -> Int -> Subword -- | triangular numbers -- -- A000217 triangularNumber :: Int -> Int -- | Size of an upper triangle starting at i and ending at -- j. "(0,N)" what be the normal thing to use. upperTri :: Subword -> Int -- | Subword indexing. Given the longest subword and the current subword, -- calculate a linear index "[0,..]". "(l,n)" in this case means "l"ower -- bound, length "n". And "(i,j)" is the normal index. -- -- TODO probably doesn't work right with non-zero base ?! subwordIndex :: Subword -> Subword -> Int subwordFromIndex :: Subword -> Int -> Subword instance Arbitrary Subword instance IndexStream Subword instance IndexStream z => IndexStream (z :. Subword) instance Index Subword instance NFData Subword instance ToJSON Subword instance FromJSON Subword instance Serialize Subword instance Binary Subword instance Vector Vector Subword instance MVector MVector Subword instance Unbox Subword instance Eq Subword instance Ord Subword instance Show Subword instance Generic Subword instance Read Subword instance Datatype D1Subword instance Constructor C1_0Subword instance Selector S1_0_0Subword module Data.PrimitiveArray.Index -- | Vastly extended primitive arrays. Some basic ideas are now modeled -- after the vector package, especially the monadic mutable / pure -- immutable array system. -- -- NOTE all operations in MPrimArrayOps and PrimArrayOps are highly -- unsafe. No bounds-checking is performed at all. module Data.PrimitiveArray.Class -- | Mutable version of an array. -- | The core set of operations for monadic arrays. class Index sh => MPrimArrayOps arr sh elm boundsM :: MPrimArrayOps arr sh elm => MutArr m (arr sh elm) -> (sh, sh) fromListM :: (MPrimArrayOps arr sh elm, PrimMonad m) => sh -> sh -> [elm] -> m (MutArr m (arr sh elm)) newM :: (MPrimArrayOps arr sh elm, PrimMonad m) => sh -> sh -> m (MutArr m (arr sh elm)) newWithM :: (MPrimArrayOps arr sh elm, PrimMonad m) => sh -> sh -> elm -> m (MutArr m (arr sh elm)) readM :: (MPrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> sh -> m elm writeM :: (MPrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> sh -> elm -> m () -- | The core set of functions on immutable arrays. class Index sh => PrimArrayOps arr sh elm bounds :: PrimArrayOps arr sh elm => arr sh elm -> (sh, sh) unsafeFreeze :: (PrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> m (arr sh elm) unsafeThaw :: (PrimArrayOps arr sh elm, PrimMonad m) => arr sh elm -> m (MutArr m (arr sh elm)) unsafeIndex :: PrimArrayOps arr sh elm => arr sh elm -> sh -> elm transformShape :: (PrimArrayOps arr sh elm, Index sh') => (sh -> sh') -> arr sh elm -> arr sh' elm class Index sh => PrimArrayMap arr sh e e' map :: PrimArrayMap arr sh e e' => (e -> e') -> arr sh e -> arr sh e' -- | Infix index operator. Performs minimal bounds-checking using assert in -- non-optimized code. (!) :: PrimArrayOps arr sh elm => arr sh elm -> sh -> elm -- | Returns true if the index is valid for the array. inBoundsM :: (Monad m, MPrimArrayOps arr sh elm) => MutArr m (arr sh elm) -> sh -> Bool -- | Construct a mutable primitive array from a lower and an upper bound, a -- default element, and a list of associations. fromAssocsM :: (PrimMonad m, MPrimArrayOps arr sh elm) => sh -> sh -> elm -> [(sh, elm)] -> m (MutArr m (arr sh elm)) -- | Return all associations from an array. assocs :: (IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> [(sh, elm)] -- | Creates an immutable array from lower and upper bounds and a complete -- list of elements. fromList :: (PrimArrayOps arr sh elm, MPrimArrayOps arr sh elm) => sh -> sh -> [elm] -> arr sh elm -- | Creates an immutable array from lower and upper bounds, a default -- element, and a list of associations. fromAssocs :: (PrimArrayOps arr sh elm, MPrimArrayOps arr sh elm) => sh -> sh -> elm -> [(sh, elm)] -> arr sh elm -- | Returns all elements of an immutable array as a list. toList :: (IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> [elm] -- | freezeTables freezes a stack of tables. class FreezeTables m t where type family Frozen t :: * freezeTables :: FreezeTables m t => t -> m (Frozen t) instance (Functor m, Applicative m, Monad m, PrimMonad m, FreezeTables m ts, PrimArrayOps arr sh elm) => FreezeTables m (ts :. MutArr m (arr sh elm)) instance Applicative m => FreezeTables m Z -- | Dense primitive arrays where the lower index is zero (or the -- equivalent of zero for newtypes and enumerations). -- -- Actual writes to data structures use a more safe -- write instead of the unsafe unsafeWrite. Writes also -- tend to occur much less in DP algorithms (say, N^2 writes for an N^3 -- time algorithm -- mostly reads are being executed). -- -- TODO consider if we want to force the lower index to be zero, or allow -- non-zero lower indices. Will have to be considered together with the -- Index.Class module! module Data.PrimitiveArray.Dense data Unboxed sh e Unboxed :: !sh -> !sh -> !(Vector e) -> Unboxed sh e data Boxed sh e Boxed :: !sh -> !sh -> !(Vector e) -> Boxed sh e instance (Read sh, Read e, Unbox e) => Read (Unboxed sh e) instance (Show sh, Show e, Unbox e) => Show (Unboxed sh e) instance (Eq sh, Eq e, Unbox e) => Eq (Unboxed sh e) instance Generic (Unboxed sh e) instance (Read sh, Read e) => Read (Boxed sh e) instance (Show sh, Show e) => Show (Boxed sh e) instance (Eq sh, Eq e) => Eq (Boxed sh e) instance Generic (Boxed sh e) instance Datatype D1Unboxed instance Constructor C1_0Unboxed instance Datatype D1Boxed instance Constructor C1_0Boxed instance Index sh => PrimArrayMap Boxed sh e e' instance (Index sh, Unbox elm) => PrimArrayOps Boxed sh elm instance Index sh => MPrimArrayOps Boxed sh elm instance NFData (MutArr m (Boxed sh e)) instance NFData (Boxed sh e) instance (FromJSON sh, FromJSON e) => FromJSON (Boxed sh e) instance (ToJSON sh, ToJSON e) => ToJSON (Boxed sh e) instance (Serialize sh, Serialize e) => Serialize (Boxed sh e) instance (Binary sh, Binary e) => Binary (Boxed sh e) instance (Index sh, Unbox e, Unbox e') => PrimArrayMap Unboxed sh e e' instance (Index sh, Unbox elm) => PrimArrayOps Unboxed sh elm instance (Index sh, Unbox elm) => MPrimArrayOps Unboxed sh elm instance NFData (MutArr m (Unboxed sh e)) instance NFData (Unboxed sh e) instance (FromJSON sh, FromJSON e, Unbox e) => FromJSON (Unboxed sh e) instance (ToJSON sh, ToJSON e, Unbox e) => ToJSON (Unboxed sh e) instance (Serialize sh, Serialize e, Unbox e) => Serialize (Unboxed sh e) instance (Binary sh, Binary e, Unbox e) => Binary (Unboxed sh e) -- | Operations to fill primitive arrays. Arrays are combined just like -- indices using Z and '(:.)'. This allows filling an unlimited -- number of tables. ExtShape provides the rangeStream -- function with generates a stream of indices in (generally) the right -- order. module Data.PrimitiveArray.FillTables -- | Run the forward phase of algorithms. Is *really* unsafe for now if -- tables have different sizes, as in its broken. -- -- TODO Need to run min/max on the bounds for all tables, not just the -- last table. Otherwise we don't really need the distinction between -- save and unsafe. This will have to be in runFillTables. unsafeRunFillTables :: (Index sh, IndexStream sh, WriteCell m (tail :. (MutArr m (arr sh elm), t)) sh, MPrimArrayOps arr sh elm, Monad m, PrimMonad m) => (tail :. (MutArr m (arr sh elm), t)) -> m () -- | WriteCell provides methods to fill all cells with a specific -- index sh in a stack of non-terminal tables c. class Monad m => WriteCell m c sh unsafeWriteCell :: WriteCell m c sh => c -> sh -> m () writeCell :: WriteCell m c sh => c -> sh -> m () instance (WriteCell m cs sh, Monad m, MPrimArrayOps arr sh a, PrimMonad m) => WriteCell m (cs :. (MutArr m (arr sh a), sh -> m a)) sh instance Monad m => WriteCell m Z sh module Data.PrimitiveArray