vector
Efficient Arrays
https://github.com/haskell/vector
LTS Haskell 22.41: | 0.13.1.0@rev:2 |
Stackage Nightly 2024-11-12: | 0.13.2.0 |
Latest on Hackage: | 0.13.2.0 |
vector-0.13.2.0@sha256:98f5cb3080a3487527476e3c272dcadaba1376539f2aa0646f2f19b3af6b2f67,8481
Module documentation for 0.13.2.0
- Data
- Data.Vector
- Data.Vector.Fusion
- Data.Vector.Generic
- Data.Vector.Generic.Base
- Data.Vector.Generic.Mutable
- Data.Vector.Generic.New
- Data.Vector.Internal
- Data.Vector.Internal.Check
- Data.Vector.Mutable
- Data.Vector.Primitive
- Data.Vector.Storable
- Data.Vector.Storable.Internal
- Data.Vector.Storable.Mutable
- Data.Vector.Strict
- Data.Vector.Unboxed
- Data.Vector.Unboxed.Base
- Data.Vector.Unboxed.Mutable
- Data.Vector
The vector
package
Vector is a collection of efficient Int
-indexed array implementations:
boxed, unboxed, storable, and primitive vectors
(all can be mutable or immutable). The package features a generic API,
polymorphic in vector type, and implements stream fusion,
a powerful optimisation framework that can help eliminate intermediate data structures.
Table of Contents
Tutorial
A beginner-friendly tutorial for vectors can be found on MMHaskell.
If you have already started your adventure with vectors, the tutorial on Haskell Wiki covers more ground.
Vector vs Array
Arrays are data structures that can store a multitude of elements and allow immediate access to every one of them. However, they are often seen as legacy constructs that are rarely used in modern Haskell. Even though Haskell has a built-in Data.Array module, arrays might be a bit overwhelming to use due to their complex API. Conversely, vectors incorporate the array’s O(1) access to elements with a much friendlier API of lists. Since they allow for framework optimisation via loop fusion, vectors emphasise efficiency and keep a rich interface. Unless you’re confident with arrays, it’s well-advised to use vectors when looking for a similar functionality.
Vectors Available in the Package
Lazy boxed vectors (Data.Vector
) store each of their elements as a
pointer to a heap-allocated value. Because of indirection, lazy boxed vectors
are slower in comparison to unboxed vectors.
Strict boxed vectors (Data.Vector.Strict
) contain elements that are
strictly evaluated.
Unboxed vectors (Data.Vector.Unboxed
) determine an array’s representation
from its elements’ type. For example, vector of primitive types (e.g. Int
) will be
backed by primitive array while vector of product types by structure of arrays.
They are quite efficient due to the unboxed representation they use.
Storable vectors (Data.Vector.Storable
) are backed by pinned memory, i.e.,
they cannot be moved by the garbage collector. Their primary use case is C FFI.
Primitive vectors (Data.Vector.Primitive
) are backed by simple byte array and
can store only data types that are represented in memory as a sequence of bytes without
a pointer, i.e., they belong to the Prim
type class, e.g., Int
, Double
, etc.
It’s advised to use unboxed vectors if you’re looking for the performance of primitive vectors,
but more versality.
Stream Fusion
An optimisation framework used by vectors, stream fusion is a technique that merges
several functions into one and prevents creation of intermediate data structures. For example,
the expression sum . filter g . map f
won’t allocate temporary vectors if
compiled with optimisations.
Changes
Changes in version 0.13.2.0
- Strict boxed vector
Data.Vector.Strict
andData.Vector.Strict.Mutable
is added (#488). it ensures that all values in the vector are evaluated to WHNF. DoNotUnboxStrict
,DoNotUnboxLazy
, andDoNotUnboxNormalForm
wrapper are added for defining unbox instances for types that contain not unboxable fields. #503, #508spanR
andbreakR
were added #476. They allow parsing vector from the right.- We had some improvements on
*.Mutable.{next,prev}Permutation{,By}
#498:- Add
*.Mutable.prevPermutation{,By}
and*.Mutable.nextPermutationBy
- Improve time performance. We may now expect good specialization supported by inlining.
The implementation has also been algorithmically updated: in the previous implementation
the full enumeration of all the permutations of
[1..n]
took Omega(n*n!), but it now takes O(n!). - Add tests for
{next,prev}Permutation
- Add benchmarks for
{next,prev}Permutation
- Add
- Cabal >= 3.0 is now required for building package (#481).
vector:benchmarks-O2
public sublibrary containing benchmarks is added (#481).- Type family
Mutable
provides instances for arrays fromprimitive
. - Various documentation improvements.
Changes in version 0.13.1.0
- Specialized variants of
findIndexR
are reexported for all vector types. #469 UnboxViaPrim
could be used for derivingUnbox
instances (V_UnboxViaPrim
constructor is exported) #450- Fields of
Data.Vector.Fusion.Bundle.Size
are now strict #456 - Compatibility with future GHC 9.10 release #462
- Test suite no longer fails when built with QuickCheck-2.14 #461
- Doctests now work with current versions of GHC #465
- Various documentation improvements
Changes in version 0.13.0.0
mkType
fromData.Vector.Generic
is deprecated in favor ofData.Data.mkNoRepType
- The role signatures on several
Vector
types were too permissive, so they have been tightened up:-
The role signature for
Data.Vector.Mutable.MVector
is nowtype role MVector nominal representational
(previously, both arguments werephantom
). #224 -
The role signature for
Data.Vector.Primitive.Vector
is nowtype role Vector nominal
(previously, it wasphantom
). The role signature forData.Vector.Primitive.Mutable.MVector
is nowtype role MVector nominal nominal
(previously, both arguments werephantom
). #316 -
The role signature for
Data.Vector.Storable.Vector
is nowtype role Vector nominal
(previous, it wasphantom
), and the signature forData.Vector.Storable.Mutable.MVector
is nowtype role MVector nominal nominal
(previous, both arguments werephantom
). #235We pick
nominal
for the role of the last argument instead ofrepresentational
since the internal structure of aStorable
vector is determined by theStorable
instance of the element type, and it is not guaranteed that theStorable
instances between two representationally equal types will preserve this internal structure. One consequence of this choice is that it is no longer possible tocoerce
betweenStorable.Vector a
andStorable.Vector b
ifa
andb
are nominally distinct but representationally equal types. We now provideunsafeCoerce{M}Vector
andunsafeCast
functions to allow this (the onus is on the user to ensure that noStorable
invariants are broken when using these functions).
-
- Methods of type classes
Data.Vector.Generic.Mutable.MVector
andData.Vector.Generic.Vector
use concrete monads (ST
, etc) istead of being polymorphic (PrimMonad
, etc). #335. This makes it possible to deriveUnbox
with:GeneralizedNewtypeDeriving
- via
UnboxViaPrim
andPrim
instance - via
As
andIsoUnbox
instance: #378
- Add
MonadFix
instance for boxed vectors: #312 - Re-export
PrimMonad
andRealWorld
from mutable vectors: #320 - Add
maximumOn
andminimumOn
: #356 - The functions
scanl1
,scanl1'
,scanr1
, andscanr1'
for immutable vectors are now defined when given empty vectors as arguments, in which case they return empty vectors. This new behavior is consistent with the one of the corresponding functions inData.List
. Prior to this change, applying an empty vector to any of those functions resulted in an error. This change was introduced in: #382 - Change allocation strategy for
unfoldrN
: #387 - Remove
CPP
driven error reporting in favor ofHasCallStack
: #397 - Remove redundant
Storable
constraints on to/fromForeignPtr
conversions: #394 - Add
unsafeCast
toPrimitive
vectors: #401 - Make
(!?)
operator strict: #402 - Add
readMaybe
: #425 - Add
groupBy
andgroup
forData.Vector.Generic
and the specialized version inData.Vector
,Data.Vector.Unboxed
,Data.Vector.Storable
andData.Vector.Primitive
. #427 - Add
toArraySlice
andunsafeFromArraySlice
functions for conversion to and from the underlying boxedArray
: #434
Changes in version 0.12.3.1
- Bugfix for ghcjs and
Double
memset forStorable
vector: #410 - Avoid haddock bug: #383
- Improve haddock and doctests
- Disable problematic tests with -boundschecks #407
Changes in version 0.12.3.0
-
Fix performance regression due to introduction of
keepAlive#
primop in ghc-9.0: #372 -
Add monadic functions for mutable vectors: #338
- Added folds for monadic functions:
mapM_
,imapM_
,forM_
,iforM_
,foldl
,foldl'
,foldM
,foldM'
,ifoldl
,ifoldl'
,ifoldM
,ifoldM'
- Added
modifyM
andunsafeModifyM
for mutable vectors - Added
generate
andgenerateM
for mutable vectors
- Added folds for monadic functions:
Changes in version 0.12.2.0
- Add
MINIMAL
pragma toVector
&MVector
type classes: #11 - Export
unstreamM
fromfrom Data.Vector.Generic
: #70 - Added
unfoldrExactN
andunfoldrExactNM
: #140 - Added
iforM
andiforM_
: #262 - Added
MonadFix
instance for boxed vectors: #178 - Added
uncons
andunsnoc
: #212 - Added
foldMap
andfoldMap'
: #263 - Added
isSameVector
for storable vectors - Added
toArray
,fromArray
,toMutableArray
andfromMutableArray
- Added
iscanl
,iscanl'
,iscanr
,iscanr'
toPrimitive
,Storable
andUnboxed
- Added
izipWithM
,izipWithM_
,imapM
andimapM_
toPrimitive
andStorable
- Added
ifoldM
,ifoldM'
,ifoldM_
andifoldM'_
toPrimitive
andStorable
- Added
eqBy
andcmpBy
- Added
findIndexR
toGeneric
: #172 - Added
catMaybes
: #329 - Added
mapMaybeM
andimapMaybeM
: #183
Changes in version 0.12.1.2
- Fix for lost function
Data.Vector.Generic.mkType
: #287
Changes in version 0.12.1.1 (deprecated)
- add semigrioups dep to test suite so CI actually runs again on GHC < 8
Changes in version 0.12.1.0 (deprecated)
- Fix integer overflows in specializations of Bundle/Stream enumFromTo on Integral types
- Fix possibility of OutOfMemory with
take
and very large arguments. - Fix
slice
function causing segfault and not checking the bounds properly. - updated specialization rule for EnumFromTo on Float and Double to make sure it always matches the version in GHC Base (which changed as of 8.6) Thanks to Aleksey Khudyakov @Shimuuar for this fix.
- fast rejection short circuiting in eqBy operations
- the O2 test suite now has reasonable memory usage on every GHC version, special thanks to Alexey Kuleshevich (@lehins).
- The
Mutable
type family is now injective on GHC 8.0 or later. - Using empty
Storable
vectors no longer results in division-by-zero errors. - The
Data
instances forVector
types now have well defined implementations fortoConstr
,gunfold
, anddataTypeOf
. - New function:
partitionWith
. - Add
Unbox
instances forIdentity
,Const
,Down
,Dual
,Sum
,Product
,Min
,Max
,First
,Last
,WrappedMonoid
,Arg
,Any
,All
,Alt
, andCompose
. - Add
NFData1
instances for applicableVector
types.
Changes in version 0.12.0.3
- Monad Fail support
Changes in version 0.12.0.2
- Fixes issue #220, compact heap operations crashing on boxed vectors constructed using traverse.
- backport injective type family support
- Cleanup the memset code internal to storable vector modules to be compatible with future Primitive releases
Changes in version 0.12.0.1
- Make sure
length
can be inlined - Include modules that test-suites depend on in other-modules
Changes in version 0.12.0.0
- Documentation fixes/additions
- New functions: createT, iscanl/r, iterateNM, unfoldrM, uniq
- New instances for various vector types: Semigroup, MonadZip
- Made
Storable
vectors respect memory alignment - Changed some macros to ConstraintKinds
- Dropped compatibility with old GHCs to support this
- Add
Eq1
,Ord1
,Show1
, andRead1
Vector
instances, and related helper functions. - Relax context for
Unbox (Complex a)
.
Changes in version 0.11.0.0
- Define
Applicative
instances forData.Vector.Fusion.Util.{Box,Id}
- Define non-bottom
fail
forinstance Monad Vector
- New generalized stream fusion framework
- Various safety fixes
- Various overflows due to vector size have been eliminated
- Memory is initialized on creation of unboxed vectors
- Changes to SPEC usage to allow building under more conditions
Changes in version 0.10.12.3
- Allow building with
primtive-0.6
Changes in version 0.10.12.2
- Add support for
deepseq-1.4.0.0
Changes in version 0.10.12.1
- Fixed compilation on non-head GHCs
Changes in version 0.10.12.0
-
Export MVector constructor from Data.Vector.Primitive to match Vector’s (which was already exported).
-
Fix building on GHC 7.9 by adding Applicative instances for Id and Box
Changes in version 0.10.11.0
- Support OverloadedLists for boxed Vector in GHC >= 7.8
Changes in version 0.10.10.0
- Minor version bump to rectify PVP violation occured in 0.10.9.3 release
Changes in version 0.10.9.3 (deprecated)
- Add support for OverloadedLists in GHC >= 7.8
Changes in version 0.10.9.2
- Fix compilation with GHC 7.9
Changes in version 0.10.9.1
- Implement poly-kinded Typeable
Changes in version 0.10.0.1
- Require
primitive
to include workaround for a GHC array copying bug
Changes in version 0.10
NFData
instances- More efficient block fills
- Safe Haskell support removed