{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE CPP #-}

#if MIN_VERSION_base(4,12,0)
{-# LANGUAGE NoStarIsType #-}
#endif

{-|
This module reexports the functionality in 'Data.Vector.Generic' which maps well
to explicity sized vectors.

Functions returning a vector determine the size from the type context unless
they have a @'@ suffix in which case they take an explicit 'Proxy' argument.

Functions where the resultant vector size is not know until compile time are
not exported.
-}

module Data.Vector.Generic.Sized
  ( Vector
  , MVector
   -- * Accessors
   -- ** Length information
  , length
  , length'
  , knownLength
  , knownLength'
    -- ** Indexing
  , index
  , index'
  , unsafeIndex
  , head
  , last
    -- ** Monadic indexing
  , indexM
  , indexM'
  , unsafeIndexM
  , headM
  , lastM
    -- ** Extracting subvectors (slicing)
  , slice
  , slice'
  , init
  , tail
  , take
  , take'
  , drop
  , drop'
  , splitAt
  , splitAt'
    -- * Construction
    -- ** Initialization
  , empty
  , singleton
  , fromTuple
  , replicate
  , replicate'
  , generate
  , generate'
  , iterateN
  , iterateN'
    -- ** Monadic initialization
  , replicateM
  , replicateM'
  , generateM
  , generateM'
    -- ** Unfolding
  , unfoldrN
  , unfoldrN'
    -- ** Enumeration
  , enumFromN
  , enumFromN'
  , enumFromStepN
  , enumFromStepN'
    -- ** Concatenation
  , cons
  , snoc
  , (++)
    -- ** Restricting memory usage
  , force
    -- * Modifying vectors
    -- ** Bulk updates
  , (//)
  , update
  , update_
  , unsafeUpd
  , unsafeUpdate
  , unsafeUpdate_
    -- ** Accumulations
  , accum
  , accumulate
  , accumulate_
  , unsafeAccum
  , unsafeAccumulate
  , unsafeAccumulate_
    -- ** Permutations
  , reverse
  , backpermute
  , unsafeBackpermute
    -- * Lenses
  , ix
  , _head
  , _last
    -- * Elementwise operations
    -- ** Indexing
  , indexed
    -- ** Mapping
  , map
  , imap
  , concatMap
    -- ** Monadic mapping
  , mapM
  , imapM
  , mapM_
  , imapM_
  , forM
  , forM_
    -- ** Zipping
  , zipWith
  , zipWith3
  , zipWith4
  , zipWith5
  , zipWith6
  , izipWith
  , izipWith3
  , izipWith4
  , izipWith5
  , izipWith6
  , zip
  , zip3
  , zip4
  , zip5
  , zip6
    -- ** Monadic zipping
  , zipWithM
  , izipWithM
  , zipWithM_
  , izipWithM_
    -- ** Unzipping
  , unzip
  , unzip3
  , unzip4
  , unzip5
  , unzip6
    -- * Working with predicates
    -- ** Searching
  , elem
  , notElem
  , find
  , findIndex
  , elemIndex
    -- * Folding
  , foldl
  , foldl1
  , foldl'
  , foldl1'
  , foldr
  , foldr1
  , foldr'
  , foldr1'
  , ifoldl
  , ifoldl'
  , ifoldr
  , ifoldr'
    -- ** Specialised folds
  , all
  , any
  , and
  , or
  , sum
  , product
  , maximum
  , maximumBy
  , minimum
  , minimumBy
  , maxIndex
  , maxIndexBy
  , minIndex
  , minIndexBy
    -- ** Monadic folds
  , foldM
  , ifoldM
  , fold1M
  , foldM'
  , ifoldM'
  , fold1M'
  , foldM_
  , ifoldM_
  , fold1M_
  , foldM'_
  , ifoldM'_
  , fold1M'_
    -- ** Monadic sequencing
  , sequence
  , sequence_
    -- * Prefix sums (scans)
  , prescanl
  , prescanl'
  , postscanl
  , postscanl'
  , scanl
  , scanl'
  , scanl1
  , scanl1'
  , prescanr
  , prescanr'
  , postscanr
  , postscanr'
  , scanr
  , scanr'
  , scanr1
  , scanr1'
    -- * Conversions
    -- ** Lists
  , toList
  , fromList
  , fromListN
  , fromListN'
  , withSizedList
    -- ** Other Vector types
  , convert
    -- ** Mutable vectors
  , freeze
  , thaw
  , copy
  , unsafeFreeze
  , unsafeThaw
    -- ** Unsized Vectors
  , toSized
  , withSized
  , fromSized
  , withVectorUnsafe
  ) where

import Data.Vector.Generic.Sized.Internal
import qualified Data.Vector.Generic as VG
import qualified Data.Vector as Boxed
import qualified Data.Vector.Generic.Mutable.Sized as SVGM
import Data.Vector.Generic.Mutable.Sized.Internal
import GHC.Generics (Generic)
import GHC.TypeLits
import Data.Bifunctor
import Data.Finite
import Data.Finite.Internal
import Data.Proxy
import Control.DeepSeq (NFData)
import Control.Monad.Primitive
import Foreign.Storable
import Data.Data
import Data.Functor.Classes
import Control.Comonad
import Foreign.Ptr (castPtr)
import Data.Semigroup
import Text.Read.Lex
import Text.ParserCombinators.ReadPrec
import GHC.Read
import Data.Type.Equality
import Unsafe.Coerce
import qualified Data.Functor.Rep as Rep
import Data.Distributive
import Prelude
       hiding (length, replicate, (++), head, last, init, tail, take,
               drop, splitAt, reverse, map, concatMap, zipWith, zipWith3, zip,
               zip3, unzip, unzip3, elem, notElem, foldl, foldl1, foldr, foldr1,
               all, any, and, or, sum, product, maximum, minimum, scanl, scanl1,
               scanr, scanr1, mapM, mapM_, sequence, sequence_)


import Data.IndexedListLiterals hiding (toList, fromList)
import qualified Data.IndexedListLiterals as ILL

instance (KnownNat n, VG.Vector v a, Read (v a)) => Read (Vector v n a) where
  readPrec = parens $ prec 10 $ do
      expectP (Ident "Vector")
      vec <- readPrec
      if VG.length vec == (fromIntegral $ natVal (Proxy :: Proxy n)) then return $ Vector vec else pfail

type instance VG.Mutable (Vector v n) = MVector (VG.Mutable v) n

-- | Any sized vector containing storable elements is itself storable.
instance (KnownNat n, Storable a, VG.Vector v a)
      => Storable (Vector v n a) where
  sizeOf _ = sizeOf (undefined :: a) * fromIntegral (natVal (Proxy :: Proxy n))
  alignment _ = alignment (undefined :: a)
  peek ptr = generateM (peekElemOff (castPtr ptr) . fromIntegral)
  poke ptr = imapM_ (pokeElemOff (castPtr ptr) . fromIntegral)

-- | The 'Applicative' instance for sized vectors does not have the same
-- behaviour as the 'Applicative' instance for the unsized vectors found in the
-- 'vectors' package. The instance defined here has the same behaviour as the
-- 'Control.Applicative.ZipList' instance.
instance KnownNat n => Applicative (Vector Boxed.Vector n) where
  pure = replicate
  (<*>) = zipWith ($)
  (*>) = seq
  (<*) = flip seq

-- | Treats a @'Data.Vector.Sized.Vector' n a@ as, essentially, a @'Finite'
-- n -> a@, and emulates the 'Monad' instance for that function.
--
-- @'join' :: Vector n (Vector n a) -> Vector n a@ gets the /diagonal/ from
-- a square "matrix".
instance KnownNat n => Monad (Vector Boxed.Vector n) where
  return   = replicate
  xs >>= f = imap (\i x -> f x `index` i) xs
  (>>)     = seq

-- | Non-empty sized vectors are lawful comonads.
--
-- 'extract' is 'head'
--
-- 'duplicate' generates all unique sequences of a vector with the same length as it,
-- using wrap-around.
--
-- e.g.
-- @
-- duplicate [1,2,3,4,5] = [[1,2,3,4,5], [2,3,4,5,1], [3,4,5,1,2], [4,5,1,2,3], [5,1,2,3,4]]
-- @
instance (KnownNat n, n ~ (1 + m)) => Comonad (Vector Boxed.Vector n) where
  extract = head
  extend f r@(Vector v) = Vector $ VG.generate len (\i -> f (Vector (VG.slice i len v')))
    where
      v' = v VG.++ VG.init v
      len = length r

instance (KnownNat n, n ~ (1 + m)) => ComonadApply (Vector Boxed.Vector n) where
  (<@>) = (<*>)
  (<@)  = (<*)
  (@>)  = (*>)

-- | The 'Semigroup' instance for sized vectors does not have the same
-- behaviour as the 'Semigroup' instance for the unsized vectors found in the
-- 'vectors' package. This instance has @(<>) = zipWith (<>)@, but 'vectors'
-- uses concatentation.
instance (Semigroup g, VG.Vector v g) => Semigroup (Vector v n g) where
  (<>) = zipWith (<>)
  stimes = map . stimes

-- | The 'Monoid' instance for sized vectors does not have the same
-- behaviour as the 'Monoid' instance for the unsized vectors found in the
-- 'vectors' package. This instance has @mempty = replicate mempty@ and
-- @mappend = zipWith mappend@, where the 'vectors' instance uses the empty
-- vector and concatenation.
--
-- If 'mempty' is not necessary, using the 'Semigroup' instance over this
-- 'Monoid' will dodge the 'KnownNat' constraint.
instance (Monoid m, VG.Vector v m, KnownNat n) => Monoid (Vector v n m) where
  mempty = replicate mempty
  mappend = zipWith mappend
  mconcat vs = generate $ mconcat . flip fmap vs . flip index

instance KnownNat n => Distributive (Vector Boxed.Vector n) where
  distribute = Rep.distributeRep
  {-# inline distribute #-}

instance KnownNat n => Rep.Representable (Vector Boxed.Vector n) where
  type Rep (Vector Boxed.Vector n) = Finite n
  tabulate = generate
  {-# inline tabulate #-}
  index = Data.Vector.Generic.Sized.index
  {-# inline index #-}

-- | /O(1)/ Yield the length of the vector as an 'Int'. This is more like
-- 'natVal' than 'Data.Vector.length', extracting the value from the 'KnownNat'
-- instance and not looking at the vector itself.
length :: forall v n a. KnownNat n
       => Vector v n a -> Int
length _ = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline length #-}

-- | /O(1)/ Yield the length of the vector as a 'Proxy'. This function
-- doesn't /do/ anything; it merely allows the size parameter of the vector
-- to be passed around as a 'Proxy'.
length' :: forall v n a.
           Vector v n a -> Proxy n
length' _ = Proxy
{-# inline length' #-}

-- | /O(1)/ Reveal a 'KnownNat' instance for a vector's length, determined
-- at runtime.
knownLength :: forall v n a r. VG.Vector v a
            => Vector v n a -- ^ a vector of some (potentially unknown) length
            -> (KnownNat n => r) -- ^ a value that depends on knowing the vector's length
            -> r -- ^ the value computed with the length
knownLength v x = knownLength' v $ const x

-- | /O(1)/ Reveal a 'KnownNat' instance and 'Proxy' for a vector's length,
-- determined at runtime.
knownLength' :: forall v n a r. VG.Vector v a
             => Vector v n a -- ^ a vector of some (potentially unknown) length
             -> (KnownNat n => Proxy n -> r) -- ^ a value that depends on knowing the vector's length, which is given as a 'Proxy'
             -> r -- ^ the value computed with the length
knownLength' (Vector v) x = case someNatVal (fromIntegral (VG.length v)) of
  Just (SomeNat (Proxy :: Proxy n')) -> case unsafeCoerce Refl :: n' :~: n of Refl -> x Proxy
  Nothing -> error "impossible: Vector has negative length"

-- | /O(1)/ Safe indexing using a 'Finite'.
index :: forall v n a. VG.Vector v a
      => Vector v n a -> Finite n -> a
index (Vector v) (Finite i) = v `VG.unsafeIndex` fromIntegral i
{-# inline index #-}

-- | /O(1)/ Safe indexing using a 'Proxy'.
index' :: forall v n m a p. (KnownNat n, VG.Vector v a)
       => Vector v (n+m+1) a -> p n -> a
index' (Vector v) p = v `VG.unsafeIndex` i
  where i = fromIntegral (natVal p)
{-# inline index' #-}

-- | /O(1)/ Indexing using an Int without bounds checking.
unsafeIndex :: forall v n a. VG.Vector v a
      => Vector v n a -> Int -> a
unsafeIndex (Vector v) i = v `VG.unsafeIndex` i
{-# inline unsafeIndex #-}

-- | /O(1)/ Yield the first element of a non-empty vector.
head :: forall v n a. VG.Vector v a
     => Vector v (1+n) a -> a
head (Vector v) = VG.unsafeHead v
{-# inline head #-}

-- | /O(1)/ Yield the last element of a non-empty vector.
last :: forall v n a. (VG.Vector v a)
     => Vector v (n+1) a -> a
last (Vector v) = VG.unsafeLast v
{-# inline last #-}

-- | Lens to access (/O(1)/) and update (/O(n)/) an arbitrary element by its index.
ix :: forall v n a f. (VG.Vector v a, Functor f)
   => Finite n -> (a -> f a) -> Vector v n a -> f (Vector v n a)
ix n f vector = (\x -> vector // [(n, x)]) <$> f (index vector n)
{-# inline ix #-}

-- | Lens to access (/O(1)/) and update (/O(n)/) the first element of a non-empty vector.
_head :: forall v n a f. (VG.Vector v a, Functor f)
      => (a -> f a) -> Vector v (1+n) a -> f (Vector v (1+n) a)
_head f vector = (\x -> cons x $ tail vector) <$> f (head vector)
{-# inline _head #-}

-- | Lens to access (/O(1)/) and update (/O(n)/) the last element of a non-empty vector.
_last :: forall v n a f. (VG.Vector v a, Functor f)
       => (a -> f a) -> Vector v (n+1) a -> f (Vector v (n+1) a)
_last f vector = (\x -> snoc (init vector) x) <$> f (last vector)
{-# inline _last #-}

-- | /O(1)/ Safe indexing in a monad. See the documentation for 'VG.indexM' for
-- an explanation of why this is useful.
indexM :: forall v n a m. (VG.Vector v a, Monad m)
      => Vector v n a -> Finite n -> m a
indexM (Vector v) (Finite i) = v `VG.indexM` fromIntegral i
{-# inline indexM #-}

-- | /O(1)/ Safe indexing in a monad using a 'Proxy'. See the documentation for
-- 'VG.indexM' for an explanation of why this is useful.
indexM' :: forall v n k a m p. (KnownNat n, VG.Vector v a, Monad m)
      => Vector v (n+k) a -> p n -> m a
indexM' (Vector v) p = v `VG.indexM` i
  where i = fromIntegral (natVal p)
{-# inline indexM' #-}

-- | /O(1)/ Indexing using an Int without bounds checking. See the
-- documentation for 'VG.indexM' for an explanation of why this is useful.
unsafeIndexM :: forall v n a m. (VG.Vector v a, Monad m)
      => Vector v n a -> Int -> m a
unsafeIndexM (Vector v) i = v `VG.unsafeIndexM` i
{-# inline unsafeIndexM #-}

-- | /O(1)/ Yield the first element of a non-empty vector in a monad. See the
-- documentation for 'VG.indexM' for an explanation of why this is useful.
headM :: forall v n a m. (VG.Vector v a, Monad m)
      => Vector v (1+n) a -> m a
headM (Vector v) = VG.unsafeHeadM v
{-# inline headM #-}

-- | /O(1)/ Yield the last element of a non-empty vector in a monad. See the
-- documentation for 'VG.indexM' for an explanation of why this is useful.
lastM :: forall v n a m. (VG.Vector v a, Monad m)
      => Vector v (n+1) a -> m a
lastM (Vector v) = VG.unsafeLastM v
{-# inline lastM #-}

-- | /O(1)/ Yield a slice of the vector without copying it with an inferred
-- length argument.
slice :: forall v i n m a p. (KnownNat i, KnownNat n, VG.Vector v a)
      => p i -- ^ starting index
      -> Vector v (i+n+m) a
      -> Vector v n a
slice start (Vector v) = Vector (VG.unsafeSlice i n v)
  where i = fromIntegral (natVal start)
        n = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline slice #-}

-- | /O(1)/ Yield a slice of the vector without copying it with an explicit
-- length argument.
slice' :: forall v i n m a p
        . (KnownNat i, KnownNat n, VG.Vector v a)
       => p i -- ^ starting index
       -> p n -- ^ length
       -> Vector v (i+n+m) a
       -> Vector v n a
slice' start _ = slice start
{-# inline slice' #-}

-- | /O(1)/ Yield all but the last element of a non-empty vector without
-- copying.
init :: forall v n a. (VG.Vector v a)
     => Vector v (n+1) a -> Vector v n a
init (Vector v) = Vector (VG.unsafeInit v)
{-# inline init #-}

-- | /O(1)/ Yield all but the first element of a non-empty vector without
-- copying.
tail :: forall v n a. (VG.Vector v a)
     => Vector v (1+n) a -> Vector v n a
tail (Vector v) = Vector (VG.unsafeTail v)
{-# inline tail #-}

-- | /O(1)/ Yield the first n elements. The resultant vector always contains
-- this many elements. The length of the resultant vector is inferred from the
-- type.
take :: forall v n m a. (KnownNat n, VG.Vector v a)
     => Vector v (n+m) a -> Vector v n a
take (Vector v) = Vector (VG.unsafeTake i v)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline take #-}

-- | /O(1)/ Yield the first n elements. The resultant vector always contains
-- this many elements. The length of the resultant vector is given explicitly
-- as a 'Proxy' argument.
take' :: forall v n m a p. (KnownNat n, VG.Vector v a)
      => p n -> Vector v (n+m) a -> Vector v n a
take' _ = take
{-# inline take' #-}

-- | /O(1)/ Yield all but the the first n elements. The given vector must
-- contain at least this many elements The length of the resultant vector is
-- inferred from the type.
drop :: forall v n m a. (KnownNat n, VG.Vector v a)
     => Vector v (n+m) a -> Vector v m a
drop (Vector v) = Vector (VG.unsafeDrop i v)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline drop #-}

-- | /O(1)/ Yield all but the the first n elements. The given vector must
-- contain at least this many elements The length of the resultant vector is
-- givel explicitly as a 'Proxy' argument.
drop' :: forall v n m a p. (KnownNat n, VG.Vector v a)
      => p n -> Vector v (n+m) a -> Vector v m a
drop' _ = drop
{-# inline drop' #-}

-- | /O(1)/ Yield the first n elements paired with the remainder without copying.
-- The lengths of the resultant vector are inferred from the type.
splitAt :: forall v n m a. (KnownNat n, VG.Vector v a)
        => Vector v (n+m) a -> (Vector v n a, Vector v m a)
splitAt (Vector v) = (Vector a, Vector b)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
        (a, b) = VG.splitAt i v
{-# inline splitAt #-}

-- | /O(1)/ Yield the first n elements paired with the remainder without
-- copying.  The length of the first resultant vector is passed explicitly as a
-- 'Proxy' argument.
splitAt' :: forall v n m a p. (KnownNat n, VG.Vector v a)
         => p n -> Vector v (n+m) a -> (Vector v n a, Vector v m a)
splitAt' _ = splitAt
{-# inline splitAt' #-}

--------------------------------------------------------------------------------
-- * Construction
--------------------------------------------------------------------------------

--
-- ** Initialization
--

-- | /O(1)/ Empty vector.
empty :: forall v a. (VG.Vector v a)
      => Vector v 0 a
empty = Vector VG.empty
{-# inline empty #-}

-- | /O(1)/ Vector with exactly one element.
singleton :: forall v a. (VG.Vector v a)
           => a -> Vector v 1 a
singleton a = Vector (VG.singleton a)
{-# inline singleton #-}

-- | /O(n)/ Construct a vector in a type safe manner
--   fromTuple (1,2) :: Vector v 2 Int
--   fromTuple ("hey", "what's", "going", "on") :: Vector v 4 String
fromTuple :: forall v a input length.
             (VG.Vector v a, IndexedListLiterals input length a, KnownNat length)
          => input -> Vector v length a
fromTuple = Vector . VG.fromListN (fromIntegral $ natVal $ Proxy @length) . ILL.toList

-- | /O(n)/ Construct a vector with the same element in each position where the
-- length is inferred from the type.
replicate :: forall v n a. (KnownNat n, VG.Vector v a)
          => a -> Vector v n a
replicate a = Vector (VG.replicate i a)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline replicate #-}

-- | /O(n)/ Construct a vector with the same element in each position where the
-- length is given explicitly as a 'Proxy' argument.
replicate' :: forall v n a p. (KnownNat n, VG.Vector v a)
           => p n -> a -> Vector v n a
replicate' _ = replicate
{-# inline replicate' #-}

-- | /O(n)/ construct a vector of the given length by applying the function to
-- each index where the length is inferred from the type.
generate :: forall v n a. (KnownNat n, VG.Vector v a)
         => (Finite n -> a) -> Vector v n a
generate f = Vector (VG.generate i (f . Finite . fromIntegral))
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline generate #-}

-- | /O(n)/ construct a vector of the given length by applying the function to
-- each index where the length is given explicitly as a 'Proxy' argument.
generate' :: forall v n a p. (KnownNat n, VG.Vector v a)
          => p n -> (Finite n -> a) -> Vector v n a
generate' _ = generate
{-# inline generate' #-}

-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
-- The length is inferred from the type.
iterateN :: forall v n a. (KnownNat n, VG.Vector v a)
         => (a -> a) -> a -> Vector v n a
iterateN f z = Vector (VG.iterateN i f z)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline iterateN #-}

-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
-- The length is given explicitly as a 'Proxy' argument.
iterateN' :: forall v n a p. (KnownNat n, VG.Vector v a)
          => p n -> (a -> a) -> a -> Vector v n a
iterateN' _ = iterateN
{-# inline iterateN' #-}

--
-- ** Monadic initialisation
--

-- | /O(n)/ Execute the monadic action @n@ times and store the results in a
-- vector where @n@ is inferred from the type.
replicateM :: forall v n m a. (KnownNat n, VG.Vector v a, Monad m)
           => m a -> m (Vector v n a)
replicateM a = Vector <$> VG.replicateM i a
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline replicateM #-}

-- | /O(n)/ Execute the monadic action @n@ times and store the results in a
-- vector where @n@ is given explicitly as a 'Proxy' argument.
replicateM' :: forall v n m a p. (KnownNat n, VG.Vector v a, Monad m)
            => p n -> m a -> m (Vector v n a)
replicateM' _ = replicateM
{-# inline replicateM' #-}

-- | /O(n)/ Construct a vector of length @n@ by applying the monadic action to
-- each index where n is inferred from the type.
generateM :: forall v n m a. (KnownNat n, VG.Vector v a, Monad m)
          => (Finite n -> m a) -> m (Vector v n a)
generateM f = Vector <$> VG.generateM i (f . Finite . fromIntegral)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline generateM #-}

-- | /O(n)/ Construct a vector of length @n@ by applying the monadic action to
-- each index where n is given explicitly as a 'Proxy' argument.
generateM' :: forall v n m a p. (KnownNat n, VG.Vector v a, Monad m)
           => p n -> (Finite n -> m a) -> m (Vector v n a)
generateM' _ = generateM
{-# inline generateM' #-}

--
-- ** Unfolding
--

-- | /O(n)/ Construct a vector with exactly @n@ elements by repeatedly applying
-- the generator function to the a seed. The length, @n@, is inferred from the
-- type.
unfoldrN :: forall v n a b. (KnownNat n, VG.Vector v a)
         => (b -> (a, b)) -> b -> Vector v n a
unfoldrN f z = Vector (VG.unfoldrN i (Just . f) z)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline unfoldrN #-}

-- | /O(n)/ Construct a vector with exactly @n@ elements by repeatedly applying
-- the generator function to the a seed. The length, @n@, is given explicitly
-- as a 'Proxy' argument.
unfoldrN' :: forall v n a b p. (KnownNat n, VG.Vector v a)
          => p n -> (b -> (a, b)) -> b -> Vector v n a
unfoldrN' _ = unfoldrN
{-# inline unfoldrN' #-}

--
-- ** Enumeration
--

-- | /O(n)/ Yield a vector of length @n@ containing the values @x@, @x+1@
-- etc. The length, @n@, is inferred from the type.
enumFromN :: forall v n a. (KnownNat n, VG.Vector v a, Num a)
          => a -> Vector v n a
enumFromN a = Vector (VG.enumFromN a i)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline enumFromN #-}

-- | /O(n)/ Yield a vector of length @n@ containing the values @x@, @x+1@
-- etc. The length, @n@, is given explicitly as a 'Proxy' argument.
enumFromN' :: forall v n a p. (KnownNat n, VG.Vector v a, Num a)
           => a -> p n -> Vector v n a
enumFromN' a _ = enumFromN a
{-# inline enumFromN' #-}

-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@,
-- @x+y+y@ etc. The length, @n@, is inferred from the type.
enumFromStepN :: forall v n a. (KnownNat n, VG.Vector v a, Num a)
          => a -> a -> Vector v n a
enumFromStepN a a' = Vector (VG.enumFromStepN a a' i)
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline enumFromStepN #-}

-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@,
-- @x+y+y@ etc. The length, @n@, is given explicitly as a 'Proxy' argument.
enumFromStepN' :: forall v n a p. (KnownNat n, VG.Vector v a, Num a)
               => a -> a -> p n -> Vector v n a
enumFromStepN' a a' _ = enumFromStepN a a'
{-# inline enumFromStepN' #-}

--
-- ** Concatenation
--

-- | /O(n)/ Prepend an element.
cons :: forall v n a. VG.Vector v a
     => a -> Vector v n a -> Vector v (1+n) a
cons x (Vector xs) = Vector (VG.cons x xs)
{-# inline cons #-}

-- | /O(n)/ Append an element.
snoc :: forall v n a. VG.Vector v a
     => Vector v n a -> a -> Vector v (n+1) a
snoc (Vector xs) x = Vector (VG.snoc xs x)
{-# inline snoc #-}

-- | /O(m+n)/ Concatenate two vectors.
(++) :: forall v n m a. VG.Vector v a
     => Vector v n a -> Vector v m a -> Vector v (n+m) a
Vector vn ++ Vector vm = Vector (vn VG.++ vm)
{-# inline (++) #-}

--
-- ** Restricting memory usage
--

-- | /O(n)/ Yield the argument but force it not to retain any extra memory,
-- possibly by copying it.
--
-- This is especially useful when dealing with slices. For example:
--
-- > force (slice 0 2 <huge vector>)
--
-- Here, the slice retains a reference to the huge vector. Forcing it creates
-- a copy of just the elements that belong to the slice and allows the huge
-- vector to be garbage collected.
force :: VG.Vector v a => Vector v n a -> Vector v n a
force (Vector v) = Vector (VG.force v)
{-# inline force #-}


--------------------------------------------------------------------------------
-- * Modifying vectors
--------------------------------------------------------------------------------

--
-- ** Bulk updates
--

-- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
-- element at position @i@ by @a@.
--
-- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
--
(//) :: VG.Vector v a
     => Vector v m a    -- ^ initial vector (of length @m@)
     -> [(Finite m, a)] -- ^ list of index/value pairs (of length @n@)
     -> Vector v m a
Vector v // us = Vector (v VG.// (fmap . first) (fromIntegral . getFinite) us)
{-# inline (//) #-}

-- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,
-- replace the vector element at position @i@ by @a@.
--
-- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>
--
update :: (VG.Vector v a, VG.Vector v (Int, a))
        => Vector v m a        -- ^ initial vector (of length @m@)
        -> Vector v n (Int, a) -- ^ vector of index/value pairs (of length @n@)
        -> Vector v m a
update (Vector v) (Vector w) = Vector (VG.update v w)
{-# inline update #-}

-- | /O(m+n)/ For each index @i@ from the index vector and the
-- corresponding value @a@ from the value vector, replace the element of the
-- initial vector at position @i@ by @a@.
--
-- > update_ <5,9,2,7>  <2,0,2> <1,3,8> = <3,9,8,7>
--
-- This function is useful for instances of 'Vector' that cannot store pairs.
-- Otherwise, 'update' is probably more convenient.
--
-- @
-- update_ xs is ys = 'update' xs ('zip' is ys)
-- @
update_ :: (VG.Vector v a, VG.Vector v Int)
        => Vector v m a   -- ^ initial vector (of length @m@)
        -> Vector v n Int -- ^ index vector (of length @n@)
        -> Vector v n a   -- ^ value vector (of length @n@)
        -> Vector v m a
update_ (Vector v) (Vector is) (Vector w) = Vector (VG.update_ v is w)
{-# inline update_ #-}

-- | Same as ('//') but without bounds checking.
unsafeUpd :: (VG.Vector v a)
          => Vector v m a -- ^ initial vector (of length @m@)
          -> [(Int, a)]   -- ^ list of index/value pairs (of length @n@)
          -> Vector v m a
unsafeUpd (Vector v) us = Vector (VG.unsafeUpd v us)
{-# inline unsafeUpd #-}

-- | Same as 'update' but without bounds checking.
unsafeUpdate :: (VG.Vector v a, VG.Vector v (Int, a))
             => Vector v m a        -- ^ initial vector (of length @m@)
             -> Vector v n (Int, a) -- ^ vector of index/value pairs (of length @n@)
             -> Vector v m a
unsafeUpdate (Vector v) (Vector w) = Vector (VG.unsafeUpdate v w)
{-# inline unsafeUpdate #-}

-- | Same as 'update_' but without bounds checking.
unsafeUpdate_ :: (VG.Vector v a, VG.Vector v Int)
              => Vector v m a   -- ^ initial vector (of length @m@)
              -> Vector v n Int -- ^ index vector (of length @n@)
              -> Vector v n a   -- ^ value vector (of length @n@)
              -> Vector v m a
unsafeUpdate_ (Vector v) (Vector is) (Vector w) =
  Vector (VG.unsafeUpdate_ v is w)
{-# inline unsafeUpdate_ #-}

--
-- ** Accumulations
--

-- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
-- @a@ at position @i@ by @f a b@.
--
-- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
accum :: VG.Vector v a
      => (a -> b -> a) -- ^ accumulating function @f@
      -> Vector v m a  -- ^ initial vector (of length @m@)
      -> [(Int,b)]     -- ^ list of index/value pairs (of length @n@)
      -> Vector v m a
accum f (Vector v) us = Vector (VG.accum f v us)
{-# inline accum #-}

-- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector
-- element @a@ at position @i@ by @f a b@.
--
-- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>
accumulate :: (VG.Vector v a, VG.Vector v (Int, b))
           => (a -> b -> a)      -- ^ accumulating function @f@
           -> Vector v m a       -- ^ initial vector (of length @m@)
           -> Vector v n (Int,b) -- ^ vector of index/value pairs (of length @n@)
           -> Vector v m a
accumulate f (Vector v) (Vector us) = Vector (VG.accumulate f v us)
{-# inline accumulate #-}

-- | /O(m+n)/ For each index @i@ from the index vector and the
-- corresponding value @b@ from the the value vector,
-- replace the element of the initial vector at
-- position @i@ by @f a b@.
--
-- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
--
-- This function is useful for instances of 'Vector' that cannot store pairs.
-- Otherwise, 'accumulate' is probably more convenient:
--
-- @
-- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
-- @
accumulate_ :: (VG.Vector v a, VG.Vector v Int, VG.Vector v b)
            => (a -> b -> a)  -- ^ accumulating function @f@
            -> Vector v m a   -- ^ initial vector (of length @m@)
            -> Vector v n Int -- ^ index vector (of length @n@)
            -> Vector v n b   -- ^ value vector (of length @n@)
            -> Vector v m a
accumulate_ f (Vector v) (Vector is) (Vector xs) = Vector (VG.accumulate_ f v is xs)
{-# inline accumulate_ #-}

-- | Same as 'accum' but without bounds checking.
unsafeAccum :: VG.Vector v a
            => (a -> b -> a) -- ^ accumulating function @f@
            -> Vector v m a  -- ^ initial vector (of length @m@)
            -> [(Int,b)]     -- ^ list of index/value pairs (of length @n@)
            -> Vector v m a
unsafeAccum f (Vector v) us = Vector (VG.unsafeAccum f v us)
{-# inline unsafeAccum #-}

-- | Same as 'accumulate' but without bounds checking.
unsafeAccumulate :: (VG.Vector v a, VG.Vector v (Int, b))
                 => (a -> b -> a)      -- ^ accumulating function @f@
                 -> Vector v m a       -- ^ initial vector (of length @m@)
                 -> Vector v n (Int,b) -- ^ vector of index/value pairs (of length @n@)
                 -> Vector v m a
unsafeAccumulate f (Vector v) (Vector us) = Vector (VG.unsafeAccumulate f v us)
{-# inline unsafeAccumulate #-}

-- | Same as 'accumulate_' but without bounds checking.
unsafeAccumulate_ :: (VG.Vector v a, VG.Vector v Int, VG.Vector v b)
            => (a -> b -> a)  -- ^ accumulating function @f@
            -> Vector v m a   -- ^ initial vector (of length @m@)
            -> Vector v n Int -- ^ index vector (of length @n@)
            -> Vector v n b   -- ^ value vector (of length @n@)
            -> Vector v m a
unsafeAccumulate_ f (Vector v) (Vector is) (Vector xs) = Vector (VG.unsafeAccumulate_ f v is xs)
{-# inline unsafeAccumulate_ #-}

--
-- ** Permutations
--

-- | /O(n)/ Reverse a vector
reverse :: (VG.Vector v a) => Vector v n a -> Vector v n a
reverse (Vector v) = Vector (VG.reverse v)
{-# inline reverse #-}

-- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
-- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
-- often much more efficient.
--
-- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
backpermute :: (VG.Vector v a, VG.Vector v Int)
            => Vector v m a   -- ^ @xs@ value vector
            -> Vector v n Int -- ^ @is@ index vector (of length @n@)
            -> Vector v n a
backpermute (Vector v) (Vector is) = Vector (VG.backpermute v is)
{-# inline backpermute #-}

-- | Same as 'backpermute' but without bounds checking.
unsafeBackpermute :: (VG.Vector v a, VG.Vector v Int)
                  => Vector v m a   -- ^ @xs@ value vector
                  -> Vector v n Int -- ^ @is@ index vector (of length @n@)
                  -> Vector v n a
unsafeBackpermute (Vector v) (Vector is) = Vector (VG.unsafeBackpermute v is)
{-# inline unsafeBackpermute #-}

--------------------------------------------------------------------------------
-- * Elementwise Operations
--------------------------------------------------------------------------------

--
-- ** Indexing
--

-- | /O(n)/ Pair each element in a vector with its index
indexed :: (VG.Vector v a, VG.Vector v (Int, a), VG.Vector v (Finite n,a))
        => Vector v n a -> Vector v n (Finite n,a)
indexed (Vector v) = Vector ((VG.map . first) (Finite . fromIntegral) $ VG.indexed v)
{-# inline indexed #-}

--
-- ** Mapping
--

-- | /O(n)/ Map a function over a vector
map :: (VG.Vector v a, VG.Vector v b)
    => (a -> b) -> Vector v n a -> Vector v n b
map f (Vector v) = Vector (VG.map f v)
{-# inline map #-}

-- | /O(n)/ Apply a function to every element of a vector and its index
imap :: (VG.Vector v a, VG.Vector v b)
     => (Finite n -> a -> b) -> Vector v n a -> Vector v n b
imap f (Vector v) = Vector (VG.imap (f . Finite . fromIntegral) v)
{-# inline imap #-}

-- | /O(n*m)/ Map a function over a vector and concatenate the results. The
-- function is required to always return the same length vector.
concatMap :: (VG.Vector v a, VG.Vector v b)
          => (a -> Vector v m b) -> Vector v n a -> Vector v (n*m) b
concatMap f (Vector v) = Vector (VG.concatMap (fromSized . f) v)
{-# inline concatMap #-}

--
-- ** Monadic mapping
--

-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
-- vector of results
mapM :: (Monad m, VG.Vector v a, VG.Vector v b)
      => (a -> m b) -> Vector v n a -> m (Vector v n b)
mapM f (Vector v) = Vector <$> VG.mapM f v
{-# inline mapM #-}

-- | /O(n)/ Apply the monadic action to every element of a vector and its
-- index, yielding a vector of results
imapM :: (Monad m, VG.Vector v a, VG.Vector v b)
      => (Finite n -> a -> m b) -> Vector v n a -> m (Vector v n b)
imapM f (Vector v) = Vector <$> (VG.imapM (f . Finite . fromIntegral) v)
{-# inline imapM #-}

-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
-- results
mapM_ :: (Monad m, VG.Vector v a) => (a -> m b) -> Vector v n a -> m ()
mapM_ f (Vector v) = VG.mapM_ f v
{-# inline mapM_ #-}

-- | /O(n)/ Apply the monadic action to every element of a vector and its
-- index, ignoring the results
imapM_ :: (Monad m, VG.Vector v a) => (Finite n -> a -> m b) -> Vector v n a -> m ()
imapM_ f (Vector v) = VG.imapM_ (f . Finite . fromIntegral) v
{-# inline imapM_ #-}

-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
-- vector of results. Equvalent to @flip 'mapM'@.
forM :: (Monad m, VG.Vector v a, VG.Vector v b)
     => Vector v n a -> (a -> m b) -> m (Vector v n b)
forM (Vector v) f = Vector <$> VG.forM v f
{-# inline forM #-}

-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
-- results. Equivalent to @flip 'mapM_'@.
forM_ :: (Monad m, VG.Vector v a) => Vector v n a -> (a -> m b) -> m ()
forM_ (Vector v) = VG.forM_ v
{-# inline forM_ #-}

--
-- ** Zipping
--

-- | /O(n)/ Zip two vectors of the same length with the given function.
zipWith :: (VG.Vector v a, VG.Vector v b, VG.Vector v c)
        => (a -> b -> c) -> Vector v n a -> Vector v n b -> Vector v n c
zipWith f (Vector as) (Vector bs) = Vector (VG.zipWith f as bs)
{-# inline zipWith #-}

-- | Zip three vectors with the given function.
zipWith3 :: (VG.Vector v a, VG.Vector v b, VG.Vector v c, VG.Vector v d)
         => (a -> b -> c -> d) -> Vector v n a -> Vector v n b -> Vector v n c -> Vector v n d
zipWith3 f (Vector as) (Vector bs) (Vector cs) = Vector (VG.zipWith3 f as bs cs)
{-# inline zipWith3 #-}

zipWith4 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e)
         => (a -> b -> c -> d -> e)
         -> Vector v n a
         -> Vector v n b
         -> Vector v n c
         -> Vector v n d
         -> Vector v n e
zipWith4 f (Vector as) (Vector bs) (Vector cs) (Vector ds)
  = Vector (VG.zipWith4 f as bs cs ds)
{-# inline zipWith4 #-}

zipWith5 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e,VG.Vector v f)
         => (a -> b -> c -> d -> e -> f)
         -> Vector v n a
         -> Vector v n b
         -> Vector v n c
         -> Vector v n d
         -> Vector v n e
         -> Vector v n f
zipWith5 f (Vector as) (Vector bs) (Vector cs) (Vector ds) (Vector es)
  = Vector (VG.zipWith5 f as bs cs ds es)
{-# inline zipWith5 #-}

zipWith6 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e,VG.Vector v f,VG.Vector v g)
         => (a -> b -> c -> d -> e -> f -> g)
         -> Vector v n a
         -> Vector v n b
         -> Vector v n c
         -> Vector v n d
         -> Vector v n e
         -> Vector v n f
         -> Vector v n g
zipWith6 f (Vector as) (Vector bs) (Vector cs) (Vector ds) (Vector es) (Vector fs)
  = Vector (VG.zipWith6 f as bs cs ds es fs)
{-# inline zipWith6 #-}

-- | /O(n)/ Zip two vectors of the same length with a function that also takes
-- the elements' indices).
izipWith :: (VG.Vector v a,VG.Vector v b,VG.Vector v c)
         => (Finite n -> a -> b -> c)
         -> Vector v n a
         -> Vector v n b
         -> Vector v n c
izipWith f (Vector xs) (Vector ys)
  = Vector (VG.izipWith (f . Finite . fromIntegral) xs ys)
{-# inline izipWith #-}

izipWith3 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d)
          => (Finite n -> a -> b -> c -> d)
          -> Vector v n a
          -> Vector v n b
          -> Vector v n c
          -> Vector v n d
izipWith3 f (Vector as) (Vector bs) (Vector cs)
  = Vector (VG.izipWith3 (f . Finite . fromIntegral) as bs cs)
{-# inline izipWith3 #-}

izipWith4 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e)
          => (Finite n -> a -> b -> c -> d -> e)
          -> Vector v n a
          -> Vector v n b
          -> Vector v n c
          -> Vector v n d
          -> Vector v n e
izipWith4 f (Vector as) (Vector bs) (Vector cs) (Vector ds)
  = Vector (VG.izipWith4 (f . Finite . fromIntegral) as bs cs ds)
{-# inline izipWith4 #-}

izipWith5 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e,VG.Vector v f)
          => (Finite n -> a -> b -> c -> d -> e -> f)
          -> Vector v n a
          -> Vector v n b
          -> Vector v n c
          -> Vector v n d
          -> Vector v n e
          -> Vector v n f
izipWith5 f (Vector as) (Vector bs) (Vector cs) (Vector ds) (Vector es)
  = Vector (VG.izipWith5 (f . Finite . fromIntegral) as bs cs ds es)
{-# inline izipWith5 #-}

izipWith6 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e,VG.Vector v f,VG.Vector v g)
          => (Finite n -> a -> b -> c -> d -> e -> f -> g)
          -> Vector v n a
          -> Vector v n b
          -> Vector v n c
          -> Vector v n d
          -> Vector v n e
          -> Vector v n f
          -> Vector v n g
izipWith6 f (Vector as) (Vector bs) (Vector cs) (Vector ds) (Vector es) (Vector fs)
  = Vector (VG.izipWith6 (f . Finite . fromIntegral) as bs cs ds es fs)
{-# inline izipWith6 #-}

-- | /O(n)/ Zip two vectors of the same length
zip :: (VG.Vector v a, VG.Vector v b, VG.Vector v (a,b))
    => Vector v n a -> Vector v n b -> Vector v n (a, b)
zip = zipWith (,)
{-# inline zip #-}

zip3 :: (VG.Vector v a, VG.Vector v b, VG.Vector v c, VG.Vector v (a, b, c))
     => Vector v n a -> Vector v n b -> Vector v n c -> Vector v n (a, b, c)
zip3 = zipWith3 (,,)
{-# inline zip3 #-}

zip4 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v (a,b,c,d))
     => Vector v n a
     -> Vector v n b
     -> Vector v n c
     -> Vector v n d
     -> Vector v n (a,b,c,d)
zip4 = zipWith4 (,,,)
{-# inline zip4 #-}

zip5 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e,VG.Vector v (a,b,c,d,e))
     => Vector v n a
     -> Vector v n b
     -> Vector v n c
     -> Vector v n d
     -> Vector v n e
     -> Vector v n (a,b,c,d,e)
zip5 = zipWith5 (,,,,)
{-# inline zip5 #-}

zip6 :: (VG.Vector v a,VG.Vector v b,VG.Vector v c,VG.Vector v d,VG.Vector v e,VG.Vector v f,VG.Vector v (a,b,c,d,e,f))
     => Vector v n a
     -> Vector v n b
     -> Vector v n c
     -> Vector v n d
     -> Vector v n e
     -> Vector v n f
     -> Vector v n (a,b,c,d,e,f)
zip6 = zipWith6 (,,,,,)
{-# inline zip6 #-}

--
-- ** Monadic zipping
--

-- | /O(n)/ Zip the two vectors of the same length with the monadic action and
-- yield a vector of results
zipWithM :: (Monad m, VG.Vector v a, VG.Vector v b, VG.Vector v c)
         => (a -> b -> m c) -> Vector v n a -> Vector v n b -> m (Vector v n c)
zipWithM f (Vector as) (Vector bs) = Vector <$> VG.zipWithM f as bs
{-# inline zipWithM #-}

-- | /O(n)/ Zip the two vectors with a monadic action that also takes the
-- element index and yield a vector of results
izipWithM :: (Monad m, VG.Vector v a, VG.Vector v b, VG.Vector v c)
         => (Finite n -> a -> b -> m c) -> Vector v n a -> Vector v n b -> m (Vector v n c)
izipWithM m (Vector as) (Vector bs) = Vector <$> VG.izipWithM (m . Finite . fromIntegral) as bs
{-# inline izipWithM #-}

-- | /O(n)/ Zip the two vectors with the monadic action and ignore the results
zipWithM_ :: (Monad m, VG.Vector v a, VG.Vector v b)
          => (a -> b -> m c) -> Vector v n a -> Vector v n b -> m ()
zipWithM_ f (Vector as) (Vector bs) = VG.zipWithM_ f as bs
{-# inline zipWithM_ #-}

-- | /O(n)/ Zip the two vectors with a monadic action that also takes
-- the element index and ignore the results
izipWithM_ :: (Monad m, VG.Vector v a, VG.Vector v b)
           => (Finite n -> a -> b -> m c) -> Vector v n a -> Vector v n b -> m ()
izipWithM_ m (Vector as) (Vector bs) = VG.izipWithM_ (m . Finite . fromIntegral) as bs
{-# inline izipWithM_ #-}

-- Unzipping
-- ---------

-- | /O(min(m,n))/ Unzip a vector of pairs.
unzip :: (VG.Vector v a, VG.Vector v b, VG.Vector v (a,b))
      => Vector v n (a, b) -> (Vector v n a, Vector v n b)
unzip xs = (map fst xs, map snd xs)
{-# inline unzip #-}

unzip3 :: (VG.Vector v a, VG.Vector v b, VG.Vector v c, VG.Vector v (a, b, c))
       => Vector v n (a, b, c) -> (Vector v n a, Vector v n b, Vector v n c)
unzip3 xs = (map (\(a, _, _) -> a) xs,
             map (\(_, b, _) -> b) xs,
             map (\(_, _, c) -> c) xs)
{-# inline unzip3 #-}

unzip4 :: (VG.Vector v a, VG.Vector v b, VG.Vector v c, VG.Vector v d,
           VG.Vector v (a, b, c, d))
       => Vector v n (a, b, c, d) -> (Vector v n a, Vector v n b, Vector v n c, Vector v n d)
unzip4 xs = (map (\(a, _, _, _) -> a) xs,
             map (\(_, b, _, _) -> b) xs,
             map (\(_, _, c, _) -> c) xs,
             map (\(_, _, _, d) -> d) xs)
{-# inline unzip4 #-}

unzip5 :: (VG.Vector v a, VG.Vector v b, VG.Vector v c, VG.Vector v d, VG.Vector v e,
           VG.Vector v (a, b, c, d, e))
       => Vector v n (a, b, c, d, e) -> (Vector v n a, Vector v n b, Vector v n c, Vector v n d, Vector v n e)
unzip5 xs = (map (\(a, _, _, _, _) -> a) xs,
             map (\(_, b, _, _, _) -> b) xs,
             map (\(_, _, c, _, _) -> c) xs,
             map (\(_, _, _, d, _) -> d) xs,
             map (\(_, _, _, _, e) -> e) xs)
{-# inline unzip5 #-}

unzip6 :: (VG.Vector v a, VG.Vector v b, VG.Vector v c, VG.Vector v d, VG.Vector v e,
           VG.Vector v f, VG.Vector v (a, b, c, d, e, f))
       => Vector v n (a, b, c, d, e, f) -> (Vector v n a, Vector v n b, Vector v n c, Vector v n d, Vector v n e, Vector v n f)
unzip6 xs = (map (\(a, _, _, _, _, _) -> a) xs,
             map (\(_, b, _, _, _, _) -> b) xs,
             map (\(_, _, c, _, _, _) -> c) xs,
             map (\(_, _, _, d, _, _) -> d) xs,
             map (\(_, _, _, _, e, _) -> e) xs,
             map (\(_, _, _, _, _, f) -> f) xs)
{-# inline unzip6 #-}

--------------------------------------------------------------------------------
-- * Working with predicates
--------------------------------------------------------------------------------

--
-- ** Searching
--


infix 4 `elem`
-- | /O(n)/ Check if the vector contains an element
elem :: (VG.Vector v a, Eq a) => a -> Vector v n a -> Bool
elem x (Vector v) = VG.elem x v
{-# inline elem #-}

infix 4 `notElem`
-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
notElem :: (VG.Vector v a, Eq a) => a -> Vector v n a -> Bool
notElem x (Vector v) = VG.notElem x v
{-# inline notElem #-}

-- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
-- if no such element exists.
find :: VG.Vector v a => (a -> Bool) -> Vector v n a -> Maybe a
find f (Vector v) = VG.find f v
{-# inline find #-}

-- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
-- or 'Nothing' if no such element exists.
findIndex :: VG.Vector v a => (a -> Bool) -> Vector v n a -> Maybe (Finite n)
findIndex f (Vector v) = Finite . fromIntegral <$> VG.findIndex f v
{-# inline findIndex #-}

-- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
-- 'Nothing' if the vector does not contain the element. This is a specialised
-- version of 'findIndex'.
elemIndex :: (VG.Vector v a, Eq a) => a -> Vector v n a -> Maybe (Finite n)
elemIndex x (Vector v) = Finite . fromIntegral <$> VG.elemIndex x v
{-# inline elemIndex #-}

--------------------------------------------------------------------------------
-- * Folding
--------------------------------------------------------------------------------

-- | /O(n)/ Left fold
foldl :: VG.Vector v b => (a -> b -> a) -> a -> Vector v n b -> a
foldl f z = VG.foldl f z . fromSized
{-# inline foldl #-}

-- | /O(n)/ Left fold on non-empty vectors
foldl1 :: VG.Vector v a => (a -> a -> a) -> Vector v (1+n) a -> a
foldl1 f = VG.foldl1 f . fromSized
{-# inline foldl1 #-}

-- | /O(n)/ Left fold with strict accumulator
foldl' :: VG.Vector v b => (a -> b -> a) -> a -> Vector v n b -> a
foldl' f z = VG.foldl' f z . fromSized
{-# inline foldl' #-}

-- | /O(n)/ Left fold on non-empty vectors with strict accumulator
foldl1' :: VG.Vector v a => (a -> a -> a) -> Vector v (1+n) a -> a
foldl1' f = VG.foldl1' f . fromSized
{-# inline foldl1' #-}

-- | /O(n)/ Right fold
foldr :: VG.Vector v a => (a -> b -> b) -> b -> Vector v n a -> b
foldr f z = VG.foldr f z . fromSized
{-# inline foldr #-}

-- | /O(n)/ Right fold on non-empty vectors
foldr1 :: VG.Vector v a => (a -> a -> a) -> Vector v (n+1) a -> a
foldr1 f = VG.foldr1 f . fromSized
{-# inline foldr1 #-}

-- | /O(n)/ Right fold with a strict accumulator
foldr' :: VG.Vector v a => (a -> b -> b) -> b -> Vector v n a -> b
foldr' f z = VG.foldr' f z . fromSized
{-# inline foldr' #-}

-- | /O(n)/ Right fold on non-empty vectors with strict accumulator
foldr1' :: VG.Vector v a => (a -> a -> a) -> Vector v (n+1) a -> a
foldr1' f = VG.foldr1' f . fromSized
{-# inline foldr1' #-}

-- | /O(n)/ Left fold (function applied to each element and its index)
ifoldl :: VG.Vector v b => (a -> Finite n -> b -> a) -> a -> Vector v n b -> a
ifoldl f z = VG.ifoldl (\x -> f x . Finite . fromIntegral) z . fromSized
{-# inline ifoldl #-}

-- | /O(n)/ Left fold with strict accumulator (function applied to each element
-- and its index)
ifoldl' :: VG.Vector v b => (a -> Finite n -> b -> a) -> a -> Vector v n b -> a
ifoldl' f z = VG.ifoldl' (\x -> f x . Finite . fromIntegral) z . fromSized
{-# inline ifoldl' #-}

-- | /O(n)/ Right fold (function applied to each element and its index)
ifoldr :: VG.Vector v a => (Finite n -> a -> b -> b) -> b -> Vector v n a -> b
ifoldr f z = VG.ifoldr (f . Finite . fromIntegral) z . fromSized
{-# inline ifoldr #-}

-- | /O(n)/ Right fold with strict accumulator (function applied to each
-- element and its index)
ifoldr' :: VG.Vector v a => (Finite n -> a -> b -> b) -> b -> Vector v n a -> b
ifoldr' f z = VG.ifoldr' (f . Finite . fromIntegral) z . fromSized
{-# inline ifoldr' #-}

-- ** Specialised folds

-- | /O(n)/ Check if all elements satisfy the predicate.
all :: VG.Vector v a => (a -> Bool) -> Vector v n a -> Bool
all f = VG.all f . fromSized
{-# inline all #-}

-- | /O(n)/ Check if any element satisfies the predicate.
any :: VG.Vector v a => (a -> Bool) -> Vector v n a -> Bool
any f = VG.any f . fromSized
{-# inline any #-}

-- | /O(n)/ Check if all elements are 'True'
and :: VG.Vector v Bool => Vector v n Bool -> Bool
and = VG.and . fromSized
{-# inline and #-}

-- | /O(n)/ Check if any element is 'True'
or :: VG.Vector v Bool => Vector v n Bool -> Bool
or = VG.or . fromSized
{-# inline or #-}

-- | /O(n)/ Compute the sum of the elements
sum :: (VG.Vector v a, Num a) => Vector v n a -> a
sum = VG.sum . fromSized
{-# inline sum #-}

-- | /O(n)/ Compute the produce of the elements
product :: (VG.Vector v a, Num a) => Vector v n a -> a
product = VG.product . fromSized
{-# inline product #-}

-- | /O(n)/ Yield the maximum element of the non-empty vector.
maximum :: (VG.Vector v a, Ord a) => Vector v (n+1) a -> a
maximum = VG.maximum . fromSized
{-# inline maximum #-}

-- | /O(n)/ Yield the maximum element of the non-empty vector according to the
-- given comparison function.
maximumBy :: VG.Vector v a
          => (a -> a -> Ordering) -> Vector v (n+1) a -> a
maximumBy cmpr = VG.maximumBy cmpr . fromSized
{-# inline maximumBy #-}

-- | /O(n)/ Yield the minimum element of the non-empty vector.
minimum :: (VG.Vector v a, Ord a) => Vector v (n+1) a -> a
minimum = VG.minimum . fromSized
{-# inline minimum #-}

-- | /O(n)/ Yield the minimum element of the non-empty vector according to the
-- given comparison function.
minimumBy :: VG.Vector v a
          => (a -> a -> Ordering) -> Vector v (n+1) a -> a
minimumBy cmpr = VG.minimumBy cmpr . fromSized
{-# inline minimumBy #-}

-- | /O(n)/ Yield the index of the maximum element of the non-empty vector.
maxIndex :: (VG.Vector v a, Ord a) => Vector v (n+1) a -> Finite (n+1)
maxIndex = Finite . fromIntegral . VG.maxIndex . fromSized
{-# inline maxIndex #-}

-- | /O(n)/ Yield the index of the maximum element of the non-empty vector
-- according to the given comparison function.
maxIndexBy :: VG.Vector v a
           => (a -> a -> Ordering) -> Vector v (n+1) a -> Finite (n + 1)
maxIndexBy cmpr = Finite . fromIntegral . VG.maxIndexBy cmpr . fromSized
{-# inline maxIndexBy #-}

-- | /O(n)/ Yield the index of the minimum element of the non-empty vector.
minIndex :: (VG.Vector v a, Ord a) => Vector v (n+1) a -> Finite (n+1)
minIndex = Finite . fromIntegral . VG.minIndex . fromSized
{-# inline minIndex #-}

-- | /O(n)/ Yield the index of the minimum element of the non-empty vector
-- according to the given comparison function.
minIndexBy :: VG.Vector v a
           => (a -> a -> Ordering) -> Vector v (n+1) a -> Finite (n + 1)
minIndexBy cmpr = Finite . fromIntegral . VG.minIndexBy cmpr . fromSized
{-# inline minIndexBy #-}

-- ** Monadic folds

-- | /O(n)/ Monadic fold
foldM :: (Monad m, VG.Vector v b) => (a -> b -> m a) -> a -> Vector v n b -> m a
foldM m z = VG.foldM m z . fromSized
{-# inline foldM #-}

-- | /O(n)/ Monadic fold (action applied to each element and its index)
ifoldM :: (Monad m, VG.Vector v b) => (a -> Finite n -> b -> m a) -> a -> Vector v n b -> m a
ifoldM m z = VG.ifoldM (\x -> m x . Finite . fromIntegral) z . fromSized
{-# inline ifoldM #-}

-- | /O(n)/ Monadic fold over non-empty vectors
fold1M :: (Monad m, VG.Vector v a)
       => (a -> a -> m a) -> Vector v (1+n) a -> m a
fold1M m = VG.fold1M m . fromSized
{-# inline fold1M #-}

-- | /O(n)/ Monadic fold with strict accumulator
foldM' :: (Monad m, VG.Vector v b) => (a -> b -> m a) -> a -> Vector v n b -> m a
foldM' m z = VG.foldM' m z . fromSized
{-# inline foldM' #-}

-- | /O(n)/ Monadic fold with strict accumulator (action applied to each
-- element and its index)
ifoldM' :: (Monad m, VG.Vector v b)
        => (a -> Finite n -> b -> m a) -> a -> Vector v n b -> m a
ifoldM' m z = VG.ifoldM' (\x -> m x . Finite . fromIntegral) z . fromSized
{-# inline ifoldM' #-}

-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
fold1M' :: (Monad m, VG.Vector v a)
        => (a -> a -> m a) -> Vector v (n+1) a -> m a
fold1M' m = VG.fold1M' m . fromSized
{-# inline fold1M' #-}

-- | /O(n)/ Monadic fold that discards the result
foldM_ :: (Monad m, VG.Vector v b)
       => (a -> b -> m a) -> a -> Vector v n b -> m ()
foldM_ m z = VG.foldM_ m z . fromSized
{-# inline foldM_ #-}

-- | /O(n)/ Monadic fold that discards the result (action applied to
-- each element and its index)
ifoldM_ :: (Monad m, VG.Vector v b)
        => (a -> Finite n -> b -> m a) -> a -> Vector v n b -> m ()
ifoldM_ m z = VG.ifoldM_ (\x -> m x . Finite . fromIntegral)  z . fromSized
{-# inline ifoldM_ #-}

-- | /O(n)/ Monadic fold over non-empty vectors that discards the result
fold1M_ :: (Monad m, VG.Vector v a)
        => (a -> a -> m a) -> Vector v (n+1) a -> m ()
fold1M_ m = VG.fold1M_ m . fromSized
{-# inline fold1M_ #-}

-- | /O(n)/ Monadic fold with strict accumulator that discards the result
foldM'_ :: (Monad m, VG.Vector v b)
        => (a -> b -> m a) -> a -> Vector v n b -> m ()
foldM'_ m z = VG.foldM'_ m z . fromSized
{-# inline foldM'_ #-}

-- | /O(n)/ Monadic fold with strict accumulator that discards the result
-- (action applied to each element and its index)
ifoldM'_ :: (Monad m, VG.Vector v b)
         => (a -> Finite n -> b -> m a) -> a -> Vector v n b -> m ()
ifoldM'_ m z = VG.ifoldM'_ (\x -> m x . Finite . fromIntegral) z . fromSized
{-# inline ifoldM'_ #-}

-- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
-- that discards the result
fold1M'_ :: (Monad m, VG.Vector v a)
         => (a -> a -> m a) -> Vector v (n+1) a -> m ()
fold1M'_ m = VG.fold1M'_ m . fromSized
{-# inline fold1M'_ #-}

-- ** Monadic sequencing

-- | Evaluate each action and collect the results
sequence :: (Monad m, VG.Vector v a, VG.Vector v (m a))
         => Vector v n (m a) -> m (Vector v n a)
sequence (Vector v) = Vector <$> VG.sequence v
{-# inline sequence #-}

-- | Evaluate each action and discard the results
sequence_ :: (Monad m, VG.Vector v (m a)) => Vector v n (m a) -> m ()
sequence_ (Vector v) = VG.sequence_ v
{-# inline sequence_ #-}

--------------------------------------------------------------------------------
-- * Prefix sums (scans)
--------------------------------------------------------------------------------

-- | /O(n)/ Prescan
--
-- @
-- prescanl f z = 'init' . 'scanl' f z
-- @
--
-- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
--
prescanl :: (VG.Vector v a, VG.Vector v b) => (a -> b -> a) -> a -> Vector v n b -> Vector v n a
prescanl f z = withVectorUnsafe (VG.prescanl f z )
{-# inline prescanl #-}

-- | /O(n)/ Prescan with strict accumulator
prescanl' :: (VG.Vector v a, VG.Vector v b) => (a -> b -> a) -> a -> Vector v n b -> Vector v n a
prescanl' f z = withVectorUnsafe (VG.prescanl' f z )
{-# inline prescanl' #-}

-- | /O(n)/ Scan
postscanl :: (VG.Vector v a, VG.Vector v b) => (a -> b -> a) -> a -> Vector v n b -> Vector v n a
postscanl f z = withVectorUnsafe (VG.postscanl f z )
{-# inline postscanl #-}

-- | /O(n)/ Scan with strict accumulator
postscanl' :: (VG.Vector v a, VG.Vector v b) => (a -> b -> a) -> a -> Vector v n b -> Vector v n a
postscanl' f z = withVectorUnsafe (VG.postscanl' f z )
{-# inline postscanl' #-}

-- | /O(n)/ Haskell-style scan
scanl :: (VG.Vector v a, VG.Vector v b) => (a -> b -> a) -> a -> Vector v n b -> Vector v n a
scanl f z = withVectorUnsafe (VG.scanl f z )
{-# inline scanl #-}

-- | /O(n)/ Haskell-style scan with strict accumulator
scanl' :: (VG.Vector v a, VG.Vector v b) => (a -> b -> a) -> a -> Vector v n b -> Vector v n a
scanl' f z = withVectorUnsafe (VG.scanl' f z )
{-# inline scanl' #-}

-- | /O(n)/ Scan over a non-empty vector
scanl1 :: VG.Vector v a => (a -> a -> a) -> Vector v (n+1) a -> Vector v (n+1) a
scanl1 f = withVectorUnsafe (VG.scanl1 f )
{-# inline scanl1 #-}

-- | /O(n)/ Scan over a non-empty vector with a strict accumulator
scanl1' :: VG.Vector v a => (a -> a -> a) -> Vector v (n+1) a -> Vector v (n+1) a
scanl1' f = withVectorUnsafe (VG.scanl1' f )
{-# inline scanl1' #-}

-- | /O(n)/ Right-to-left prescan
prescanr :: (VG.Vector v a, VG.Vector v b) => (a -> b -> b) -> b -> Vector v n a -> Vector v n b
prescanr f z = withVectorUnsafe (VG.prescanr f z )
{-# inline prescanr #-}

-- | /O(n)/ Right-to-left prescan with strict accumulator
prescanr' :: (VG.Vector v a, VG.Vector v b) => (a -> b -> b) -> b -> Vector v n a -> Vector v n b
prescanr' f z = withVectorUnsafe (VG.prescanr' f z )
{-# inline prescanr' #-}

-- | /O(n)/ Right-to-left scan
postscanr :: (VG.Vector v a, VG.Vector v b) => (a -> b -> b) -> b -> Vector v n a -> Vector v n b
postscanr f z = withVectorUnsafe (VG.postscanr f z )
{-# inline postscanr #-}

-- | /O(n)/ Right-to-left scan with strict accumulator
postscanr' :: (VG.Vector v a, VG.Vector v b) => (a -> b -> b) -> b -> Vector v n a -> Vector v n b
postscanr' f z = withVectorUnsafe (VG.postscanr' f z )
{-# inline postscanr' #-}

-- | /O(n)/ Right-to-left Haskell-style scan
scanr :: (VG.Vector v a, VG.Vector v b) => (a -> b -> b) -> b -> Vector v n a -> Vector v n b
scanr f z = withVectorUnsafe (VG.scanr f z )
{-# inline scanr #-}

-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
scanr' :: (VG.Vector v a, VG.Vector v b) => (a -> b -> b) -> b -> Vector v n a -> Vector v n b
scanr' f z = withVectorUnsafe (VG.scanr' f z )
{-# inline scanr' #-}

-- | /O(n)/ Right-to-left scan over a non-empty vector
scanr1 :: VG.Vector v a => (a -> a -> a) -> Vector v (n+1) a -> Vector v (n+1) a
scanr1 f = withVectorUnsafe (VG.scanr1 f )
{-# inline scanr1 #-}

-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
-- accumulator
scanr1' :: VG.Vector v a => (a -> a -> a) -> Vector v (n+1) a -> Vector v (n+1) a
scanr1' f = withVectorUnsafe (VG.scanr1' f )
{-# inline scanr1' #-}


-- * Conversions

-- ** Lists

-- | /O(n)/ Convert a vector to a list
toList :: VG.Vector v a => Vector v n a -> [a]
toList = VG.toList . fromSized
{-# inline toList #-}

-- | /O(n)/ Convert a list to a vector
fromList :: (VG.Vector v a, KnownNat n) => [a] -> Maybe (Vector v n a)
fromList = toSized . VG.fromList
{-# inline fromList #-}

-- | /O(n)/ Convert the first @n@ elements of a list to a vector. The length of
-- the resultant vector is inferred from the type.
fromListN :: forall v n a. (VG.Vector v a, KnownNat n)
          => [a] -> Maybe (Vector v n a)
fromListN = toSized . VG.fromListN i
  where i = fromIntegral (natVal (Proxy :: Proxy n))
{-# inline fromListN #-}

-- | /O(n)/ Convert the first @n@ elements of a list to a vector. The length of
-- the resultant vector is given explicitly as a 'Proxy' argument.
fromListN' :: forall v n a p. (VG.Vector v a, KnownNat n)
           => p n -> [a] -> Maybe (Vector v n a)
fromListN' _ = fromListN
{-# inline fromListN' #-}

-- | /O(n)/ Takes a list and returns a continuation providing a vector with
-- a size parameter corresponding to the length of the list.
--
-- Essentially converts a list into a vector with the proper size
-- parameter, determined at runtime.
--
-- See 'withSized'
withSizedList :: forall v a r. VG.Vector v a
              => [a] -> (forall n. KnownNat n => Vector v n a -> r) -> r
withSizedList xs = withSized (VG.fromList xs)

-- ** Different Vector types

-- | /O(n)/ Convert different vector types
convert :: (VG.Vector v a, VG.Vector w a) => Vector v n a -> Vector w n a
convert = withVectorUnsafe VG.convert
{-# inline convert #-}

-- ** Mutable vectors

-- | /O(n)/ Yield an immutable copy of the mutable vector.
freeze :: (PrimMonad m, VG.Vector v a)
       => SVGM.MVector (VG.Mutable v) n (PrimState m) a
       -> m (Vector v n a)
freeze (MVector v) = Vector <$> VG.freeze v

-- | /O(1)/ Unsafely convert a mutable vector to an immutable one withouy
-- copying. The mutable vector may not be used after this operation.
unsafeFreeze :: (PrimMonad m, VG.Vector v a)
             => SVGM.MVector (VG.Mutable v) n (PrimState m) a
             -> m (Vector v n a)
unsafeFreeze (MVector v) = Vector <$> VG.unsafeFreeze v

-- | /O(n)/ Yield a mutable copy of the immutable vector.
thaw :: (PrimMonad m, VG.Vector v a)
     => Vector v n a
     -> m (SVGM.MVector (VG.Mutable v) n (PrimState m) a)
thaw (Vector v) = MVector <$> VG.thaw v

-- | /O(n)/ Unsafely convert an immutable vector to a mutable one without
-- copying. The immutable vector may not be used after this operation.
unsafeThaw :: (PrimMonad m, VG.Vector v a)
           => Vector v n a
           -> m (SVGM.MVector (VG.Mutable v) n (PrimState m) a)
unsafeThaw (Vector v) = MVector <$> VG.unsafeThaw v

-- | /O(n)/ Copy an immutable vector into a mutable one.
copy :: (PrimMonad m, VG.Vector v a)
     => SVGM.MVector (VG.Mutable v) n (PrimState m) a
     -> Vector v n a
     -> m ()
copy (MVector v) (Vector u) = VG.unsafeCopy v u

-- ** Unsized vectors

-- | Convert a 'Data.Vector.Generic.Vector' into a
-- 'Data.Vector.Generic.Sized.Vector' if it has the correct size, otherwise
-- return Nothing.
toSized :: forall v n a. (VG.Vector v a, KnownNat n)
        => v a -> Maybe (Vector v n a)
toSized v
  | n' == fromIntegral (VG.length v) = Just (Vector v)
  | otherwise                        = Nothing
  where n' = natVal (Proxy :: Proxy n)
{-# inline toSized #-}

-- | Takes a 'Data.Vector.Generic.Vector' and returns a continuation
-- providing a 'Data.Vector.Generic.Sized' with a size parameter @n@ that
-- is determined at runtime based on the length of the input vector.
--
-- Essentially converts a 'Data.Vector.Generic.Vector' into
-- a 'Data.Vector.Generic.Sized.Vector' with the correct size parameter
-- @n@.
withSized :: forall v a r. VG.Vector v a
          => v a
          -> (forall n. KnownNat n => Vector v n a -> r) -> r
withSized v f = case someNatVal (fromIntegral (VG.length v)) of
  Just (SomeNat (Proxy :: Proxy n)) -> f (Vector v :: Vector v n a)
  Nothing -> error "impossible: Vector has negative length"

fromSized :: Vector v n a -> v a
fromSized (Vector v) = v
{-# inline fromSized #-}

-- | Apply a function on unsized vectors to a sized vector. The function must
-- preserve the size of the vector, this is not checked.
withVectorUnsafe :: (v a -> w b) -> Vector v n a -> Vector w n b
withVectorUnsafe f (Vector v) = Vector (f v)
{-# inline withVectorUnsafe #-}

instance (VG.Vector v a, Num a, KnownNat n) => Num (Vector v n a) where
    (+)         = zipWith (+)
    (-)         = zipWith (-)
    (*)         = zipWith (*)
    negate      = map negate
    abs         = map abs
    signum      = map signum
    fromInteger = replicate . fromInteger

instance (VG.Vector v a, Fractional a, KnownNat n) => Fractional (Vector v n a) where
    (/)          = zipWith (/)
    recip        = map recip
    fromRational = replicate . fromRational

instance (VG.Vector v a, Floating a, KnownNat n) => Floating (Vector v n a) where
    pi      = replicate pi
    exp     = map exp
    log     = map log
    sqrt    = map sqrt
    (**)    = zipWith (**)
    logBase = zipWith logBase
    sin     = map sin
    cos     = map cos
    tan     = map tan
    asin    = map asin
    acos    = map acos
    atan    = map atan
    sinh    = map sinh
    cosh    = map cosh
    tanh    = map tanh
    asinh   = map asinh
    acosh   = map acosh
    atanh   = map atanh