primitive-0.9.1.0: Primitive memory-related operations

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.

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 :: Applicative 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)
- unsafeThawSmallArray :: PrimMonad m => SmallArray a -> m (SmallMutableArray (PrimState m) a)
- runSmallArray :: (forall s. ST s (SmallMutableArray s a)) -> SmallArray a
- createSmallArray :: Int -> a -> (forall s. SmallMutableArray s a -> ST s ()) -> SmallArray a
- sizeofSmallArray :: SmallArray a -> Int
- getSizeofSmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> m Int
- sizeofSmallMutableArray :: SmallMutableArray s a -> Int
- shrinkSmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> m ()
- resizeSmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> a -> m (SmallMutableArray (PrimState m) a)
- emptySmallArray :: SmallArray a
- 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

MonadZip SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods mzip :: SmallArray a -> SmallArray b -> SmallArray (a, b) Source # mzipWith :: (a -> b -> c) -> SmallArray a -> SmallArray b -> SmallArray c Source # munzip :: SmallArray (a, b) -> (SmallArray a, SmallArray b) Source #
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 Source #
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 Source #
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) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [SmallArray a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (SmallArray a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [SmallArray a] Source #
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 Source # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [SmallArray a] -> ShowS Source #
NFData1 SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods liftRnf :: (a -> ()) -> SmallArray a -> () Source #
Alternative SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods empty :: SmallArray a Source # (<|>) :: SmallArray a -> SmallArray a -> SmallArray a Source # some :: SmallArray a -> SmallArray [a] Source # many :: SmallArray a -> SmallArray [a] Source #
Applicative SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods pure :: a -> SmallArray a Source # (<*>) :: SmallArray (a -> b) -> SmallArray a -> SmallArray b Source # liftA2 :: (a -> b -> c) -> SmallArray a -> SmallArray b -> SmallArray c Source # (*>) :: SmallArray a -> SmallArray b -> SmallArray b Source # (<*) :: SmallArray a -> SmallArray b -> SmallArray a Source #
Functor SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods fmap :: (a -> b) -> SmallArray a -> SmallArray b Source # (<$) :: a -> SmallArray b -> SmallArray a Source #
Monad SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods (>>=) :: SmallArray a -> (a -> SmallArray b) -> SmallArray b Source # (>>) :: SmallArray a -> SmallArray b -> SmallArray b Source # return :: a -> SmallArray a Source #
MonadPlus SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods mzero :: SmallArray a Source # mplus :: SmallArray a -> SmallArray a -> SmallArray a Source #
MonadFail SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods fail :: String -> SmallArray a Source #
MonadFix SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods mfix :: (a -> SmallArray a) -> SmallArray a Source #
Foldable SmallArray Source # |

Instance details

Defined in Data.Primitive.SmallArray

Methods

fold :: Monoid m => SmallArray m -> m Source #

foldMap :: Monoid m => (a -> m) -> SmallArray a -> m Source #

foldMap' :: Monoid m => (a -> m) -> SmallArray a -> m Source #

foldr :: (a -> b -> b) -> b -> SmallArray a -> b Source #

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

foldl :: (b -> a -> b) -> b -> SmallArray a -> b Source #

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

foldr1 :: (a -> a -> a) -> SmallArray a -> a Source #

foldl1 :: (a -> a -> a) -> SmallArray a -> a Source #

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

null :: SmallArray a -> Bool Source #

length :: SmallArray a -> Int Source #

elem :: Eq a => a -> SmallArray a -> Bool Source #

maximum :: Ord a => SmallArray a -> a Source #

minimum :: Ord a => SmallArray a -> a Source #

sum :: Num a => SmallArray a -> a Source #

product :: Num a => SmallArray a -> a Source #

Traversable SmallArray Source # |
Instance details Defined in Data.Primitive.SmallArray Methods traverse :: Applicative f => (a -> f b) -> SmallArray a -> f (SmallArray b) Source # sequenceA :: Applicative f => SmallArray (f a) -> f (SmallArray a) Source # mapM :: Monad m => (a -> m b) -> SmallArray a -> m (SmallArray b) Source # sequence :: Monad m => SmallArray (m a) -> m (SmallArray a) Source #
Lift a => Lift (SmallArray a :: Type) Source # |
Instance details Defined in Data.Primitive.SmallArray Methods lift :: Quote m => SmallArray a -> m Exp Source # liftTyped :: forall (m :: Type -> Type). Quote m => SmallArray a -> Code m (SmallArray a) Source #
NFData a => NFData (SmallArray a) Source # |
Instance details Defined in Data.Primitive.SmallArray Methods rnf :: SmallArray a -> () Source #
Monoid (SmallArray a) Source # |
Instance details Defined in Data.Primitive.SmallArray Methods mempty :: SmallArray a Source # mappend :: SmallArray a -> SmallArray a -> SmallArray a Source # mconcat :: [SmallArray a] -> SmallArray a Source #
Semigroup (SmallArray a) Source # | Since: 0.6.3.0
Instance details Defined in Data.Primitive.SmallArray Methods (<>) :: SmallArray a -> SmallArray a -> SmallArray a Source # sconcat :: NonEmpty (SmallArray a) -> SmallArray a Source # stimes :: Integral b => b -> SmallArray a -> SmallArray a Source #
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) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SmallArray a) Source #

toConstr :: SmallArray a -> Constr Source #

dataTypeOf :: SmallArray a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SmallArray a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SmallArray a)) Source #

gmapT :: (forall b. Data b => b -> b) -> SmallArray a -> SmallArray a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SmallArray a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SmallArray a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> SmallArray a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> SmallArray a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> SmallArray a -> m (SmallArray a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallArray a -> m (SmallArray a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallArray a -> m (SmallArray a) Source #

IsList (SmallArray a) Source # |

Instance details

Defined in Data.Primitive.SmallArray

Associated Types

type Item (SmallArray a) |
Instance details Defined in Data.Primitive.SmallArray type Item (SmallArray a) = a

Methods

fromList :: [Item (SmallArray a)] -> SmallArray a Source #

fromListN :: Int -> [Item (SmallArray a)] -> SmallArray a Source #

toList :: SmallArray a -> [Item (SmallArray a)] Source #

Read a => Read (SmallArray a) Source # |
Instance details Defined in Data.Primitive.SmallArray Methods readsPrec :: Int -> ReadS (SmallArray a) Source # readList :: ReadS [SmallArray a] Source # readPrec :: ReadPrec (SmallArray a) Source # readListPrec :: ReadPrec [SmallArray a] Source #
Show a => Show (SmallArray a) Source # |
Instance details Defined in Data.Primitive.SmallArray Methods showsPrec :: Int -> SmallArray a -> ShowS Source # show :: SmallArray a -> String Source # showList :: [SmallArray a] -> ShowS Source #
Eq a => Eq (SmallArray a) Source # |
Instance details Defined in Data.Primitive.SmallArray Methods (==) :: SmallArray a -> SmallArray a -> Bool Source # (/=) :: SmallArray a -> SmallArray a -> Bool Source #
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 Source #

(<) :: SmallArray a -> SmallArray a -> Bool Source #

(<=) :: SmallArray a -> SmallArray a -> Bool Source #

(>) :: SmallArray a -> SmallArray a -> Bool Source #

(>=) :: SmallArray a -> SmallArray a -> Bool Source #

max :: SmallArray a -> SmallArray a -> SmallArray a Source #

min :: SmallArray a -> SmallArray a -> SmallArray a Source #

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

(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) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SmallMutableArray s a) Source #

toConstr :: SmallMutableArray s a -> Constr Source #

dataTypeOf :: SmallMutableArray s a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SmallMutableArray s a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SmallMutableArray s a)) Source #

gmapT :: (forall b. Data b => b -> b) -> SmallMutableArray s a -> SmallMutableArray s a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SmallMutableArray s a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SmallMutableArray s a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> SmallMutableArray s a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> SmallMutableArray s a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> SmallMutableArray s a -> m (SmallMutableArray s a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallMutableArray s a -> m (SmallMutableArray s a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SmallMutableArray s a -> m (SmallMutableArray s a) Source #

Eq (SmallMutableArray s a) Source # |
Instance details Defined in Data.Primitive.SmallArray Methods (==) :: SmallMutableArray s a -> SmallMutableArray s a -> Bool Source # (/=) :: SmallMutableArray s a -> SmallMutableArray s a -> Bool Source #

newSmallArray Source #

Arguments

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

Create a new small mutable array.

Note: this function does not check if the input is non-negative.

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.

Note: this function does not do bounds checking.

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.

Note: this function does not do bounds checking.

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.

Note: this function does not do bounds or overlap checking.

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.

Note: this function does not do bounds or overlap checking.

indexSmallArray Source #

Arguments

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

Look up an element in an immutable array.

Note: this function does not do bounds checking.

indexSmallArrayM Source #

Arguments

:: Applicative m |
=> SmallArray a | array
-> Int | index
-> m a |

Look up an element in an immutable array.

The purpose of returning a result using an applicative 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

It also 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.

Note: this function does not do bounds checking.

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.

Note: this function does not do bounds checking.

cloneSmallArray Source #

Arguments

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

Create a copy of a slice of an immutable array.

Note: The provided array should contain the full subrange specified by the two Ints, but this is not checked.

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.

Note: The provided array should contain the full subrange specified by the two Ints, but this is not checked.

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.

Note: The provided array should contain the full subrange specified by the two Ints, but this is not checked.

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.

Note: The provided array should contain the full subrange specified by the two Ints, but this is not checked.

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.

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

Execute the monadic action and freeze the resulting array.

    runSmallArray m = runST $ m >>= unsafeFreezeSmallArray

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

Create an array of the given size with a default value, apply the monadic function and freeze the result. If the size is 0, return `emptySmallArray` (rather than a new copy thereof).

    createSmallArray 0 _ _ = emptySmallArray
    createSmallArray n x f = runSmallArray $ do
      mary <- newSmallArray n x
      f mary
      pure mary

sizeofSmallArray :: SmallArray a -> Int Source #

The number of elements in an immutable array.

getSizeofSmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> m Int Source #

Get the number of elements in a mutable array. Unlike `sizeofSmallMutableArray`, this function will be sure to produce the correct result if `SmallMutableArray` has been shrunk in place. Consider the following:

    do
      sa <- newSmallArray 10 x
      print $ sizeofSmallMutableArray sa
      shrinkSmallMutableArray sa 5
      print $ sizeofSmallMutableArray sa

The compiler is well within its rights to eliminate the second size check and print `10` twice. However, `getSizeofSmallMutableArray` will check the size each time it's executed (not evaluated), so it won't have this problem:

    do
      sa <- newSmallArray 10 x
      print =<< getSizeofSmallMutableArray sa
      shrinkSmallMutableArray sa 5
      print =<< getSizeofSmallMutableArray sa

will certainly print `10` and then `5`.

sizeofSmallMutableArray :: SmallMutableArray s a -> Int Source #

Deprecated: use getSizeofSmallMutableArray instead

The number of elements in a mutable array. This should only be used for arrays that are not shrunk in place.

This is deprecated and will be removed in a future release. Use `getSizeofSmallMutableArray` instead.

shrinkSmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> m () Source #

Shrink the mutable array in place. The size given must be equal to or less than the current size of the array. This is not checked.

resizeSmallMutableArray Source #

Arguments

:: PrimMonad m |
=> SmallMutableArray (PrimState m) a |
-> Int | New size
-> a | Newly created slots initialized to this element. Only used when array is grown.
-> m (SmallMutableArray (PrimState m) a) |

Resize a mutable array to new specified size. The returned `SmallMutableArray` is either the original `SmallMutableArray` resized in-place or, if not possible, a newly allocated `SmallMutableArray` with the original content copied over.

To avoid undefined behaviour, the original `SmallMutableArray` shall not be accessed anymore after a `resizeSmallMutableArray` has been performed. Moreover, no reference to the old one should be kept in order to allow garbage collection of the original `SmallMutableArray` in case a new `SmallMutableArray` had to be allocated.

emptySmallArray :: SmallArray a Source #

The empty `SmallArray`.

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.