-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A contiguous growable array type.
--
-- A contiguous growable array type. See the haddocks for more details.
@package growable-vector
@version 0.1
-- | Purpose
--
-- A contiguous growable array type with heap-allocated contents, written
-- Vec arr s a.
--
-- Vec has O(1) indexing, amortised O(1) push
-- (to the end), and O(1) pop (from the end).
--
-- A note about representation
--
-- The type exposed by this module is polymorphic in the type of array
-- backing the data structure, functionality which is provided by the
-- contiguous library. There are modules providing monomorphised
-- variants for better type inference. They are:
--
--
-- - GrowableVector.Lifted: backed by Array; for storing
-- lifted elements. This suits most Haskell types.
-- - GrowableVector.Lifted.Small: backed by SmallArray;
-- also for storing lifted elements, but more efficient for <= 128
-- elements.
-- - GrowableVector.Unlifted: backed by UnliftedArray;
-- for storing elements which can be unlifted (i.e., non-thunk pointers;
-- e.g., ByteArray, MVar, IORef). See the
-- PrimUnlifted typeclass for more details.
-- - GrowableVector.Unboxed: backed by PrimArray; for
-- storing elements which can be completely unboxed (i.e., non-thunk,
-- non-pointers; e.g., Int, Word, Char). See the
-- Prim typeclass for more details.
--
--
-- A note about type variable ordering
--
-- The type variables in this module will be ordered according to the
-- following precedence list (with higher precedence meaning left-most in
-- the forall-quantified type variables):
--
--
-- - The PrimMonad type variable, m
-- - The array type, arr
-- - The PrimState token, s
-- - The element type, a
-- - Everything else is unspecified (look at the forall)
--
--
-- This structuring is intended to document and ensure a uniform
-- experience for users of -XTypeApplications.
--
-- A note about ordering of arguments
--
-- The arguments of functions in this module will generally be ordered as
-- follows:
--
--
-- - The vector
-- - The index (e.g. when reading/writing)
-- - The element
--
--
-- As an example, write, which has all three of these, takes the
-- vector, then the index, then the element.
--
-- As another example, push, which does not take an index, takes
-- the vector, then the element.
--
-- Any function which accepts more than one of the types in the list, or
-- accepts a type which is not in the list, has no guarantee about its
-- argument order.
module GrowableVector
-- | Indexing
--
-- The Vec type allows access to values by (0-based) index. An
-- example will be more explicit:
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [0, 2, 4, 6]
--
-- >>> two <- unsafeRead vec 1
--
-- >>> unsafeWrite vec 1 7
--
-- >>> seven <- unsafeRead vec 1
--
-- >>> two + seven
-- 9
--
--
-- However, be careful: if you try to access an index which isn't in the
-- Vec, your program will exhibit undefined behaviour ("UB"),
-- either returning garbage or segfaulting. You cannot do this:
--
--
-- v <- fromFoldable [0, 2, 4, 6]
-- unsafeRead v 6 -- this is UB
--
--
--
-- If you want safe access, use read:
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [0, 2, 4, 6]
--
-- >>> read vec 1
-- Just 2
--
-- >>> read vec 6
-- Nothing
--
--
-- Capacity and reallocation
--
-- The capacity of a vector is the amount of space allocated for any
-- future elements that will be added onto the vector. This is not to be
-- confused with the length of a vector, which specifies the
-- number of actual elements within the vector. If a vector's length
-- exceeds its capacity, its capacity will automatically be increased,
-- but its elements will have to be reallocated.
--
-- For example, a vector with capacity 10 and length 0 would be an empty
-- vector with space for 10 more elements. Pushing 10 or fewer elements
-- onto the vector will not change its capacity or cause reallocation to
-- occur. However, if the vector's length is increased to 11, it will
-- have to reallocate, which can be slow. For this reason, it is
-- recommended to use withCapacity whenever possible to specify
-- how big the vector is expected to get.
--
-- Guarantees
--
-- Vec is a (pointer, capacity, length) triplet. The pointer will
-- never be null.
--
-- Because of the semantics of the GHC runtime, creating a new vector
-- will always allocate. In particular, if you construct a
-- MutablePrimArray-backed Vec with capacity 0 via
-- new 0, fromFoldable [], or
-- shrinkToFit on an empty Vec, the 16-byte header
-- to GHC ByteArray# will be allocated, but nothing else (for the
-- curious: this is needed for sameMutableByteArray# to work).
-- Similarly, if you store zero-sized types inside such a Vec, it
-- will not allocate space for them. Note that in this case the
-- Vec may not report a capacity of 0. Vec will
-- allocate if and only if 'sizeOf (undefined :: a) *
-- capacity > 0.
--
-- If a Vec has allocated memory, then the memory it points
-- to is on the heap (as defined by GHC's allocator), and its pointer
-- points to length initialised, contiguous elements in order
-- (i.e. what you would see if you turned it into a list), followed by
-- capacity - length logically
-- uninitialised, contiguous elements.
--
-- Vec will never automatically shrink itself, even if completely
-- empty. This ensures no unnecessary allocations or deallocations occur.
-- Emptying a Vec and then filling it back up to the same
-- length should incur no calls to the allocator. If you wish to
-- free up unused memory, use shrinkToFit.
--
-- push will never (re)allocate if the reported capacity is
-- sufficient. push will (re)allocate if length
-- == capacity. That is, the reported capacity is
-- completely accurate, and can be relied on. Bulk insertion methods
-- may reallocate, even when not necessary.
--
-- Vec does not guarantee any particular growth strategy when
-- reallocating when full, nor when reserve is called. The
-- strategy is basic and may prove desirable to use a non-constant growth
-- factor. Whatever strategy is used will of course guarantee O(1)
-- amortised push.
--
-- fromFoldable and withCapacity will produce a Vec
-- with exactly the requested capacity.
--
-- Vec will not specifically overwrite any data that is removed
-- from it, but also won't specifically preserve it. Its uninitialised
-- memory is scratch space that it may use however it wants. It will
-- generally just do whatever is most efficient or otherwise easy to
-- implement. Do not rely on removed data to be erased for security
-- purposes. Even if a Vec drops out of scope, its buffer may
-- simply be reused by another Vec. Even if you zero a Vecs
-- memory first, this may not actually happen when you think it does
-- because of Garbage Collection.
data Vec arr s a
-- | <math>. Constructs a new, empty Vec arr s a.
--
--
-- >>> vec <- new @_ @Array @_ @Int
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 0) (capacity vec)
--
new :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => m (Vec arr s a)
-- | <math>. Constructs a new, empty Vec arr s a.
--
-- The vector will be able to hold exactly capacity elements
-- without reallocating. It is important to note that althrough the
-- returned vector has the capacity specified, with vector will
-- have a zero length.
--
--
-- >>> vec <- withCapacity @_ @SmallArray @_ @Int 10
-- -- The vector contains no items, even though it has capacity for more
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- These are all done without reallocating...
--
-- >>> forM_ [1..10] $ \i -> push vec i
--
-- >>> assertM (== 10) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- ..but this may make the vector reallocate
--
-- >>> push vec 11
--
-- >>> assertM (== 11) (length vec)
--
-- >>> assertM (>= 11) (capacity vec)
--
withCapacity :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Word -> m (Vec arr s a)
-- | <math>. Returns the number of elements in the vector.
length :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> m Word
-- | <math>. Returns the maximum number of elements the vector can
-- hold without reallocating.
--
--
-- >>> vec <- withCapacity @_ @PrimArray @_ @Word 10
--
-- >>> push vec 42
--
-- >>> assertM (== 10) (capacity vec)
--
capacity :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> m Word
-- | <math>. Reserves capacity for at least additional more
-- elements to be inserted in the given Vec arr s a. The
-- collection may reserve more space to avoid frequent reallocations.
-- After calling reserve, capacity will be greater than or equal
-- to length + additional. Does nothing if capacity is already
-- sufficient.
--
--
-- >>> vec <- fromFoldable @_ @PrimArray @_ @Int @_ [1]
--
-- >>> reserve vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserve :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> Word -> m ()
-- | <math>. Reserves the minimum capacity for exactly
-- additional more elements to be inserted in the given
-- Vec arr s a. After calling reserveExact,
-- capacity will be greater than or equal to length +
-- additional. Does nothing if the capacity is already sufficient.
--
-- Capacity cannot be relied upon to be precisely minimal. Prefer
-- reserve if future insertions are expected.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int @_ [1]
--
-- >>> reserveExact vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserveExact :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> Word -> m ()
-- | <math>. Shrinks the capacity of the vector as much as possible.
--
--
-- >>> vec <- withCapacity @_ @Array @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkToFit vec
--
-- >>> assertM (== 3) (capacity vec)
--
shrinkToFit :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> m ()
-- | <math>. Shrinks the capacity of the vector with a lower bound.
--
-- The capacity will remain at least as large as both the length and the
-- supplied value.
--
-- If the current capacity is less than the lower limit, this is a no-op.
--
--
-- >>> vec <- withCapacity @_ @Array @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkTo vec 4
--
-- >>> assertM (>= 4) (capacity vec)
--
-- >>> shrinkTo vec 0
--
-- >>> assertM (>= 3) (capacity vec)
--
shrinkTo :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> Word -> m ()
-- | <math>. Return the element at the given position.
--
-- If the element index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length).
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using read instead.
unsafeRead :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> Word -> m a
-- | <math>. Return the element at the given position, or
-- Nothing if the index is out of bounds.
--
-- The bounds are defined as [0, length).
read :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> Word -> m (Maybe a)
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using write instead.
unsafeWrite :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> Word -> a -> m ()
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is in bounds, this returns Just (). If
-- the index is out of bounds, this returns Nothing.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
write :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> Word -> a -> m (Maybe ())
-- | Amortised <math>. Appends an element to the vector.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [1, 2]
--
-- >>> push vec 3
--
-- >>> assertM (== [1, 2, 3]) (toList vec)
--
push :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> a -> m ()
-- | <math>. Removes the last element from a vector and returns it,
-- or Nothing if it is empty.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [1, 2, 3]
--
-- >>> assertM (== Just 3) (pop vec)
--
-- >>> assertM (== [1, 2]) (toList vec)
--
pop :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> m (Maybe a)
-- | <math>. Extend the vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Char ['a', 'b', 'c']
--
-- >>> extend vec ['d', 'e', 'f']
--
-- >>> assertM (== "abcdef") (toList vec)
--
extend :: forall m arr s a t. (MonadPrim s m, Contiguous arr, Element arr a, Foldable t) => Vec arr s a -> t a -> m ()
-- | <math>. Create a vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [1..10]
--
-- >>> assertM (== [1..10]) (toList vec)
--
fromFoldable :: forall m arr s a t. (MonadPrim s m, Contiguous arr, Element arr a, Foldable t) => t a -> m (Vec arr s a)
-- | <math>. Create a list with the elements of the vector.
--
--
-- >>> vec <- new @_ @PrimArray @_ @Int
--
-- >>> extend vec [1..5]
--
-- >>> toList vec
-- [1,2,3,4,5]
--
toList :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> m [a]
-- | <math>. Create a lifted Vector copy of a vector.
toLiftedVector :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => Vec arr s a -> m (Vector a)
-- | <math>. Create a lifted Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toLiftedVectorWith :: forall m arr s a b. (MonadPrim s m, Contiguous arr, Element arr a) => (Word -> a -> m b) -> Vec arr s a -> m (Vector b)
-- | <math>. Create a Primitive Vector copy of a vector.
toPrimitiveVector :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a, Prim a) => Vec arr s a -> m (Vector a)
-- | <math>. Create a Primitive Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toPrimitiveVectorWith :: forall m arr s a b. (MonadPrim s m, Contiguous arr, Element arr a, Prim b) => (Word -> a -> m b) -> Vec arr s a -> m (Vector b)
-- | <math>. Create a Storable Vector copy of a vector.
toStorableVector :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a, Storable a) => Vec arr s a -> m (Vector a)
-- | <math>. Create a Storable Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toStorableVectorWith :: forall m arr s a b. (MonadPrim s m, Contiguous arr, Element arr a, Storable b) => (Word -> a -> m b) -> Vec arr s a -> m (Vector b)
-- | <math>. Map over an array, modifying the elements in place.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [1..10]
--
-- >>> map (+ 1) vec
--
-- >>> assertM (== [2, 3 .. 11]) (toList vec)
--
map :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => (a -> a) -> Vec arr s a -> m ()
-- | <math>. Map strictly over an array, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [1..10]
--
-- >>> map' (* 2) vec
--
-- >>> assertM (== [2, 4 .. 20]) (toList vec)
--
map' :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => (a -> a) -> Vec arr s a -> m ()
-- | <math>. Map over an array with a function that takes the index
-- and its corresponding element as input, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [1..10]
--
-- >>> imap (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => (Word -> a -> a) -> Vec arr s a -> m ()
-- | <math>. Map strictly over an array with a function that takes
-- the index and its corresponding element as input, modifying the
-- elements in place.
--
--
-- >>> vec <- fromFoldable @_ @Array @_ @Int [1..10]
--
-- >>> imap' (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap' :: forall m arr s a. (MonadPrim s m, Contiguous arr, Element arr a) => (Word -> a -> a) -> Vec arr s a -> m ()
-- | Purpose
--
-- A contiguous growable array type with heap-allocated contents, written
-- Vec s a.
--
-- Vec has O(1) indexing, amortised O(1) push
-- (to the end), and O(1) pop (from the end).
--
-- A note about representation
--
-- The type exposed by this module is backed by an Array; and thus
-- is suitable for storing lifted elements. This suits most Haskell
-- types. See the module-level documentation for GrowableVector to
-- see what other types are provided, and which may be more optimal for
-- your use-case.
--
-- A note about type variable ordering
--
-- The type variables in this module will be ordered according to the
-- following precedence list (with higher precedence meaning left-most in
-- the forall-quantified type variables):
--
--
-- - The PrimMonad type variable, m
-- - The PrimState token, s
-- - The element type, a
-- - Everything else is unspecified (look at the forall)
--
--
-- This structuring is intended to document and ensure a uniform
-- experience for users of -XTypeApplications.
--
-- A note about ordering of arguments
--
-- The arguments of functions in this module will generally be ordered as
-- follows:
--
--
-- - The vector
-- - The index (e.g. when reading/writing)
-- - The element
--
--
-- As an example, write, which has all three of these, takes the
-- vector, then the index, then the element.
--
-- As another example, push, which does not take an index, takes
-- the vector, then the element.
--
-- Any function which accepts more than one of the types in the list, or
-- accepts a type which is not in the list, has no guarantee about its
-- argument order.
module GrowableVector.Lifted
-- | Indexing
--
-- The Vec type allows access to values by (0-based) index. An
-- example will be more explicit:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> two <- unsafeRead vec 1
--
-- >>> unsafeWrite vec 1 7
--
-- >>> seven <- unsafeRead vec 1
--
-- >>> two + seven
-- 9
--
--
-- However, be careful: if you try to access an index which isn't in the
-- Vec, your program will exhibit undefined behaviour ("UB"),
-- either returning garbage or segfaulting. You cannot do this:
--
--
-- v <- fromFoldable [0, 2, 4, 6]
-- unsafeRead v 6 -- this is UB
--
--
--
-- If you want safe access, use read:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> read vec 1
-- Just 2
--
-- >>> read vec 6
-- Nothing
--
--
-- Capacity and reallocation
--
-- The capacity of a vector is the amount of space allocated for any
-- future elements that will be added onto the vector. This is not to be
-- confused with the length of a vector, which specifies the
-- number of actual elements within the vector. If a vector's length
-- exceeds its capacity, its capacity will automatically be increased,
-- but its elements will have to be reallocated.
--
-- For example, a vector with capacity 10 and length 0 would be an empty
-- vector with space for 10 more elements. Pushing 10 or fewer elements
-- onto the vector will not change its capacity or cause reallocation to
-- occur. However, if the vector's length is increased to 11, it will
-- have to reallocate, which can be slow. For this reason, it is
-- recommended to use withCapacity whenever possible to specify
-- how big the vector is expected to get.
--
-- Guarantees
--
-- Vec is a (pointer, capacity, length) triplet. The pointer will
-- never be null.
--
-- Because of the semantics of the GHC runtime, creating a new vector
-- will always allocate. In particular, if you construct a
-- MutableArray-backed Vec with capacity 0 via
-- new 0, fromFoldable [], or
-- shrinkToFit on an empty Vec, the 16-byte header
-- to GHC 'ByteArray#' will be allocated, but nothing else (for the
-- curious: this is needed for 'sameMutableByteArray#' to work).
-- Similarly, if you store zero-sized types inside such a Vec, it
-- will not allocate space for them. Note that in this case the
-- Vec may not report a capacity of 0. Vec will
-- allocate if and only if 'sizeOf (undefined :: a) *
-- capacity > 0.
--
-- If a Vec has allocated memory, then the memory it points
-- to is on the heap (as defined by GHC's allocator), and its pointer
-- points to length initialised, contiguous elements in order
-- (i.e. what you would see if you turned it into a list), followed by
-- capacity - length logically
-- uninitialised, contiguous elements.
--
-- Vec will never automatically shrink itself, even if completely
-- empty. This ensures no unnecessary allocations or deallocations occur.
-- Emptying a Vec and then filling it back up to the same
-- length should incur no calls to the allocator. If you wish to
-- free up unused memory, use shrinkToFit.
--
-- push will never (re)allocate if the reported capacity is
-- sufficient. push will (re)allocate if length
-- == capacity. That is, the reported capacity is
-- completely accurate, and can be relied on. Bulk insertion methods
-- may reallocate, even when not necessary.
--
-- Vec does not guarantee any particular growth strategy when
-- reallocating when full, nor when reserve is called. The
-- strategy is basic and may prove desirable to use a non-constant growth
-- factor. Whatever strategy is used will of course guarantee O(1)
-- amortised push.
--
-- fromFoldable and withCapacity will produce a Vec
-- with exactly the requested capacity.
--
-- Vec will not specifically overwrite any data that is removed
-- from it, but also won't specifically preserve it. Its uninitialised
-- memory is scratch space that it may use however it wants. It will
-- generally just do whatever is most efficient or otherwise easy to
-- implement. Do not rely on removed data to be erased for security
-- purposes. Even if a Vec drops out of scope, its buffer may
-- simply be reused by another Vec. Even if you zero a Vecs
-- memory first, this may not actually happen when you think it does
-- because of Garbage Collection.
data Vec s a
-- | <math>. Constructs a new, empty Vec s a.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 0) (capacity vec)
--
new :: forall m s a. MonadPrim s m => m (Vec s a)
-- | <math>. Constructs a new, empty Vec arr s a.
--
-- The vector will be able to hold exactly capacity elements
-- without reallocating. It is important to note that althrough the
-- returned vector has the capacity specified, with vector will
-- have a zero length.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
-- -- The vector contains no items, even though it has capacity for more
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- These are all done without reallocating...
--
-- >>> forM_ [1..10] $ \i -> push vec i
--
-- >>> assertM (== 10) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- ..but this may make the vector reallocate
--
-- >>> push vec 11
--
-- >>> assertM (== 11) (length vec)
--
-- >>> assertM (>= 11) (capacity vec)
--
withCapacity :: forall m s a. MonadPrim s m => Word -> m (Vec s a)
-- | <math>. Returns the number of elements in the vector.
length :: forall m s a. MonadPrim s m => Vec s a -> m Word
-- | <math>. Returns the maximum number of elements the vector can
-- hold without reallocating.
--
--
-- >>> vec <- withCapacity @_ @_ @Word 10
--
-- >>> push vec 42
--
-- >>> assertM (== 10) (capacity vec)
--
capacity :: forall m s a. MonadPrim s m => Vec s a -> m Word
-- | <math>. Reserves capacity for at least additional more
-- elements to be inserted in the given Vec s a. The
-- collection may reserve more space to avoid frequent reallocations.
-- After calling reserve, capacity will be greater than or equal
-- to length + additional. Does nothing if capacity is already
-- sufficient.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserve vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserve :: forall m s a. MonadPrim s m => Vec s a -> Word -> m ()
-- | <math>. Reserves the minimum capacity for exactly
-- additional more elements to be inserted in the given
-- Vec s a. After calling reserveExact, capacity
-- will be greater than or equal to length + additional. Does
-- nothing if the capacity is already sufficient.
--
-- Capacity cannot be relied upon to be precisely minimal. Prefer
-- reserve if future insertions are expected.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserveExact vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserveExact :: forall m s a. MonadPrim s m => Vec s a -> Word -> m ()
-- | <math>. Shrinks the capacity of the vector as much as possible.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkToFit vec
--
-- >>> assertM (== 3) (capacity vec)
--
shrinkToFit :: forall m s a. MonadPrim s m => Vec s a -> m ()
-- | <math>. Shrinks the capacity of the vector with a lower bound.
--
-- The capacity will remain at least as large as both the length and the
-- supplied value.
--
-- If the current capacity is less than the lower limit, this is a no-op.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkTo vec 4
--
-- >>> assertM (>= 4) (capacity vec)
--
-- >>> shrinkTo vec 0
--
-- >>> assertM (>= 3) (capacity vec)
--
shrinkTo :: forall m s a. MonadPrim s m => Vec s a -> Word -> m ()
-- | <math>. Return the element at the given position.
--
-- If the element index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length).
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using read instead.
unsafeRead :: forall m s a. MonadPrim s m => Vec s a -> Word -> m a
-- | <math>. Return the element at the given position, or
-- Nothing if the index is out of bounds.
--
-- The bounds are defined as [0, length).
read :: forall m s a. MonadPrim s m => Vec s a -> Word -> m (Maybe a)
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using write instead.
unsafeWrite :: forall m s a. MonadPrim s m => Vec s a -> Word -> a -> m ()
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is in bounds, this returns Just (). If
-- the index is out of bounds, this returns Nothing.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
write :: forall m s a. MonadPrim s m => Vec s a -> Word -> a -> m (Maybe ())
-- | Amortised <math>. Appends an element to the vector.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2]
--
-- >>> push vec 3
--
-- >>> assertM (== [1, 2, 3]) (toList vec)
--
push :: forall m s a. MonadPrim s m => Vec s a -> a -> m ()
-- | <math>. Removes the last element from a vector and returns it,
-- or Nothing if it is empty.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2, 3]
--
-- >>> assertM (== Just 3) (pop vec)
--
-- >>> assertM (== [1, 2]) (toList vec)
--
pop :: forall m s a. MonadPrim s m => Vec s a -> m (Maybe a)
-- | <math>. Extend the vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Char ['a', 'b', 'c']
--
-- >>> extend vec ['d', 'e', 'f']
--
-- >>> assertM (== "abcdef") (toList vec)
--
extend :: forall m s a t. (MonadPrim s m, Foldable t) => Vec s a -> t a -> m ()
-- | <math>. Create a vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> assertM (== [1..10]) (toList vec)
--
fromFoldable :: forall m s a t. (MonadPrim s m, Foldable t) => t a -> m (Vec s a)
-- | <math>. Create a list with the elements of the vector.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> extend vec [1..5]
--
-- >>> toList vec
-- [1,2,3,4,5]
--
toList :: forall m s a. MonadPrim s m => Vec s a -> m [a]
-- | <math>. Create a lifted Vector copy of a vector.
toLiftedVector :: forall m s a. MonadPrim s m => Vec s a -> m (Vector a)
-- | <math>. Create a lifted Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toLiftedVectorWith :: forall m s a b. MonadPrim s m => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Primitive Vector copy of a vector.
toPrimitiveVector :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m (Vector a)
-- | <math>. Create a Primitive Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toPrimitiveVectorWith :: forall m s a b. (MonadPrim s m, Prim b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Storable Vector copy of a vector.
toStorableVector :: forall m s a. (MonadPrim s m, Storable a) => Vec s a -> m (Vector a)
-- | <math>. Create a Storable Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toStorableVectorWith :: forall m s a b. (MonadPrim s m, Storable b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Map over an array, modifying the elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map (+ 1) vec
--
-- >>> assertM (== [2, 3 .. 11]) (toList vec)
--
map :: forall m s a. MonadPrim s m => (a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map' (* 2) vec
--
-- >>> assertM (== [2, 4 .. 20]) (toList vec)
--
map' :: forall m s a. MonadPrim s m => (a -> a) -> Vec s a -> m ()
-- | <math>. Map over an array with a function that takes the index
-- and its corresponding element as input, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap :: forall m s a. MonadPrim s m => (Word -> a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array with a function that takes
-- the index and its corresponding element as input, modifying the
-- elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap' (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap' :: forall m s a. MonadPrim s m => (Word -> a -> a) -> Vec s a -> m ()
-- | Purpose
--
-- A contiguous growable array type with heap-allocated contents, written
-- Vec s a.
--
-- Vec has O(1) indexing, amortised O(1) push
-- (to the end), and O(1) pop (from the end).
--
-- A note about representation
--
-- The type exposed by this module is backed by a SmallArray; and
-- thus is suitable for storing lifted elements. This suits most Haskell
-- types. This module is more efficient than GrowableVector.Lifted
-- when there are <= 128 elements. See the module-level documentation
-- for GrowableVector to see what other types are provided, and
-- which one may be more optimal for your use-case.
--
-- A note about type variable ordering
--
-- The type variables in this module will be ordered according to the
-- following precedence list (with higher precedence meaning left-most in
-- the forall-quantified type variables):
--
--
-- - The PrimMonad type variable, m
-- - The PrimState token, s
-- - The element type, a
-- - Everything else is unspecified (look at the forall)
--
--
-- This structuring is intended to document and ensure a uniform
-- experience for users of -XTypeApplications.
--
-- A note about ordering of arguments
--
-- The arguments of functions in this module will generally be ordered as
-- follows:
--
--
-- - The vector
-- - The index (e.g. when reading/writing)
-- - The element
--
--
-- As an example, write, which has all three of these, takes the
-- vector, then the index, then the element.
--
-- As another example, push, which does not take an index, takes
-- the vector, then the element.
--
-- Any function which accepts more than one of the types in the list, or
-- accepts a type which is not in the list, has no guarantee about its
-- argument order.
module GrowableVector.Lifted.Small
-- | Indexing
--
-- The Vec type allows access to values by (0-based) index. An
-- example will be more explicit:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> two <- unsafeRead vec 1
--
-- >>> unsafeWrite vec 1 7
--
-- >>> seven <- unsafeRead vec 1
--
-- >>> two + seven
-- 9
--
--
-- However, be careful: if you try to access an index which isn't in the
-- Vec, your program will exhibit undefined behaviour ("UB"),
-- either returning garbage or segfaulting. You cannot do this:
--
--
-- v <- fromFoldable [0, 2, 4, 6]
-- unsafeRead v 6 -- this is UB
--
--
--
-- If you want safe access, use read:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> read vec 1
-- Just 2
--
-- >>> read vec 6
-- Nothing
--
--
-- Capacity and reallocation
--
-- The capacity of a vector is the amount of space allocated for any
-- future elements that will be added onto the vector. This is not to be
-- confused with the length of a vector, which specifies the
-- number of actual elements within the vector. If a vector's length
-- exceeds its capacity, its capacity will automatically be increased,
-- but its elements will have to be reallocated.
--
-- For example, a vector with capacity 10 and length 0 would be an empty
-- vector with space for 10 more elements. Pushing 10 or fewer elements
-- onto the vector will not change its capacity or cause reallocation to
-- occur. However, if the vector's length is increased to 11, it will
-- have to reallocate, which can be slow. For this reason, it is
-- recommended to use withCapacity whenever possible to specify
-- how big the vector is expected to get.
--
-- Guarantees
--
-- Vec is a (pointer, capacity, length) triplet. The pointer will
-- never be null.
--
-- Because of the semantics of the GHC runtime, creating a new vector
-- will always allocate. In particular, if you construct a
-- MutableArray-backed Vec with capacity 0 via
-- new 0, fromFoldable [], or
-- shrinkToFit on an empty Vec, the 16-byte header
-- to GHC 'ByteArray#' will be allocated, but nothing else (for the
-- curious: this is needed for 'sameMutableByteArray#' to work).
-- Similarly, if you store zero-sized types inside such a Vec, it
-- will not allocate space for them. Note that in this case the
-- Vec may not report a capacity of 0. Vec will
-- allocate if and only if 'sizeOf (undefined :: a) *
-- capacity > 0.
--
-- If a Vec has allocated memory, then the memory it points
-- to is on the heap (as defined by GHC's allocator), and its pointer
-- points to length initialised, contiguous elements in order
-- (i.e. what you would see if you turned it into a list), followed by
-- capacity - length logically
-- uninitialised, contiguous elements.
--
-- Vec will never automatically shrink itself, even if completely
-- empty. This ensures no unnecessary allocations or deallocations occur.
-- Emptying a Vec and then filling it back up to the same
-- length should incur no calls to the allocator. If you wish to
-- free up unused memory, use shrinkToFit.
--
-- push will never (re)allocate if the reported capacity is
-- sufficient. push will (re)allocate if length
-- == capacity. That is, the reported capacity is
-- completely accurate, and can be relied on. Bulk insertion methods
-- may reallocate, even when not necessary.
--
-- Vec does not guarantee any particular growth strategy when
-- reallocating when full, nor when reserve is called. The
-- strategy is basic and may prove desirable to use a non-constant growth
-- factor. Whatever strategy is used will of course guarantee O(1)
-- amortised push.
--
-- fromFoldable and withCapacity will produce a Vec
-- with exactly the requested capacity.
--
-- Vec will not specifically overwrite any data that is removed
-- from it, but also won't specifically preserve it. Its uninitialised
-- memory is scratch space that it may use however it wants. It will
-- generally just do whatever is most efficient or otherwise easy to
-- implement. Do not rely on removed data to be erased for security
-- purposes. Even if a Vec drops out of scope, its buffer may
-- simply be reused by another Vec. Even if you zero a Vecs
-- memory first, this may not actually happen when you think it does
-- because of Garbage Collection.
data Vec s a
-- | <math>. Constructs a new, empty Vec s a.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 0) (capacity vec)
--
new :: forall m s a. MonadPrim s m => m (Vec s a)
-- | <math>. Constructs a new, empty Vec arr s a.
--
-- The vector will be able to hold exactly capacity elements
-- without reallocating. It is important to note that althrough the
-- returned vector has the capacity specified, with vector will
-- have a zero length.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
-- -- The vector contains no items, even though it has capacity for more
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- These are all done without reallocating...
--
-- >>> forM_ [1..10] $ \i -> push vec i
--
-- >>> assertM (== 10) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- ..but this may make the vector reallocate
--
-- >>> push vec 11
--
-- >>> assertM (== 11) (length vec)
--
-- >>> assertM (>= 11) (capacity vec)
--
withCapacity :: forall m s a. MonadPrim s m => Word -> m (Vec s a)
-- | <math>. Returns the number of elements in the vector.
length :: forall m s a. MonadPrim s m => Vec s a -> m Word
-- | <math>. Returns the maximum number of elements the vector can
-- hold without reallocating.
--
--
-- >>> vec <- withCapacity @_ @_ @Word 10
--
-- >>> push vec 42
--
-- >>> assertM (== 10) (capacity vec)
--
capacity :: forall m s a. MonadPrim s m => Vec s a -> m Word
-- | <math>. Reserves capacity for at least additional more
-- elements to be inserted in the given Vec s a. The
-- collection may reserve more space to avoid frequent reallocations.
-- After calling reserve, capacity will be greater than or equal
-- to length + additional. Does nothing if capacity is already
-- sufficient.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserve vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserve :: forall m s a. MonadPrim s m => Vec s a -> Word -> m ()
-- | <math>. Reserves the minimum capacity for exactly
-- additional more elements to be inserted in the given
-- Vec s a. After calling reserveExact, capacity
-- will be greater than or equal to length + additional. Does
-- nothing if the capacity is already sufficient.
--
-- Capacity cannot be relied upon to be precisely minimal. Prefer
-- reserve if future insertions are expected.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserveExact vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserveExact :: forall m s a. MonadPrim s m => Vec s a -> Word -> m ()
-- | <math>. Shrinks the capacity of the vector as much as possible.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkToFit vec
--
-- >>> assertM (== 3) (capacity vec)
--
shrinkToFit :: forall m s a. MonadPrim s m => Vec s a -> m ()
-- | <math>. Shrinks the capacity of the vector with a lower bound.
--
-- The capacity will remain at least as large as both the length and the
-- supplied value.
--
-- If the current capacity is less than the lower limit, this is a no-op.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkTo vec 4
--
-- >>> assertM (>= 4) (capacity vec)
--
-- >>> shrinkTo vec 0
--
-- >>> assertM (>= 3) (capacity vec)
--
shrinkTo :: forall m s a. MonadPrim s m => Vec s a -> Word -> m ()
-- | <math>. Return the element at the given position.
--
-- If the element index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length).
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using read instead.
unsafeRead :: forall m s a. MonadPrim s m => Vec s a -> Word -> m a
-- | <math>. Return the element at the given position, or
-- Nothing if the index is out of bounds.
--
-- The bounds are defined as [0, length).
read :: forall m s a. MonadPrim s m => Vec s a -> Word -> m (Maybe a)
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using write instead.
unsafeWrite :: forall m s a. MonadPrim s m => Vec s a -> Word -> a -> m ()
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is in bounds, this returns Just (). If
-- the index is out of bounds, this returns Nothing.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
write :: forall m s a. MonadPrim s m => Vec s a -> Word -> a -> m (Maybe ())
-- | Amortised <math>. Appends an element to the vector.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2]
--
-- >>> push vec 3
--
-- >>> assertM (== [1, 2, 3]) (toList vec)
--
push :: forall m s a. MonadPrim s m => Vec s a -> a -> m ()
-- | <math>. Removes the last element from a vector and returns it,
-- or Nothing if it is empty.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2, 3]
--
-- >>> assertM (== Just 3) (pop vec)
--
-- >>> assertM (== [1, 2]) (toList vec)
--
pop :: forall m s a. MonadPrim s m => Vec s a -> m (Maybe a)
-- | <math>. Extend the vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Char ['a', 'b', 'c']
--
-- >>> extend vec ['d', 'e', 'f']
--
-- >>> assertM (== "abcdef") (toList vec)
--
extend :: forall m s a t. (MonadPrim s m, Foldable t) => Vec s a -> t a -> m ()
-- | <math>. Create a vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> assertM (== [1..10]) (toList vec)
--
fromFoldable :: forall m s a t. (MonadPrim s m, Foldable t) => t a -> m (Vec s a)
-- | <math>. Create a list with the elements of the vector.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> extend vec [1..5]
--
-- >>> toList vec
-- [1,2,3,4,5]
--
toList :: forall m s a. MonadPrim s m => Vec s a -> m [a]
-- | <math>. Create a lifted Vector copy of a vector.
toLiftedVector :: forall m s a. MonadPrim s m => Vec s a -> m (Vector a)
-- | <math>. Create a lifted Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toLiftedVectorWith :: forall m s a b. MonadPrim s m => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Primitive Vector copy of a vector.
toPrimitiveVector :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m (Vector a)
-- | <math>. Create a Primitive Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toPrimitiveVectorWith :: forall m s a b. (MonadPrim s m, Prim b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Storable Vector copy of a vector.
toStorableVector :: forall m s a. (MonadPrim s m, Storable a) => Vec s a -> m (Vector a)
-- | <math>. Create a Storable Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toStorableVectorWith :: forall m s a b. (MonadPrim s m, Storable b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Map over an array, modifying the elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map (+ 1) vec
--
-- >>> assertM (== [2, 3 .. 11]) (toList vec)
--
map :: forall m s a. MonadPrim s m => (a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map' (* 2) vec
--
-- >>> assertM (== [2, 4 .. 20]) (toList vec)
--
map' :: forall m s a. MonadPrim s m => (a -> a) -> Vec s a -> m ()
-- | <math>. Map over an array with a function that takes the index
-- and its corresponding element as input, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap :: forall m s a. MonadPrim s m => (Word -> a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array with a function that takes
-- the index and its corresponding element as input, modifying the
-- elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap' (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap' :: forall m s a. MonadPrim s m => (Word -> a -> a) -> Vec s a -> m ()
-- | Purpose
--
-- A contiguous growable array type with heap-allocated contents, written
-- Vec s a.
--
-- Vec has O(1) indexing, amortised O(1) push
-- (to the end), and O(1) pop (from the end).
--
-- A note about representation
--
-- The type exposed by this module is backed by a PrimArray; and
-- thus is most suitable for storing elements which can be completely
-- unboxed, i.e.; non-thunk non-pointers, such as Int,
-- Word, or Char. See the Prim typeclass for more
-- details. See the module-level documentation for GrowableVector
-- to see what other types are provided, and which may be more optimal
-- for your use-case.
--
-- A note about type variable ordering
--
-- The type variables in this module will be ordered according to the
-- following precedence list (with higher precedence meaning left-most in
-- the forall-quantified type variables):
--
--
-- - The PrimMonad type variable, m
-- - The PrimState token, s
-- - The element type, a
-- - Everything else is unspecified (look at the forall)
--
--
-- This structuring is intended to document and ensure a uniform
-- experience for users of -XTypeApplications.
--
-- A note about ordering of arguments
--
-- The arguments of functions in this module will generally be ordered as
-- follows:
--
--
-- - The vector
-- - The index (e.g. when reading/writing)
-- - The element
--
--
-- As an example, write, which has all three of these, takes the
-- vector, then the index, then the element.
--
-- As another example, push, which does not take an index, takes
-- the vector, then the element.
--
-- Any function which accepts more than one of the types in the list, or
-- accepts a type which is not in the list, has no guarantee about its
-- argument order.
module GrowableVector.Unboxed
-- | Indexing
--
-- The Vec type allows access to values by (0-based) index. An
-- example will be more explicit:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> two <- unsafeRead vec 1
--
-- >>> unsafeWrite vec 1 7
--
-- >>> seven <- unsafeRead vec 1
--
-- >>> two + seven
-- 9
--
--
-- However, be careful: if you try to access an index which isn't in the
-- Vec, your program will exhibit undefined behaviour ("UB"),
-- either returning garbage or segfaulting. You cannot do this:
--
--
-- v <- fromFoldable [0, 2, 4, 6]
-- unsafeRead v 6 -- this is UB
--
--
--
-- If you want safe access, use read:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> read vec 1
-- Just 2
--
-- >>> read vec 6
-- Nothing
--
--
-- Capacity and reallocation
--
-- The capacity of a vector is the amount of space allocated for any
-- future elements that will be added onto the vector. This is not to be
-- confused with the length of a vector, which specifies the
-- number of actual elements within the vector. If a vector's length
-- exceeds its capacity, its capacity will automatically be increased,
-- but its elements will have to be reallocated.
--
-- For example, a vector with capacity 10 and length 0 would be an empty
-- vector with space for 10 more elements. Pushing 10 or fewer elements
-- onto the vector will not change its capacity or cause reallocation to
-- occur. However, if the vector's length is increased to 11, it will
-- have to reallocate, which can be slow. For this reason, it is
-- recommended to use withCapacity whenever possible to specify
-- how big the vector is expected to get.
--
-- Guarantees
--
-- Vec is a (pointer, capacity, length) triplet. The pointer will
-- never be null.
--
-- Because of the semantics of the GHC runtime, creating a new vector
-- will always allocate. In particular, if you construct a
-- MutablePrimArray-backed Vec with capacity 0 via
-- new 0, fromFoldable [], or
-- shrinkToFit on an empty Vec, the 16-byte header
-- to GHC 'ByteArray#' will be allocated, but nothing else (for the
-- curious: this is needed for 'sameMutableByteArray#' to work).
-- Similarly, if you store zero-sized types inside such a Vec, it
-- will not allocate space for them. Note that in this case the
-- Vec may not report a capacity of 0. Vec will
-- allocate if and only if 'sizeOf (undefined :: a) *
-- capacity > 0.
--
-- If a Vec has allocated memory, then the memory it points
-- to is on the heap (as defined by GHC's allocator), and its pointer
-- points to length initialised, contiguous elements in order
-- (i.e. what you would see if you turned it into a list), followed by
-- capacity - length logically
-- uninitialised, contiguous elements.
--
-- Vec will never automatically shrink itself, even if completely
-- empty. This ensures no unnecessary allocations or deallocations occur.
-- Emptying a Vec and then filling it back up to the same
-- length should incur no calls to the allocator. If you wish to
-- free up unused memory, use shrinkToFit.
--
-- push will never (re)allocate if the reported capacity is
-- sufficient. push will (re)allocate if length
-- == capacity. That is, the reported capacity is
-- completely accurate, and can be relied on. Bulk insertion methods
-- may reallocate, even when not necessary.
--
-- Vec does not guarantee any particular growth strategy when
-- reallocating when full, nor when reserve is called. The
-- strategy is basic and may prove desirable to use a non-constant growth
-- factor. Whatever strategy is used will of course guarantee O(1)
-- amortised push.
--
-- fromFoldable and withCapacity will produce a Vec
-- with exactly the requested capacity.
--
-- Vec will not specifically overwrite any data that is removed
-- from it, but also won't specifically preserve it. Its uninitialised
-- memory is scratch space that it may use however it wants. It will
-- generally just do whatever is most efficient or otherwise easy to
-- implement. Do not rely on removed data to be erased for security
-- purposes. Even if a Vec drops out of scope, its buffer may
-- simply be reused by another Vec. Even if you zero a Vecs
-- memory first, this may not actually happen when you think it does
-- because of Garbage Collection.
data Vec s a
-- | <math>. Constructs a new, empty Vec s a.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 0) (capacity vec)
--
new :: forall m s a. (MonadPrim s m, Prim a) => m (Vec s a)
-- | <math>. Constructs a new, empty Vec arr s a.
--
-- The vector will be able to hold exactly capacity elements
-- without reallocating. It is important to note that althrough the
-- returned vector has the capacity specified, with vector will
-- have a zero length.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
-- -- The vector contains no items, even though it has capacity for more
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- These are all done without reallocating...
--
-- >>> forM_ [1..10] $ \i -> push vec i
--
-- >>> assertM (== 10) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- ..but this may make the vector reallocate
--
-- >>> push vec 11
--
-- >>> assertM (== 11) (length vec)
--
-- >>> assertM (>= 11) (capacity vec)
--
withCapacity :: forall m s a. (MonadPrim s m, Prim a) => Word -> m (Vec s a)
-- | <math>. Returns the number of elements in the vector.
length :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m Word
-- | <math>. Returns the maximum number of elements the vector can
-- hold without reallocating.
--
--
-- >>> vec <- withCapacity @_ @_ @Word 10
--
-- >>> push vec 42
--
-- >>> assertM (== 10) (capacity vec)
--
capacity :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m Word
-- | <math>. Reserves capacity for at least additional more
-- elements to be inserted in the given Vec s a. The
-- collection may reserve more space to avoid frequent reallocations.
-- After calling reserve, capacity will be greater than or equal
-- to length + additional. Does nothing if capacity is already
-- sufficient.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserve vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserve :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> Word -> m ()
-- | <math>. Reserves the minimum capacity for exactly
-- additional more elements to be inserted in the given
-- Vec s a. After calling reserveExact, capacity
-- will be greater than or equal to length + additional. Does
-- nothing if the capacity is already sufficient.
--
-- Capacity cannot be relied upon to be precisely minimal. Prefer
-- reserve if future insertions are expected.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserveExact vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserveExact :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> Word -> m ()
-- | <math>. Shrinks the capacity of the vector as much as possible.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkToFit vec
--
-- >>> assertM (== 3) (capacity vec)
--
shrinkToFit :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m ()
-- | <math>. Shrinks the capacity of the vector with a lower bound.
--
-- The capacity will remain at least as large as both the length and the
-- supplied value.
--
-- If the current capacity is less than the lower limit, this is a no-op.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkTo vec 4
--
-- >>> assertM (>= 4) (capacity vec)
--
-- >>> shrinkTo vec 0
--
-- >>> assertM (>= 3) (capacity vec)
--
shrinkTo :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> Word -> m ()
-- | <math>. Return the element at the given position.
--
-- If the element index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length).
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using read instead.
unsafeRead :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> Word -> m a
-- | <math>. Return the element at the given position, or
-- Nothing if the index is out of bounds.
--
-- The bounds are defined as [0, length).
read :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> Word -> m (Maybe a)
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using write instead.
unsafeWrite :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> Word -> a -> m ()
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is in bounds, this returns Just (). If
-- the index is out of bounds, this returns Nothing.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
write :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> Word -> a -> m (Maybe ())
-- | Amortised <math>. Appends an element to the vector.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2]
--
-- >>> push vec 3
--
-- >>> assertM (== [1, 2, 3]) (toList vec)
--
push :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> a -> m ()
-- | <math>. Removes the last element from a vector and returns it,
-- or Nothing if it is empty.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2, 3]
--
-- >>> assertM (== Just 3) (pop vec)
--
-- >>> assertM (== [1, 2]) (toList vec)
--
pop :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m (Maybe a)
-- | <math>. Extend the vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Char ['a', 'b', 'c']
--
-- >>> extend vec ['d', 'e', 'f']
--
-- >>> assertM (== "abcdef") (toList vec)
--
extend :: forall m s a t. (MonadPrim s m, Prim a, Foldable t) => Vec s a -> t a -> m ()
-- | <math>. Create a vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> assertM (== [1..10]) (toList vec)
--
fromFoldable :: forall m s a t. (MonadPrim s m, Prim a, Foldable t) => t a -> m (Vec s a)
-- | <math>. Create a list with the elements of the vector.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> extend vec [1..5]
--
-- >>> toList vec
-- [1,2,3,4,5]
--
toList :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m [a]
-- | <math>. Create a lifted Vector copy of a vector.
toLiftedVector :: forall m s a. (MonadPrim s m, Prim a) => Vec s a -> m (Vector a)
-- | <math>. Create a lifted Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toLiftedVectorWith :: forall m s a b. (MonadPrim s m, Prim a) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Primitive Vector copy of a vector.
toPrimitiveVector :: forall m s a. (MonadPrim s m, Prim a, Prim a) => Vec s a -> m (Vector a)
-- | <math>. Create a Primitive Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toPrimitiveVectorWith :: forall m s a b. (MonadPrim s m, Prim a, Prim a, Prim b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Storable Vector copy of a vector.
toStorableVector :: forall m s a. (MonadPrim s m, Prim a, Storable a) => Vec s a -> m (Vector a)
-- | <math>. Create a Storable Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toStorableVectorWith :: forall m s a b. (MonadPrim s m, Prim a, Storable b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Map over an array, modifying the elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map (+ 1) vec
--
-- >>> assertM (== [2, 3 .. 11]) (toList vec)
--
map :: forall m s a. (MonadPrim s m, Prim a) => (a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map' (* 2) vec
--
-- >>> assertM (== [2, 4 .. 20]) (toList vec)
--
map' :: forall m s a. (MonadPrim s m, Prim a) => (a -> a) -> Vec s a -> m ()
-- | <math>. Map over an array with a function that takes the index
-- and its corresponding element as input, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap :: forall m s a. (MonadPrim s m, Prim a) => (Word -> a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array with a function that takes
-- the index and its corresponding element as input, modifying the
-- elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap' (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap' :: forall m s a. (MonadPrim s m, Prim a) => (Word -> a -> a) -> Vec s a -> m ()
-- | Purpose
--
-- A contiguous growable array type with heap-allocated contents, written
-- Vec s a.
--
-- Vec has O(1) indexing, amortised O(1) push
-- (to the end), and O(1) pop (from the end).
--
-- A note about representation
--
-- The type exposed by this module is backed by an UnliftedArray;
-- and thus is most suitable for elements which can be unlifted, i.e.;
-- non-thunk pointers, such as ByteArray, MVar, or
-- IORef. See the PrimUnlifted typeclass for more details.
-- See the module-level documentation for GrowableVector to see
-- what other types are provided, and which may be more optimal for your
-- use-case.
--
-- A note about type variable ordering
--
-- The type variables in this module will be ordered according to the
-- following precedence list (with higher precedence meaning left-most in
-- the forall-quantified type variables):
--
--
-- - The PrimMonad type variable, m
-- - The PrimState token, s
-- - The element type, a
-- - Everything else is unspecified (look at the forall)
--
--
-- This structuring is intended to document and ensure a uniform
-- experience for users of -XTypeApplications.
--
-- A note about ordering of arguments
--
-- The arguments of functions in this module will generally be ordered as
-- follows:
--
--
-- - The vector
-- - The index (e.g. when reading/writing)
-- - The element
--
--
-- As an example, write, which has all three of these, takes the
-- vector, then the index, then the element.
--
-- As another example, push, which does not take an index, takes
-- the vector, then the element.
--
-- Any function which accepts more than one of the types in the list, or
-- accepts a type which is not in the list, has no guarantee about its
-- argument order.
module GrowableVector.Unlifted
-- | Indexing
--
-- The Vec type allows access to values by (0-based) index. An
-- example will be more explicit:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> two <- unsafeRead vec 1
--
-- >>> unsafeWrite vec 1 7
--
-- >>> seven <- unsafeRead vec 1
--
-- >>> two + seven
-- 9
--
--
-- However, be careful: if you try to access an index which isn't in the
-- Vec, your program will exhibit undefined behaviour ("UB"),
-- either returning garbage or segfaulting. You cannot do this:
--
--
-- v <- fromFoldable [0, 2, 4, 6]
-- unsafeRead v 6 -- this is UB
--
--
--
-- If you want safe access, use read:
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [0, 2, 4, 6]
--
-- >>> read vec 1
-- Just 2
--
-- >>> read vec 6
-- Nothing
--
--
-- Capacity and reallocation
--
-- The capacity of a vector is the amount of space allocated for any
-- future elements that will be added onto the vector. This is not to be
-- confused with the length of a vector, which specifies the
-- number of actual elements within the vector. If a vector's length
-- exceeds its capacity, its capacity will automatically be increased,
-- but its elements will have to be reallocated.
--
-- For example, a vector with capacity 10 and length 0 would be an empty
-- vector with space for 10 more elements. Pushing 10 or fewer elements
-- onto the vector will not change its capacity or cause reallocation to
-- occur. However, if the vector's length is increased to 11, it will
-- have to reallocate, which can be slow. For this reason, it is
-- recommended to use withCapacity whenever possible to specify
-- how big the vector is expected to get.
--
-- Guarantees
--
-- Vec is a (pointer, capacity, length) triplet. The pointer will
-- never be null.
--
-- Because of the semantics of the GHC runtime, creating a new vector
-- will always allocate. In particular, if you construct a
-- MutablePrimArray-backed Vec with capacity 0 via
-- new 0, fromFoldable [], or
-- shrinkToFit on an empty Vec, the 16-byte header
-- to GHC 'ByteArray#' will be allocated, but nothing else (for the
-- curious: this is needed for 'sameMutableByteArray#' to work).
-- Similarly, if you store zero-sized types inside such a Vec, it
-- will not allocate space for them. Note that in this case the
-- Vec may not report a capacity of 0. Vec will
-- allocate if and only if 'sizeOf (undefined :: a) *
-- capacity > 0.
--
-- If a Vec has allocated memory, then the memory it points
-- to is on the heap (as defined by GHC's allocator), and its pointer
-- points to length initialised, contiguous elements in order
-- (i.e. what you would see if you turned it into a list), followed by
-- capacity - length logically
-- uninitialised, contiguous elements.
--
-- Vec will never automatically shrink itself, even if completely
-- empty. This ensures no unnecessary allocations or deallocations occur.
-- Emptying a Vec and then filling it back up to the same
-- length should incur no calls to the allocator. If you wish to
-- free up unused memory, use shrinkToFit.
--
-- push will never (re)allocate if the reported capacity is
-- sufficient. push will (re)allocate if length
-- == capacity. That is, the reported capacity is
-- completely accurate, and can be relied on. Bulk insertion methods
-- may reallocate, even when not necessary.
--
-- Vec does not guarantee any particular growth strategy when
-- reallocating when full, nor when reserve is called. The
-- strategy is basic and may prove desirable to use a non-constant growth
-- factor. Whatever strategy is used will of course guarantee O(1)
-- amortised push.
--
-- fromFoldable and withCapacity will produce a Vec
-- with exactly the requested capacity.
--
-- Vec will not specifically overwrite any data that is removed
-- from it, but also won't specifically preserve it. Its uninitialised
-- memory is scratch space that it may use however it wants. It will
-- generally just do whatever is most efficient or otherwise easy to
-- implement. Do not rely on removed data to be erased for security
-- purposes. Even if a Vec drops out of scope, its buffer may
-- simply be reused by another Vec. Even if you zero a Vecs
-- memory first, this may not actually happen when you think it does
-- because of Garbage Collection.
data Vec s a
-- | <math>. Constructs a new, empty Vec s a.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 0) (capacity vec)
--
new :: forall m s a. (MonadPrim s m, PrimUnlifted a) => m (Vec s a)
-- | <math>. Constructs a new, empty Vec arr s a.
--
-- The vector will be able to hold exactly capacity elements
-- without reallocating. It is important to note that althrough the
-- returned vector has the capacity specified, with vector will
-- have a zero length.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
-- -- The vector contains no items, even though it has capacity for more
--
-- >>> assertM (== 0) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- These are all done without reallocating...
--
-- >>> forM_ [1..10] $ \i -> push vec i
--
-- >>> assertM (== 10) (length vec)
--
-- >>> assertM (== 10) (capacity vec)
-- -- ..but this may make the vector reallocate
--
-- >>> push vec 11
--
-- >>> assertM (== 11) (length vec)
--
-- >>> assertM (>= 11) (capacity vec)
--
withCapacity :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Word -> m (Vec s a)
-- | <math>. Returns the number of elements in the vector.
length :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> m Word
-- | <math>. Returns the maximum number of elements the vector can
-- hold without reallocating.
--
--
-- >>> vec <- withCapacity @_ @_ @Word 10
--
-- >>> push vec 42
--
-- >>> assertM (== 10) (capacity vec)
--
capacity :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> m Word
-- | <math>. Reserves capacity for at least additional more
-- elements to be inserted in the given Vec s a. The
-- collection may reserve more space to avoid frequent reallocations.
-- After calling reserve, capacity will be greater than or equal
-- to length + additional. Does nothing if capacity is already
-- sufficient.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserve vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserve :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> Word -> m ()
-- | <math>. Reserves the minimum capacity for exactly
-- additional more elements to be inserted in the given
-- Vec s a. After calling reserveExact, capacity
-- will be greater than or equal to length + additional. Does
-- nothing if the capacity is already sufficient.
--
-- Capacity cannot be relied upon to be precisely minimal. Prefer
-- reserve if future insertions are expected.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int @_ [1]
--
-- >>> reserveExact vec 10
--
-- >>> assertM (>= 11) (capacity vec)
--
reserveExact :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> Word -> m ()
-- | <math>. Shrinks the capacity of the vector as much as possible.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkToFit vec
--
-- >>> assertM (== 3) (capacity vec)
--
shrinkToFit :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> m ()
-- | <math>. Shrinks the capacity of the vector with a lower bound.
--
-- The capacity will remain at least as large as both the length and the
-- supplied value.
--
-- If the current capacity is less than the lower limit, this is a no-op.
--
--
-- >>> vec <- withCapacity @_ @_ @Int 10
--
-- >>> extend vec [1, 2, 3]
--
-- >>> assertM (== 10) (capacity vec)
--
-- >>> shrinkTo vec 4
--
-- >>> assertM (>= 4) (capacity vec)
--
-- >>> shrinkTo vec 0
--
-- >>> assertM (>= 3) (capacity vec)
--
shrinkTo :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> Word -> m ()
-- | <math>. Return the element at the given position.
--
-- If the element index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length).
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using read instead.
unsafeRead :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> Word -> m a
-- | <math>. Return the element at the given position, or
-- Nothing if the index is out of bounds.
--
-- The bounds are defined as [0, length).
read :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> Word -> m (Maybe a)
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is out of bounds, this function will segfault.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
--
-- This function is intended to be used in situations where you have
-- manually proved that your indices are within bounds, and you don't
-- want to repeatedly pay for bounds checking.
--
-- Consider using write instead.
unsafeWrite :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> Word -> a -> m ()
-- | <math>. Write a value to the vector at the given position.
--
-- If the index is in bounds, this returns Just (). If
-- the index is out of bounds, this returns Nothing.
--
-- The bounds are defined as [0, length). If you want to add an element
-- past length - 1, use push or extend, which can
-- intelligently handle resizes.
write :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> Word -> a -> m (Maybe ())
-- | Amortised <math>. Appends an element to the vector.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2]
--
-- >>> push vec 3
--
-- >>> assertM (== [1, 2, 3]) (toList vec)
--
push :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> a -> m ()
-- | <math>. Removes the last element from a vector and returns it,
-- or Nothing if it is empty.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1, 2, 3]
--
-- >>> assertM (== Just 3) (pop vec)
--
-- >>> assertM (== [1, 2]) (toList vec)
--
pop :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> m (Maybe a)
-- | <math>. Extend the vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Char ['a', 'b', 'c']
--
-- >>> extend vec ['d', 'e', 'f']
--
-- >>> assertM (== "abcdef") (toList vec)
--
extend :: forall m s a t. (MonadPrim s m, PrimUnlifted a, Foldable t) => Vec s a -> t a -> m ()
-- | <math>. Create a vector with the elements of some
-- Foldable structure.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> assertM (== [1..10]) (toList vec)
--
fromFoldable :: forall m s a t. (MonadPrim s m, PrimUnlifted a, Foldable t) => t a -> m (Vec s a)
-- | <math>. Create a list with the elements of the vector.
--
--
-- >>> vec <- new @_ @_ @Int
--
-- >>> extend vec [1..5]
--
-- >>> toList vec
-- [1,2,3,4,5]
--
toList :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> m [a]
-- | <math>. Create a lifted Vector copy of a vector.
toLiftedVector :: forall m s a. (MonadPrim s m, PrimUnlifted a) => Vec s a -> m (Vector a)
-- | <math>. Create a lifted Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toLiftedVectorWith :: forall m s a b. (MonadPrim s m, PrimUnlifted a) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Primitive Vector copy of a vector.
toPrimitiveVector :: forall m s a. (MonadPrim s m, PrimUnlifted a, Prim a) => Vec s a -> m (Vector a)
-- | <math>. Create a Primitive Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toPrimitiveVectorWith :: forall m s a b. (MonadPrim s m, PrimUnlifted a, Prim b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Create a Storable Vector copy of a vector.
toStorableVector :: forall m s a. (MonadPrim s m, PrimUnlifted a, Storable a) => Vec s a -> m (Vector a)
-- | <math>. Create a Storable Vector copy of a vector by
-- applying a function to each element and its corresponding index.
toStorableVectorWith :: forall m s a b. (MonadPrim s m, PrimUnlifted a, Storable b) => (Word -> a -> m b) -> Vec s a -> m (Vector b)
-- | <math>. Map over an array, modifying the elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map (+ 1) vec
--
-- >>> assertM (== [2, 3 .. 11]) (toList vec)
--
map :: forall m s a. (MonadPrim s m, PrimUnlifted a) => (a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> map' (* 2) vec
--
-- >>> assertM (== [2, 4 .. 20]) (toList vec)
--
map' :: forall m s a. (MonadPrim s m, PrimUnlifted a) => (a -> a) -> Vec s a -> m ()
-- | <math>. Map over an array with a function that takes the index
-- and its corresponding element as input, modifying the elements in
-- place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap :: forall m s a. (MonadPrim s m, PrimUnlifted a) => (Word -> a -> a) -> Vec s a -> m ()
-- | <math>. Map strictly over an array with a function that takes
-- the index and its corresponding element as input, modifying the
-- elements in place.
--
--
-- >>> vec <- fromFoldable @_ @_ @Int [1..10]
--
-- >>> imap' (\ix el -> ix + 1) vec
--
-- >>> assertM (== zipWith (+) [0..] [1..10]) (toList vec)
--
imap' :: forall m s a. (MonadPrim s m, PrimUnlifted a) => (Word -> a -> a) -> Vec s a -> m ()