fixed-vector-0.5.0.0: Data/Vector/Fixed.hs
{-# OPTIONS_GHC -fno-warn-orphans #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE DeriveDataTypeable #-}
-- |
-- Generic API for vectors with fixed length.
--
-- For encoding of vector size library uses Peano naturals defined in
-- the library. At come point in the future it would make sense to
-- switch to new GHC type level numerals.
module Data.Vector.Fixed (
-- * Vector type class
-- ** Vector size
Dim
, Z
, S
-- ** Synonyms for small numerals
, N1
, N2
, N3
, N4
, N5
, N6
-- ** Type class
, Vector(..)
, VectorN
, Arity
, Fun(..)
, length
-- * Constructors
-- $construction
-- ** Small dimensions
-- $smallDim
, mk1
, mk2
, mk3
, mk4
, mk5
-- ** Consing
, ContVec
, empty
, vector
, (<|)
-- ** Variadic function
, Make
, mkN
-- ** Functions
, replicate
, replicateM
, generate
, generateM
, unfoldr
, basis
-- * Modifying vectors
-- ** Transformations
, head
, tail
, cons
, snoc
, reverse
-- ** Indexing & lenses
, C.Index
, (!)
, index
, element
, elementTy
-- ** Comparison
, eq
, ord
-- ** Maps
, map
, mapM
, mapM_
, imap
, imapM
, imapM_
, sequence
, sequence_
, sequenceA
, traverse
-- * Folding
, foldl
, foldr
, foldl1
, fold
, foldMap
, ifoldl
, ifoldr
, foldM
, ifoldM
-- ** Special folds
, sum
, maximum
, minimum
, and
, or
, all
, any
-- * Zips
, zipWith
, zipWithM
, izipWith
, izipWithM
-- * Conversion
, convert
, toList
, fromList
, fromList'
, fromListM
, fromFoldable
-- * Data types
, VecList(..)
, Only(..)
-- ** Tuple synonyms
, Tuple2
, Tuple3
, Tuple4
, Tuple5
) where
import Control.Applicative (Applicative(..),(<$>))
import Data.Data (Typeable,Data)
import qualified Data.Foldable as F
import qualified Data.Traversable as T
import Data.Vector.Fixed.Cont (Vector(..),VectorN,Dim,length,ContVec,vector,
empty,S,Z,Arity,Fun(..),accum,apply,
N1,N2,N3,N4,N5,N6,vector)
import qualified Data.Vector.Fixed.Cont as C
import Data.Vector.Fixed.Internal
import qualified Prelude as P
import Prelude hiding ( replicate,map,zipWith,maximum,minimum,and,or,all,any
, foldl,foldr,foldl1,length,sum,reverse
, head,tail,mapM,mapM_,sequence,sequence_
)
-- $construction
--
-- There are several ways to construct fixed vectors except using
-- their constructor if it's available. For small ones it's possible
-- to use functions 'mk1', 'mk2', etc.
--
-- >>> mk3 'a' 'b' 'c' :: (Char,Char,Char)
-- ('a','b','c')
--
-- Another option is to create tuple and 'convert' it to desired
-- vector type. For example:
--
-- > v = convert (x,y,z)
--
-- It will work on if type of @v@ is know from elsewhere. Same trick
-- could be used to pattern match on the vector with opaque
-- representation using view patterns
--
-- > function :: Vec N3 Double -> ...
-- > function (convert -> (x,y,z)) = ...
--
-- Third way is to use variadic function 'mkN'. It works similarly to
-- 'Text.Printf.printf' except it produces result of type 'ContVec'
-- which should be converted to vector of desired type by 'vector':
--
-- >>> vector $ mkN 'a' 'b' 'c' :: (Char,Char,Char)
-- ('a','b','c')
--
-- Probably most generic way is to cons values to the @ContVec@ and
-- convert it vector of desired type using 'vector':
--
-- >>> vector $ 'a' <| 'b' <| 'c' <| empty :: (Char,Char,Char)
-- ('a','b','c')
-- $smallDim
--
-- Constructors for vectors with small dimensions.
--------------------------------------------------------------------------------
-- We are trying to be clever with indexing here. It's not possible to
-- write generic indexing function. For example it's necessary O(n)
-- for VecList. It's however possible to write O(1) indexing for some
-- vectors and we trying to use such functions where possible.
--
-- We try to use presumable more efficient basicIndex
--
-- 1. It should not interfere with deforestation. So we should
-- rewrite only when deforestation rule already fired.
-- (starting from phase 1).
--
-- 2. Creation of vector is costlier than generic indexing so we should
-- apply rule only when vector is created anyway
--
-- In order to avoid firing this rule on implementation of (!) it has
-- been necessary to move definition of all functions to internal module.
{-# RULES
"fixed-vector:index/basicIndex"[1] forall vv i.
runIndex i (C.cvec vv) = C.basicIndex vv i
#-}
-- | Vector based on the lists. Not very useful by itself but is
-- necessary for implementation.
data VecList n a where
Nil :: VecList Z a
Cons :: a -> VecList n a -> VecList (S n) a
deriving (Typeable)
-- Vector instance
type instance Dim (VecList n) = n
instance Arity n => Vector (VecList n) a where
construct = Fun $ accum
(\(T_List f) a -> T_List (f . Cons a))
(\(T_List f) -> f Nil)
(T_List id :: T_List a n n)
inspect v (Fun f) = apply step (Flip v) f
where
step :: Flip VecList a (S k) -> (a, Flip VecList a k)
step (Flip (Cons a xs)) = (a, Flip xs)
{-# INLINE construct #-}
{-# INLINE inspect #-}
instance Arity n => VectorN VecList n a
newtype Flip f a n = Flip (f n a)
newtype T_List a n k = T_List (VecList k a -> VecList n a)
-- Standard instances
instance (Show a, Arity n) => Show (VecList n a) where
show = show . foldr (:) []
instance (Eq a, Arity n) => Eq (VecList n a) where
(==) = eq
instance (Ord a, Arity n) => Ord (VecList n a) where
compare = ord
instance Arity n => Functor (VecList n) where
fmap = map
instance Arity n => Applicative (VecList n) where
pure = replicate
(<*>) = zipWith ($)
instance Arity n => F.Foldable (VecList n) where
foldr = foldr
instance Arity n => T.Traversable (VecList n) where
sequenceA = sequenceA
traverse = traverse
-- | Single-element tuple.
newtype Only a = Only a
deriving (Show,Eq,Ord,Typeable,Data)
instance Functor Only where
fmap f (Only a) = Only (f a)
instance F.Foldable Only where
foldr = foldr
instance T.Traversable Only where
sequenceA (Only f) = Only <$> f
traverse f (Only a) = Only <$> f a
type instance Dim Only = S Z
instance Vector Only a where
construct = Fun Only
inspect (Only a) (Fun f) = f a
{-# INLINE construct #-}
{-# INLINE inspect #-}
type Tuple2 a = (a,a)
type Tuple3 a = (a,a,a)
type Tuple4 a = (a,a,a,a)
type Tuple5 a = (a,a,a,a,a)