-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Fast unboxed arrays with a flexible interface
--
-- Fast unboxed arrays with a flexible interface. The library is built of
-- fusible combinators, as described in the paper /Stream Fusion: From
-- Lists to Streams to Nothing at All/.
--
-- For best results, compile with your user programs with -O2 -fvia-C
-- -optc-O3.
--
-- This library is deprecated: please consider using the vector package,
-- http://hackage.haskell.org/package/vector.
@package uvector
@version 0.1.1.1
-- | Description
-- --------------------------------------------------------------- This
-- module defines unlifted arrays generically as a GADT.
--
-- Slicing is implemented by each BUArr having the slicing
-- information. A possible alternative design would be to maintain this
-- information in UArr, but not in the representations, but at the
-- root. This may seem attractive at first, but seems to be more
-- disruptive without any real benefits _ this is essentially, because we
-- then need the slicing information at each level; ie, also at the leafs
-- where it is sufficient using the current implementation.
--
-- Todo
-- ----------------------------------------------------------------------
module Data.Array.Vector.UArr
-- | This type class determines the types that can be elements immutable
-- unboxed arrays. The representation type of these arrays is defined by
-- way of an associated type. All representation-dependent functions are
-- methods of this class.
class UA e where { data family UArr e; data family MUArr e :: * -> *; }
lengthU :: (UA e) => UArr e -> Int
indexU :: (UA e) => UArr e -> Int -> e
sliceU :: (UA e) => UArr e -> Int -> Int -> UArr e
lengthMU :: (UA e) => MUArr e s -> Int
newMU :: (UA e) => Int -> ST s (MUArr e s)
readMU :: (UA e) => MUArr e s -> Int -> ST s e
writeMU :: (UA e) => MUArr e s -> Int -> e -> ST s ()
copyMU :: (UA e) => MUArr e s -> Int -> UArr e -> ST s ()
unsafeFreezeMU :: (UA e) => MUArr e s -> Int -> ST s (UArr e)
memcpyMU :: (UA e) => MUArr e s -> MUArr e s -> Int -> ST s ()
memcpyOffMU :: (UA e) => MUArr e s -> MUArr e s -> Int -> Int -> Int -> ST s ()
memmoveOffMU :: (UA e) => MUArr e s -> MUArr e s -> Int -> Int -> Int -> ST s ()
class (UAE e) => UPrim e
mkUAPrim :: (UPrim e) => BUArr e -> UArr e
unUAPrim :: (UPrim e) => UArr e -> BUArr e
mkMUAPrim :: (UPrim e) => MBUArr s e -> MUArr e s
unMUAPrim :: (UPrim e) => MUArr e s -> MBUArr s e
-- | O(1). Yield an array of units.
unitsU :: Int -> UArr ()
-- | O(1). Elementwise pairing of array elements.
--
-- N.B: The output will be as long as the first array (and will
-- thus access past the end of the second array), unlike its List
-- counterpart. This will not occur at the time zipU is called, but only
-- after the resulting array is accessed.
zipU :: (UA a, UA b) => UArr a -> UArr b -> UArr (a :*: b)
-- | O(1). Elementwise unpairing of array elements.
unzipU :: (UA a, UA b) => UArr (a :*: b) -> (UArr a :*: UArr b)
-- | O(1). Yield the first components of an array of pairs.
fstU :: (UA a, UA b) => UArr (a :*: b) -> UArr a
-- | O(1). Yield the second components of an array of pairs.
sndU :: (UA a, UA b) => UArr (a :*: b) -> UArr b
-- | O(n). newU constructs an immutable array of the given
-- size by performing the provided initialization function on a mutable
-- representation of the output array.
newU :: (UA e) => Int -> (forall s. MUArr e s -> ST s ()) -> UArr e
newDynU :: (UA e) => Int -> (forall s. MUArr e s -> ST s Int) -> UArr e
newDynResU :: (UA e) => Int -> (forall s. MUArr e s -> ST s (Int :*: r)) -> UArr e :*: r
-- | O(1). unsafeFreezeAllMU converts an entire mutable array
-- into an immutable array, without copying. The mutable array must not
-- be mutated after this.
unsafeFreezeAllMU :: (UA e) => MUArr e s -> ST s (UArr e)
-- | Elementwise pairing of mutable arrays. This is an unsafe operation, as
-- no copying is performed, so changes to the pair array will affect the
-- original arrays, and vice versa.
unsafeZipMU :: (UA a, UA b) => MUArr a s -> MUArr b s -> MUArr (a :*: b) s
-- | Elementwise unpairing of mutable arrays. This is an unsafe operation,
-- as no copying is performed, so changes to the unpaired arrays will
-- affect the original, and vice versa.
unsafeUnzipMU :: (UA a, UA b) => MUArr (a :*: b) s -> MUArr a s :*: MUArr b s
instance (Integral a, UA a) => UA (Ratio a)
instance (RealFloat a, UA a) => UA (Complex a)
instance UA Int64
instance UPrim Int64
instance UA Int32
instance UPrim Int32
instance UA Int16
instance UPrim Int16
instance UA Int8
instance UPrim Int8
instance UA Word64
instance UPrim Word64
instance UA Word32
instance UPrim Word32
instance UA Word16
instance UPrim Word16
instance UA Word8
instance UPrim Word8
instance UA Double
instance UPrim Double
instance UA Float
instance UPrim Float
instance UA Word
instance UPrim Word
instance UA Int
instance UPrim Int
instance UA Char
instance UPrim Char
instance UA Bool
instance UPrim Bool
instance (UA a, UA b) => UA (a :*: b)
instance UA ()
-- | The top level interface to operations on strict, non-nested, fusible
-- arrays.
--
-- Note that the time complexities provided for functions in this package
-- depend on fusion. Thus the times given assume that fusion did not
-- occur and that the full operation is performed. In some cases fusion
-- can take multiple O(n) operations on UArrs and optimize them
-- out of the generated code completely.
module Data.Array.Vector
-- | This type class determines the types that can be elements immutable
-- unboxed arrays. The representation type of these arrays is defined by
-- way of an associated type. All representation-dependent functions are
-- methods of this class.
class UA e where { data family UArr e; data family MUArr e :: * -> *; }
sliceU :: (UA e) => UArr e -> Int -> Int -> UArr e
lengthMU :: (UA e) => MUArr e s -> Int
newMU :: (UA e) => Int -> ST s (MUArr e s)
readMU :: (UA e) => MUArr e s -> Int -> ST s e
writeMU :: (UA e) => MUArr e s -> Int -> e -> ST s ()
copyMU :: (UA e) => MUArr e s -> Int -> UArr e -> ST s ()
unsafeFreezeMU :: (UA e) => MUArr e s -> Int -> ST s (UArr e)
memcpyMU :: (UA e) => MUArr e s -> MUArr e s -> Int -> ST s ()
memcpyOffMU :: (UA e) => MUArr e s -> MUArr e s -> Int -> Int -> Int -> ST s ()
memmoveOffMU :: (UA e) => MUArr e s -> MUArr e s -> Int -> Int -> Int -> ST s ()
-- | O(1). streamU generates a stream from an array, from
-- left to right.
streamU :: (UA a) => UArr a -> Stream a
-- | O(n). unstreamU creates an array from a stream, filling
-- it from left to right.
unstreamU :: (UA a) => Stream a -> UArr a
-- | O(n). toU turns a list into a UArr.
toU :: (UA e) => [e] -> UArr e
-- | O(n). fromU collects the elements of a UArr into
-- a list.
fromU :: (UA e) => UArr e -> [e]
-- | O(1). emptyU yields an empty array.
emptyU :: (UA e) => UArr e
-- | O(1). singletonU yields a singleton array containing the
-- given element.
singletonU :: (UA e) => e -> UArr e
-- | O(n). consU prepends the given element to an array.
consU :: (UA e) => e -> UArr e -> UArr e
-- | O(n). snocU appends the given element to an array.
snocU :: (UA e) => UArr e -> e -> UArr e
-- | O(n). appendU concatenates two arrays.
appendU :: (UA e) => UArr e -> UArr e -> UArr e
-- | O(n). Concatenate a list of arrays.
concatU :: (UA e) => [UArr e] -> UArr e
-- | O(1). headU yields the first element of an array.
headU :: (UA e) => UArr e -> e
-- | O(n). lastU yields the last element of an array.
lastU :: (UA e) => UArr e -> e
-- | O(n). tailU yields the given array without its initial
-- element.
tailU :: (UA e) => UArr e -> UArr e
-- | O(n). initU yields the input array without its last
-- element.
initU :: (UA e) => UArr e -> UArr e
-- | O(1). nullU tests whether the given array is empty.
nullU :: (UA e) => UArr e -> Bool
-- | O(1). Yield an array of units.
unitsU :: Int -> UArr ()
-- | O(1). lengthU returns the length of a UArr as an
-- Int.
lengthU :: (UA e) => UArr e -> Int
-- | O(n). mapU maps a function over an array.
mapU :: (UA e, UA e') => (e -> e') -> UArr e -> UArr e'
-- | O(n). foldU reduces an array using an associative
-- combination function and its unit.
foldU :: (UA a) => (a -> a -> a) -> a -> UArr a -> a
-- | O(n). fold1U is a variant of foldU that requires
-- a non-empty input array. Throws an exception if its input array is
-- empty.
fold1U :: (UA a) => (a -> a -> a) -> UArr a -> a
-- | O(n). fold1MaybeU behaves like fold1U but returns
-- NothingS if the input array is empty.
fold1MaybeU :: (UA a) => (a -> a -> a) -> UArr a -> MaybeS a
-- | O(n). foldlU reduces an array proceeding from the left.
foldlU :: (UA a) => (b -> a -> b) -> b -> UArr a -> b
-- | O(n). foldl1U is a variant of foldlU that assumes
-- a non-empty input array, but requires no starting element. Throws an
-- exception if the input array is empty.
foldl1U :: (UA a) => (a -> a -> a) -> UArr a -> a
-- | O(n) foldrU, applied to a binary operator, a starting
-- value (typically the right-identity of the operator), and a 'UArr a',
-- reduces the 'UArr a' using the binary operator, from right to left.
foldrU :: (UA a) => (a -> b -> b) -> b -> UArr a -> b
-- | O(n) A variant of foldr that has no starting value
-- argument, and thus must be applied to a non-empty 'UArr a'.
foldr1U :: (UA a) => (a -> a -> a) -> UArr a -> a
-- | O(n). foldl1MaybeU behaves like foldl1U but
-- returns NothingS if the input array is empty.
foldl1MaybeU :: (UA a) => (a -> a -> a) -> UArr a -> MaybeS a
-- | O(n). andU yields the conjunction of a boolean array.
andU :: UArr Bool -> Bool
-- | O(n). andU yields the disjunction of a boolean array.
orU :: UArr Bool -> Bool
-- | O(n). anyU p u determines whether any element
-- in array u satisfies predicate p.
anyU :: (UA e) => (e -> Bool) -> UArr e -> Bool
-- | O(n). allU p u determines whether all elements
-- in array u satisfy predicate p.
allU :: (UA e) => (e -> Bool) -> UArr e -> Bool
-- | O(n). sumU computes the sum of an array of a Num
-- instance.
sumU :: (Num e, UA e) => UArr e -> e
-- | O(n). productU computes the product of an array of a
-- Num instance.
productU :: (Num e, UA e) => UArr e -> e
-- | O(n). maximumU finds the maximum element in an array of
-- orderable elements.
maximumU :: (Ord e, UA e) => UArr e -> e
-- | O(n). minimumU finds the minimum element in an array of
-- orderable elements.
minimumU :: (Ord e, UA e) => UArr e -> e
-- | O(n). maximumByU finds the maximum element in an array
-- under the given ordering.
maximumByU :: (UA e) => (e -> e -> Ordering) -> UArr e -> e
-- | O(n). minimumByU finds the minimum element in an array
-- under the given ordering.
minimumByU :: (UA e) => (e -> e -> Ordering) -> UArr e -> e
-- | O(n). scanlU is equivalent to foldlU on all
-- prefixes (except the array itself) of the input array.
--
-- N.B: the behavior of this function differs from that of
-- Data.List. Compare:
--
-- scanl (+) 0.0 [1..5] gives
-- [0.0,1.0,3.0,6.0,10.0,15.0]
--
-- scanlU (+) 0.0 $ toU [1..5] gives toU
-- [0.0,1.0,3.0,6.0,10.0]
--
-- To get behavior closer to the List counterpart, see scanResU.
scanlU :: (UA a, UA b) => (b -> a -> b) -> b -> UArr a -> UArr b
-- | O(n). scanl1U is like scanlU, but requires no
-- starting value.
scanl1U :: (UA a) => (a -> a -> a) -> UArr a -> UArr a
-- | O(n). scanU is equivalent to foldU on all
-- prefixes (except the array itself) of the input array.
scanU :: (UA a) => (a -> a -> a) -> a -> UArr a -> UArr a
-- | O(n). scan1U is like scanU, but requires no
-- starting value.
scan1U :: (UA a) => (a -> a -> a) -> UArr a -> UArr a
-- | O(n). scanResU behaves like scanU, but yields a
-- strict pair with the scanU result as its fstS and the
-- missing element (foldU on the same arguments) as its
-- sndS. Compare:
--
-- scanl (+) 0.0 [1..5] gives
-- [0.0,1.0,3.0,6.0,10.0,15.0]
--
-- scanlU (+) 0.0 $ toU [1..5] gives toU
-- [0.0,1.0,3.0,6.0,10.0]
--
-- scanResU (+) 0.0 $ toU [1..5] gives toU
-- [0.0,1.0,3.0,6.0,10.0] :*: 15.0.
scanResU :: (UA a) => (a -> a -> a) -> a -> UArr a -> UArr a :*: a
-- | O(n). mapAccumLU is an accumulating map from left to
-- right. Unlike its List counterpart, it does not return the
-- accumulator.
mapAccumLU :: (UA a, UA b) => (c -> a -> c :*: b) -> c -> UArr a -> UArr b
-- | O(n). iterateU n f a constructs an array of
-- size n by iteratively applying f to a.
iterateU :: (UA a) => Int -> (a -> a) -> a -> UArr a
-- | O(n). replicateU n e yields an array containing
-- n repetitions of e.
replicateU :: (UA e) => Int -> e -> UArr e
-- | O(n). replicateEachU n r e yields an array such
-- that each element in e is repeated as many times as the value
-- contained at the corresponding index in r. For example:
--
-- replicateEachU 10 (toU [1..3]) (toU [3..5]) yields toU
-- [3.0,4.0,4.0,5.0,5.0,5.0]
--
-- N.B: the n parameter specifies how many elements are
-- allocated for the output array, but the function will happily
-- overrun the allocated buffer for all sorts of interesting effects! The
-- caller is expected to ensure that n <= sumU r.
replicateEachU :: (UA e) => Int -> UArr Int -> UArr e -> UArr e
-- | O(n). unfoldU n f z builds an array of size
-- n from a seed value z by iteratively applying
-- f, stopping when n elements have been generated or
-- f returns NothingS.
unfoldU :: (UA a) => Int -> (b -> MaybeS (a :*: b)) -> b -> UArr a
-- | O(n). takeU yields the prefix of the given length of an
-- array.
takeU :: (UA e) => Int -> UArr e -> UArr e
-- | O(n). dropU yields the suffix obtained by dropping the
-- given number of elements from an array.
dropU :: (UA e) => Int -> UArr e -> UArr e
-- | O(n). splitAtU splits an array into two subarrays at the
-- given index.
splitAtU :: (UA e) => Int -> UArr e -> (UArr e, UArr e)
-- | O(n). takeWhileU, applied to a predicate p and
-- a UArr xs, returns the longest prefix (possibly empty) of
-- xs of elements that satisfy p.
takeWhileU :: (UA e) => (e -> Bool) -> UArr e -> UArr e
-- | O(n). dropWhileU p xs returns the suffix
-- remaining after takeWhileU p xs.
dropWhileU :: (UA e) => (e -> Bool) -> UArr e -> UArr e
-- | O(n). elemU determines whether the given element is in
-- an array.
elemU :: (Eq e, UA e) => e -> UArr e -> Bool
-- | O(n). Negation of elemU.
notElemU :: (Eq e, UA e) => e -> UArr e -> Bool
-- | O(n). filterU extracts all elements from an array that
-- satisfy the given predicate.
filterU :: (UA e) => (e -> Bool) -> UArr e -> UArr e
-- | O(n), fusion. The findU function takes a
-- predicate and an array and returns the first element in the list
-- matching the predicate, or Nothing if there is no such element.
findU :: (UA a) => (a -> Bool) -> UArr a -> Maybe a
-- | O(n), fusion. The findIndexU function takes a
-- predicate and an array and returns the index of the first element in
-- the array satisfying the predicate, or Nothing if there is no
-- such element.
findIndexU :: (UA a) => (a -> Bool) -> UArr a -> Maybe Int
-- | indexU extracts an element out of an immutable unboxed array.
--
-- TODO: use indexU, the non-streaming version.
indexU :: (UA e) => UArr e -> Int -> e
-- | O(n), fusion. lookupU key assocs looks
-- up a key in an array of pairs treated as an association table.
lookupU :: (Eq a, UA a, UA b) => a -> UArr (a :*: b) -> Maybe b
-- | O(1). Elementwise pairing of array elements.
--
-- N.B: The output will be as long as the first array (and will
-- thus access past the end of the second array), unlike its List
-- counterpart. This will not occur at the time zipU is called, but only
-- after the resulting array is accessed.
zipU :: (UA a, UA b) => UArr a -> UArr b -> UArr (a :*: b)
-- | O(1). zip3U takes three arrays and returns an array of
-- triples.
zip3U :: (UA e1, UA e2, UA e3) => UArr e1 -> UArr e2 -> UArr e3 -> UArr ((e1 :*: e2) :*: e3)
-- | O(1). Elementwise unpairing of array elements.
unzipU :: (UA a, UA b) => UArr (a :*: b) -> (UArr a :*: UArr b)
-- | O(1). unzip3U unpairs an array of strict triples into
-- three arrays.
unzip3U :: (UA e1, UA e2, UA e3) => UArr ((e1 :*: e2) :*: e3) -> ((UArr e1 :*: UArr e2) :*: UArr e3)
-- | O(n). zipWithU applies a function to corresponding
-- elements of two arrays, yielding an array containing the results.
zipWithU :: (UA a, UA b, UA c) => (a -> b -> c) -> UArr a -> UArr b -> UArr c
-- | O(n). zipWith3U applies a function to corresponding
-- elements of three arrays, yielding an array with the results.
zipWith3U :: (UA a, UA b, UA c, UA d) => (a -> b -> c -> d) -> UArr a -> UArr b -> UArr c -> UArr d
-- | O(1). Yield the first components of an array of pairs.
fstU :: (UA a, UA b) => UArr (a :*: b) -> UArr a
-- | O(1). Yield the second components of an array of pairs.
sndU :: (UA a, UA b) => UArr (a :*: b) -> UArr b
-- | O(n). enumFromToU yields an enumerated array, analogous
-- to enumFromTo, but only works on instances of Integral.
enumFromToU :: (UA a, Integral a) => a -> a -> UArr a
-- | O(n). Like enumFromToU, but works on fractional numbers
-- (still incrementing by 1 each time).
enumFromToFracU :: (UA a, RealFrac a) => a -> a -> UArr a
-- | O(n). enumFromThenToU yields an enumerated array using a
-- specific step value.
enumFromThenToU :: Int -> Int -> Int -> UArr Int
-- | O(n). enumFromStepLenU s d n yields an
-- enumerated array of length n starting from s with an
-- increment of d.
enumFromStepLenU :: Int -> Int -> Int -> UArr Int
-- | O(n). enumFromToEachU n u yields an array by
-- taking each strict pair u and treating it as a range to
-- generate successive values over. For example:
--
-- enumFromToEachU 7 (toU [3 :*: 6, 8 :*: 10]) yields toU
-- [3,4,5,6,8,9,10]
--
-- N.B: This function will allocate n slots for the
-- output array, and will happily overrun its allocated space if the
-- u leads it to do so. The caller is expected to ensure that
-- n = (sumU . mapU (\(x :*: y) - y - x + 1) $ u).
enumFromToEachU :: Int -> UArr (Int :*: Int) -> UArr Int
-- | O(n). combineU f a1 a2 yields an array by
-- picking elements from a1 if f is True at
-- the given position, and picking elements from a2 otherwise.
-- For example:
--
--
-- combineU (toU [True,True,False,True,False,False]) (toU [1..3]) (toU [4..6])
--
--
-- yields toU [1.0,2.0,4.0,3.0,5.0,6.0].
combineU :: (UA a) => UArr Bool -> UArr a -> UArr a -> UArr a
-- | O(n). packU extracts all elements from an array
-- according to the provided flag array. For example:
--
--
-- packU (toU [1..5]) (toU [True,False,False,False,True])
--
--
-- yields toU [1.0,5.0].
packU :: (UA e) => UArr e -> UArr Bool -> UArr e
-- | O(n). indexedU associates each element of the array with
-- its index.
indexedU :: (UA e) => UArr e -> UArr (Int :*: e)
-- | O(n). repeatU n u repeats an array u
-- n times.
repeatU :: (UA e) => Int -> UArr e -> UArr e
-- | O(n). newU constructs an immutable array of the given
-- size by performing the provided initialization function on a mutable
-- representation of the output array.
newU :: (UA e) => Int -> (forall s. MUArr e s -> ST s ()) -> UArr e
-- | O(1). unsafeFreezeAllMU converts an entire mutable array
-- into an immutable array, without copying. The mutable array must not
-- be mutated after this.
unsafeFreezeAllMU :: (UA e) => MUArr e s -> ST s (UArr e)
-- | O(n). permuteMU permutes a MUArr according to a
-- UArr of permuted indices.
permuteMU :: (UA e) => MUArr e s -> UArr e -> UArr Int -> ST s ()
-- | O(n). atomicUpdateMU arr upds replaces elements
-- at specific indices of arr based on the contents of
-- upds (where fstS indicates the index to
-- replace, sndS the replacement value).
atomicUpdateMU :: (UA e) => MUArr e s -> UArr (Int :*: e) -> ST s ()
-- | O(n). unstreamMU fills a mutable array from a stream
-- from left to right and yields the number of elements written.
unstreamMU :: (UA a) => MUArr a s -> Stream a -> ST s Int
-- | Elementwise pairing of mutable arrays. This is an unsafe operation, as
-- no copying is performed, so changes to the pair array will affect the
-- original arrays, and vice versa.
unsafeZipMU :: (UA a, UA b) => MUArr a s -> MUArr b s -> MUArr (a :*: b) s
-- | Elementwise unpairing of mutable arrays. This is an unsafe operation,
-- as no copying is performed, so changes to the unpaired arrays will
-- affect the original, and vice versa.
unsafeUnzipMU :: (UA a, UA b) => MUArr (a :*: b) s -> MUArr a s :*: MUArr b s
-- | Strict pair
data (:*:) a b
(:*:) :: !a -> !b -> :*: a b
-- | Strict sum
data EitherS a b
LeftS :: !a -> EitherS a b
RightS :: !b -> EitherS a b
-- | Analog to fst in regular pairs.
fstS :: a :*: b -> a
-- | Analog to snd in regular pairs.
sndS :: a :*: b -> b
-- | Converts a pair to a strict pair.
pairS :: (a, b) -> a :*: b
-- | Converts a strict pair to a pair.
unpairS :: a :*: b -> (a, b)
unsafe_pairS :: (a, b) -> a :*: b
unsafe_unpairS :: a :*: b -> (a, b)
-- | Analogous to curry in regular pairs.
curryS :: (a :*: b -> c) -> a -> b -> c
-- | Analogous to uncurry in regular pairs.
uncurryS :: (a -> b -> c) -> a :*: b -> c
-- | Strict Maybe
data MaybeS a
NothingS :: MaybeS a
JustS :: !a -> MaybeS a
-- | O(1). maybeS n f m is the catamorphism for
-- MaybeS, returning n if m is NothingS,
-- and applying f to the value wrapped in JustS
-- otherwise.
maybeS :: b -> (a -> b) -> MaybeS a -> b
-- | O(1). fromMaybeS n m returns n if
-- m is NothingS and the value wrapped in JustS
-- otherwise.
fromMaybeS :: a -> MaybeS a -> a