Copyright	(c) 2015 Dan Doel
License	BSD3
Maintainer	libraries@haskell.org
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

Data.Primitive.SmallArray

Description

Small arrays are boxed (im)mutable arrays.

The underlying structure of the Array type contains a card table, allowing segments of the array to be marked as having been mutated. This allows the garbage collector to only re-traverse segments of the array that have been marked during certain phases, rather than having to traverse the entire array.

SmallArray lacks this table. This means that it takes up less memory and has slightly faster writes. It is also more efficient during garbage collection so long as the card table would have a single entry covering the entire array. These advantages make them suitable for use as arrays that are known to be small.

The card size is 128, so for uses much larger than that, Array would likely be superior.

The underlying type, SmallArray#, was introduced in GHC 7.10, so prior to that version, this module simply implements small arrays as Array.

Synopsis

data SmallArray a = SmallArray (SmallArray# a)
data SmallMutableArray s a = SmallMutableArray (SmallMutableArray# s a)
newSmallArray :: PrimMonad m => Int -> a -> m (SmallMutableArray (PrimState m) a)
readSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> m a
writeSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> a -> m ()
copySmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> SmallArray a -> Int -> Int -> m ()
copySmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> SmallMutableArray (PrimState m) a -> Int -> Int -> m ()
indexSmallArray :: SmallArray a -> Int -> a
indexSmallArrayM :: Monad m => SmallArray a -> Int -> m a
indexSmallArray## :: SmallArray a -> Int -> (# a #)
cloneSmallArray :: SmallArray a -> Int -> Int -> SmallArray a
cloneSmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> Int -> m (SmallMutableArray (PrimState m) a)
freezeSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> Int -> m (SmallArray a)
unsafeFreezeSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> m (SmallArray a)
thawSmallArray :: PrimMonad m => SmallArray a -> Int -> Int -> m (SmallMutableArray (PrimState m) a)
runSmallArray :: (forall s. ST s (SmallMutableArray s a)) -> SmallArray a
unsafeThawSmallArray :: PrimMonad m => SmallArray a -> m (SmallMutableArray (PrimState m) a)
sizeofSmallArray :: SmallArray a -> Int
sizeofSmallMutableArray :: SmallMutableArray s a -> Int
smallArrayFromList :: [a] -> SmallArray a
smallArrayFromListN :: Int -> [a] -> SmallArray a
mapSmallArray' :: (a -> b) -> SmallArray a -> SmallArray b
traverseSmallArrayP :: PrimMonad m => (a -> m b) -> SmallArray a -> m (SmallArray b)

Documentation

data SmallArray a Source #

Constructors

SmallArray (SmallArray# a)

Instances

Instances details

Monad SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods (>>=) :: SmallArray a -> (a -> SmallArray b) -> SmallArray b # (>>) :: SmallArray a -> SmallArray b -> SmallArray b # return :: a -> SmallArray a #
Functor SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods fmap :: (a -> b) -> SmallArray a -> SmallArray b # (<$) :: a -> SmallArray b -> SmallArray a #
MonadFix SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods mfix :: (a -> SmallArray a) -> SmallArray a #
MonadFail SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods fail :: String -> SmallArray a #
Applicative SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods pure :: a -> SmallArray a # (<>) :: SmallArray (a -> b) -> SmallArray a -> SmallArray b # liftA2 :: (a -> b -> c) -> SmallArray a -> SmallArray b -> SmallArray c # (>) :: SmallArray a -> SmallArray b -> SmallArray b # (<*) :: SmallArray a -> SmallArray b -> SmallArray a #
Foldable SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods fold :: Monoid m => SmallArray m -> m # foldMap :: Monoid m => (a -> m) -> SmallArray a -> m # foldMap' :: Monoid m => (a -> m) -> SmallArray a -> m # foldr :: (a -> b -> b) -> b -> SmallArray a -> b # foldr' :: (a -> b -> b) -> b -> SmallArray a -> b # foldl :: (b -> a -> b) -> b -> SmallArray a -> b # foldl' :: (b -> a -> b) -> b -> SmallArray a -> b # foldr1 :: (a -> a -> a) -> SmallArray a -> a # foldl1 :: (a -> a -> a) -> SmallArray a -> a # toList :: SmallArray a -> [a] # null :: SmallArray a -> Bool # length :: SmallArray a -> Int # elem :: Eq a => a -> SmallArray a -> Bool # maximum :: Ord a => SmallArray a -> a # minimum :: Ord a => SmallArray a -> a # sum :: Num a => SmallArray a -> a # product :: Num a => SmallArray a -> a #
Traversable SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods traverse :: Applicative f => (a -> f b) -> SmallArray a -> f (SmallArray b) # sequenceA :: Applicative f => SmallArray (f a) -> f (SmallArray a) # mapM :: Monad m => (a -> m b) -> SmallArray a -> m (SmallArray b) # sequence :: Monad m => SmallArray (m a) -> m (SmallArray a) #
Eq1 SmallArray Source #	Since: 0.6.4.0
Instance details Defined in Data.Primitive.SmallArray Methods liftEq :: (a -> b -> Bool) -> SmallArray a -> SmallArray b -> Bool #
Ord1 SmallArray Source #	Since: 0.6.4.0
Instance details Defined in Data.Primitive.SmallArray Methods liftCompare :: (a -> b -> Ordering) -> SmallArray a -> SmallArray b -> Ordering #
Read1 SmallArray Source #	Since: 0.6.4.0
Instance details Defined in Data.Primitive.SmallArray Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (SmallArray a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [SmallArray a] # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (SmallArray a) # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [SmallArray a] #
Show1 SmallArray Source #	Since: 0.6.4.0
Instance details Defined in Data.Primitive.SmallArray Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> SmallArray a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [SmallArray a] -> ShowS #
MonadZip SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods mzip :: SmallArray a -> SmallArray b -> SmallArray (a, b) # mzipWith :: (a -> b -> c) -> SmallArray a -> SmallArray b -> SmallArray c # munzip :: SmallArray (a, b) -> (SmallArray a, SmallArray b) #
Alternative SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods empty :: SmallArray a # (<\|>) :: SmallArray a -> SmallArray a -> SmallArray a # some :: SmallArray a -> SmallArray [a] # many :: SmallArray a -> SmallArray [a] #
MonadPlus SmallArray Source #
Instance details Defined in Data.Primitive.SmallArray Methods mzero :: SmallArray a # mplus :: SmallArray a -> SmallArray a -> SmallArray a #
IsList (SmallArray a) Source #
Instance details Defined in Data.Primitive.SmallArray Associated Types type Item (SmallArray a) # Methods fromList :: [Item (SmallArray a)] -> SmallArray a # fromListN :: Int -> [Item (SmallArray a)] -> SmallArray a # toList :: SmallArray a -> [Item (SmallArray a)] #
Eq a => Eq (SmallArray a) Source #
Instance details Defined in Data.Primitive.SmallArray Methods (==) :: SmallArray a -> SmallArray a -> Bool # (/=) :: SmallArray a -> SmallArray a -> Bool #
Data a => Data (SmallArray a) Source #
Instance details Defined in Data.Primitive.SmallArray Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SmallArray a -> c (SmallArray a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SmallArray a) # toConstr :: SmallArray a -> Constr # dataTypeOf :: SmallArray a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SmallArray a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SmallArray a)) # gmapT :: (forall b. Data b => b -> b) -> SmallArray a -> SmallArray a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SmallArray a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SmallArray a -> r # gmapQ :: (forall d. Data d => d -> u) -> SmallArray a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> SmallArray a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> SmallArray a -> m (SmallArray a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallArray a -> m (SmallArray a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallArray a -> m (SmallArray a) #
Ord a => Ord (SmallArray a) Source #	Lexicographic ordering. Subject to change between major versions.
Instance details Defined in Data.Primitive.SmallArray Methods compare :: SmallArray a -> SmallArray a -> Ordering # (<) :: SmallArray a -> SmallArray a -> Bool # (<=) :: SmallArray a -> SmallArray a -> Bool # (>) :: SmallArray a -> SmallArray a -> Bool # (>=) :: SmallArray a -> SmallArray a -> Bool # max :: SmallArray a -> SmallArray a -> SmallArray a # min :: SmallArray a -> SmallArray a -> SmallArray a #
Read a => Read (SmallArray a) Source #
Instance details Defined in Data.Primitive.SmallArray Methods readsPrec :: Int -> ReadS (SmallArray a) # readList :: ReadS [SmallArray a] # readPrec :: ReadPrec (SmallArray a) # readListPrec :: ReadPrec [SmallArray a] #
Show a => Show (SmallArray a) Source #
Instance details Defined in Data.Primitive.SmallArray Methods showsPrec :: Int -> SmallArray a -> ShowS # show :: SmallArray a -> String # showList :: [SmallArray a] -> ShowS #
Semigroup (SmallArray a) Source #	Since: 0.6.3.0
Instance details Defined in Data.Primitive.SmallArray Methods (<>) :: SmallArray a -> SmallArray a -> SmallArray a # sconcat :: NonEmpty (SmallArray a) -> SmallArray a # stimes :: Integral b => b -> SmallArray a -> SmallArray a #
Monoid (SmallArray a) Source #
Instance details Defined in Data.Primitive.SmallArray Methods mempty :: SmallArray a # mappend :: SmallArray a -> SmallArray a -> SmallArray a # mconcat :: [SmallArray a] -> SmallArray a #
type Item (SmallArray a) Source #
Instance details Defined in Data.Primitive.SmallArray type Item (SmallArray a) = a

data SmallMutableArray s a Source #

Constructors

SmallMutableArray (SmallMutableArray# s a)

Instances

Instances details

Eq (SmallMutableArray s a) Source #
Instance details Defined in Data.Primitive.SmallArray Methods (==) :: SmallMutableArray s a -> SmallMutableArray s a -> Bool # (/=) :: SmallMutableArray s a -> SmallMutableArray s a -> Bool #
(Typeable s, Typeable a) => Data (SmallMutableArray s a) Source #
Instance details Defined in Data.Primitive.SmallArray Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SmallMutableArray s a -> c (SmallMutableArray s a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SmallMutableArray s a) # toConstr :: SmallMutableArray s a -> Constr # dataTypeOf :: SmallMutableArray s a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SmallMutableArray s a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SmallMutableArray s a)) # gmapT :: (forall b. Data b => b -> b) -> SmallMutableArray s a -> SmallMutableArray s a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SmallMutableArray s a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SmallMutableArray s a -> r # gmapQ :: (forall d. Data d => d -> u) -> SmallMutableArray s a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> SmallMutableArray s a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> SmallMutableArray s a -> m (SmallMutableArray s a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallMutableArray s a -> m (SmallMutableArray s a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallMutableArray s a -> m (SmallMutableArray s a) #

newSmallArray Source #

Arguments

:: PrimMonad m
=> Int	size
-> a	initial contents
-> m (SmallMutableArray (PrimState m) a)

Create a new small mutable array.

readSmallArray Source #

Arguments

:: PrimMonad m
=> SmallMutableArray (PrimState m) a	array
-> Int	index
-> m a

Read the element at a given index in a mutable array.

writeSmallArray Source #

Arguments

:: PrimMonad m
=> SmallMutableArray (PrimState m) a	array
-> Int	index
-> a	new element
-> m ()

Write an element at the given idex in a mutable array.

copySmallArray Source #

Arguments

:: PrimMonad m
=> SmallMutableArray (PrimState m) a	destination
-> Int	destination offset
-> SmallArray a	source
-> Int	source offset
-> Int	length
-> m ()

Copy a slice of an immutable array into a mutable array.

copySmallMutableArray Source #

Arguments

:: PrimMonad m
=> SmallMutableArray (PrimState m) a	destination
-> Int	destination offset
-> SmallMutableArray (PrimState m) a	source
-> Int	source offset
-> Int	length
-> m ()

Copy a slice of one mutable array into another.

indexSmallArray Source #

Arguments

:: SmallArray a	array
-> Int	index
-> a

Look up an element in an immutable array.

indexSmallArrayM Source #

Arguments

:: Monad m
=> SmallArray a	array
-> Int	index
-> m a

Look up an element in an immutable array.

The purpose of returning a result using a monad is to allow the caller to avoid retaining references to the array. Evaluating the return value will cause the array lookup to be performed, even though it may not require the element of the array to be evaluated (which could throw an exception). For instance:

data Box a = Box a
...

f sa = case indexSmallArrayM sa 0 of
  Box x -> ...

x is not a closure that references sa as it would be if we instead wrote:

let x = indexSmallArray sa 0

And does not prevent sa from being garbage collected.

Note that Identity is not adequate for this use, as it is a newtype, and cannot be evaluated without evaluating the element.

indexSmallArray## :: SmallArray a -> Int -> (# a #) Source #

Read a value from the immutable array at the given index, returning the result in an unboxed unary tuple. This is currently used to implement folds.

cloneSmallArray Source #

Arguments

:: SmallArray a	source
-> Int	offset
-> Int	length
-> SmallArray a

Create a copy of a slice of an immutable array.

cloneSmallMutableArray Source #

Arguments

:: PrimMonad m
=> SmallMutableArray (PrimState m) a	source
-> Int	offset
-> Int	length
-> m (SmallMutableArray (PrimState m) a)

Create a copy of a slice of a mutable array.

freezeSmallArray Source #

Arguments

:: PrimMonad m
=> SmallMutableArray (PrimState m) a	source
-> Int	offset
-> Int	length
-> m (SmallArray a)

Create an immutable array corresponding to a slice of a mutable array.

This operation copies the portion of the array to be frozen.

unsafeFreezeSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> m (SmallArray a) Source #

Render a mutable array immutable.

This operation performs no copying, so care must be taken not to modify the input array after freezing.

thawSmallArray Source #

Arguments

:: PrimMonad m
=> SmallArray a	source
-> Int	offset
-> Int	length
-> m (SmallMutableArray (PrimState m) a)

Create a mutable array corresponding to a slice of an immutable array.

This operation copies the portion of the array to be thawed.

runSmallArray :: (forall s. ST s (SmallMutableArray s a)) -> SmallArray a Source #

unsafeThawSmallArray :: PrimMonad m => SmallArray a -> m (SmallMutableArray (PrimState m) a) Source #

Render an immutable array mutable.

This operation performs no copying, so care must be taken with its use.

sizeofSmallArray :: SmallArray a -> Int Source #

sizeofSmallMutableArray :: SmallMutableArray s a -> Int Source #

smallArrayFromList :: [a] -> SmallArray a Source #

Create a SmallArray from a list.

smallArrayFromListN :: Int -> [a] -> SmallArray a Source #

Create a SmallArray from a list of a known length. If the length of the list does not match the given length, this throws an exception.

mapSmallArray' :: (a -> b) -> SmallArray a -> SmallArray b Source #

Strict map over the elements of the array.

traverseSmallArrayP :: PrimMonad m => (a -> m b) -> SmallArray a -> m (SmallArray b) Source #

This is the fastest, most straightforward way to traverse an array, but it only works correctly with a sufficiently "affine" PrimMonad instance. In particular, it must only produce *one* result array. ListT-transformed monads, for example, will not work right at all.