-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Fixed-length lists and low-dimensional linear algebra. -- -- Vectors are represented by lists with type-encoded lengths. The -- constructor is :., which acts like a cons both at the value -- and type levels, with () taking the place of nil. So -- x:.y:.z:.() is a 3d vector. The library provides a set of -- common list-like functions (map, fold, etc) for working with vectors. -- Built up from these functions are a small but useful set of linear -- algebra operations: matrix multiplication, determinants, solving -- linear systems, inverting matrices. @package Vec @version 1.0 -- | Type level naturals. Ni is a type, ni an undefined -- value of that type, for i <- [0..19] module Data.Vec.Nat data N0 data Succ a type N1 = Succ N0 type N2 = Succ N1 type N3 = Succ N2 type N4 = Succ N3 type N5 = Succ N4 type N6 = Succ N5 type N7 = Succ N6 type N8 = Succ N7 type N9 = Succ N8 type N10 = Succ N9 type N11 = Succ N10 type N12 = Succ N11 type N13 = Succ N12 type N14 = Succ N13 type N15 = Succ N14 type N16 = Succ N15 type N17 = Succ N16 type N18 = Succ N17 type N19 = Succ N18 n0 :: N0 n1 :: N1 n2 :: N2 n3 :: N3 n4 :: N4 n5 :: N5 n6 :: N6 n7 :: N7 n8 :: N8 n9 :: N9 n10 :: N10 n11 :: N11 n12 :: N12 n13 :: N13 n14 :: N14 n15 :: N15 n16 :: N16 n17 :: N17 n18 :: N18 n19 :: N19 -- | nat n yields the Int value of the type-level natural -- n. class Nat n nat :: Nat n => n -> Int class Pred x y | x -> y, y -> x instance [overlap ok] Pred (Succ n) p => Pred (Succ (Succ n)) (Succ p) instance [overlap ok] Pred (Succ N0) N0 instance [overlap ok] Nat a => Nat (Succ a) instance [overlap ok] Nat N0 module Data.Vec.Base -- | The vector constructor. (:.) for vectors is like (:) -- for lists, and () takes the place of []. (The list -- of instances here is not meant to be readable.) data (:.) a b (:.) :: !a -> !b -> :. a b class ShowVec v showVec :: ShowVec v => v -> String type Vec2 a = a :. (a :. ()) type Vec3 a = a :. (Vec2 a) type Vec4 a = a :. (Vec3 a) type Vec5 a = a :. (Vec4 a) type Vec6 a = a :. (Vec5 a) type Vec7 a = a :. (Vec6 a) type Vec8 a = a :. (Vec7 a) type Vec9 a = a :. (Vec8 a) type Vec10 a = a :. (Vec9 a) type Vec11 a = a :. (Vec10 a) type Vec12 a = a :. (Vec11 a) type Vec13 a = a :. (Vec12 a) type Vec14 a = a :. (Vec13 a) type Vec15 a = a :. (Vec14 a) type Vec16 a = a :. (Vec15 a) type Vec17 a = a :. (Vec16 a) type Vec18 a = a :. (Vec17 a) type Vec19 a = a :. (Vec18 a) -- | The type constraint Vec n a v infers the vector type -- v from the length n, a type-level natural, and -- underlying component type a. So x :: Vec N4 a v => -- v declares x to be a 4-vector of as. class Vec n a v | n a -> v, v -> n a mkVec :: Vec n a v => n -> a -> v -- | Make a uniform vector. The length is inferred. vec :: Vec n a v => a -> v -- | Build a vector from a list, or access vector elements using run-time -- indicies, numbered from 0. class VecList a v | v -> a fromList :: VecList a v => [a] -> v getElem :: VecList a v => Int -> v -> a setElem :: VecList a v => Int -> a -> v -> v -- | get or set a vector element, known at compile time. Use the Nat types -- to access vector components. For instance, get n0 gets the x -- component, set n2 44 sets the z component to 44. class Access n a v | v -> a get :: Access n a v => n -> v -> a set :: Access n a v => n -> a -> v -> v -- | The first element. class Head v a | v -> a head :: Head v a => v -> a -- | All but the first element. class Tail v v_ | v -> v_ tail :: Tail v v_ => v -> v_ -- | Apply a function over each element in a vector. Constraint Map a b -- u v states that u is a vector of as, v -- is a vector of bs with the same length as u, and the -- function is of type a -> b. class Map a b u v | u -> a, v -> b, b u -> v, a v -> u map :: Map a b u v => (a -> b) -> u -> v -- | Combine two vectors using a binary function. The length of the result -- is the min of the lengths of the arguments. The constraint ZipWith -- a b c u v w states that u is a vector of as, -- v is a vector of bs, w is a vector of -- cs, and the binary function is of type a -> b -> -- c. class ZipWith a b c u v w | u -> a, v -> b, w -> c, u v c -> w zipWith :: ZipWith a b c u v w => (a -> b -> c) -> u -> v -> w -- | Fold a function over a vector. class Fold v a | v -> a fold :: Fold v a => (a -> a -> a) -> v -> a foldl :: Fold v a => (b -> a -> b) -> b -> v -> b foldr :: Fold v a => (a -> b -> b) -> b -> v -> b -- | Reverse a vector reverse :: Reverse' () v v' => v -> v' -- | Reverse helper function : accumulates the reversed list in its first -- argument class Reverse' p v v' | p v -> v' reverse' :: Reverse' p v v' => p -> v -> v' -- | Append two vectors class Append v1 v2 v3 | v1 v2 -> v3, v1 v3 -> v2 append :: Append v1 v2 v3 => v1 -> v2 -> v3 -- | take n v constructs a vector from the first n -- elements of v. n is a type-level natural. For -- example take n3 v makes a 3-vector of the first three -- elements of v. class Take n v v' | n v -> v' take :: Take n v v' => n -> v -> v' -- | drop n v strips the first n elements from -- v. n is a type-level natural. For example drop -- n2 v drops the first two elements. class Drop n v v' | n v -> v' drop :: Drop n v v' => n -> v -> v' -- | Get the last element, usually significant for some reason -- (quaternions, homogenous coordinates, whatever) class Last v a | v -> a last :: Last v a => v -> a -- | snoc v a appends the element a to the end of v. class Snoc v a v' | v a -> v', v' -> v a snoc :: Snoc v a v' => v -> a -> v' -- | The length of a vector class Length v n | v -> n length :: Length v n => v -> Int -- | sum of vector elements sum :: (Fold v a, Num a) => v -> a -- | product of vector elements product :: (Fold v a, Num a) => v -> a -- | maximum vector element maximum :: (Fold v a, Ord a) => v -> a -- | minimum vector element minimum :: (Fold v a, Ord a) => v -> a toList :: Fold v a => v -> [a] type Mat22 a = Vec2 (Vec2 a) type Mat23 a = Vec2 (Vec3 a) type Mat24 a = Vec2 (Vec4 a) type Mat32 a = Vec3 (Vec2 a) type Mat33 a = Vec3 (Vec3 a) type Mat34 a = Vec3 (Vec4 a) type Mat35 a = Vec3 (Vec5 a) type Mat36 a = Vec3 (Vec6 a) type Mat42 a = Vec4 (Vec2 a) type Mat43 a = Vec4 (Vec3 a) type Mat44 a = Vec4 (Vec4 a) type Mat45 a = Vec4 (Vec5 a) type Mat46 a = Vec4 (Vec6 a) type Mat47 a = Vec4 (Vec7 a) type Mat48 a = Vec4 (Vec8 a) -- | convert a matrix to a list-of-lists matToLists :: (Fold v a, Fold m v) => m -> [[a]] -- | convert a matrix to a list in row-major order matToList :: (Fold v a, Fold m v) => m -> [a] -- | convert a list-of-lists into a matrix matFromLists :: (Vec j a v, Vec i v m, VecList a v, VecList v m) => [[a]] -> m -- | convert a list into a matrix. (row-major order) matFromList :: (Vec i v m, Vec j a v, Nat i, VecList a v, VecList v m) => [a] -> m sizeOf# :: Storable a => a -> Int# class VecArrayRW v vaRead# :: VecArrayRW v => MutableByteArray# s# -> Int# -> State# s# -> (# State# s#, v #) vaWrite# :: VecArrayRW v => MutableByteArray# s# -> Int# -> v -> State# s# -> State# s# vaIndex# :: VecArrayRW v => ByteArray# -> Int# -> v vaSizeOf# :: VecArrayRW v => v -> Int# vaLength# :: VecArrayRW v => v -> Int# init# :: VecArrayRW v => v instance [overlap ok] (Eq a, Eq b) => Eq (a :. b) instance [overlap ok] (Ord a, Ord b) => Ord (a :. b) instance [overlap ok] (Read a, Read b) => Read (a :. b) instance [overlap ok] VecArrayRW (a :. v) => IArray UArray (a :. v) instance [overlap ok] VecArrayRW (a :. v) => MArray (STUArray s) (a :. v) (ST s) instance [overlap ok] VecArrayRW (Word8 :. v) => VecArrayRW (Word8 :. (Word8 :. v)) instance [overlap ok] VecArrayRW (Word8 :. ()) instance [overlap ok] VecArrayRW (Float :. v) => VecArrayRW (Float :. (Float :. v)) instance [overlap ok] VecArrayRW (Float :. ()) instance [overlap ok] VecArrayRW (Double :. v) => VecArrayRW (Double :. (Double :. v)) instance [overlap ok] VecArrayRW (Double :. ()) instance [overlap ok] VecArrayRW (Int :. v) => VecArrayRW (Int :. (Int :. v)) instance [overlap ok] VecArrayRW (Int :. ()) instance [overlap ok] (Eq u, ShowVec u, Fractional a, Ord (a :. u), ZipWith a a a (a :. u) (a :. u) (a :. u), Map a a (a :. u) (a :. u), Vec (Succ l) a (a :. u), Show (a :. u)) => Fractional (a :. u) instance [overlap ok] (Eq u, ShowVec u, Num a, Map a a (a :. u) (a :. u), ZipWith a a a (a :. u) (a :. u) (a :. u), Vec (Succ l) a (a :. u)) => Num (a :. u) instance [overlap ok] (Vec (Succ (Succ n)) a (a :. (a :. v)), Storable a, Storable (a :. v)) => Storable (a :. (a :. v)) instance [overlap ok] Storable a => Storable (a :. ()) instance [overlap ok] Length v n => Length (a :. v) (Succ n) instance [overlap ok] Length () N0 instance [overlap ok] Snoc v a (a :. v) => Snoc (a :. v) a (a :. (a :. v)) instance [overlap ok] Snoc () a (a :. ()) instance [overlap ok] Last (a' :. v) a => Last (a :. (a' :. v)) a instance [overlap ok] Last (a :. ()) a instance [overlap ok] Drop n (a :. v) v' => Drop (Succ n) (a :. (a :. v)) v' instance [overlap ok] Drop N0 v v instance [overlap ok] Take n v v' => Take (Succ n) (a :. v) (a :. v') instance [overlap ok] Take N0 v () instance [overlap ok] Append (a' :. v1) v2 v3 => Append (a :. (a' :. v1)) v2 (a :. v3) instance [overlap ok] Append (a :. ()) v (a :. v) instance [overlap ok] Append () v v instance [overlap ok] Reverse' (a :. p) v v' => Reverse' p (a :. v) v' instance [overlap ok] Reverse' p () p instance [overlap ok] Fold (a' :. u) a => Fold (a :. (a' :. u)) a instance [overlap ok] Fold (a :. ()) a instance [overlap ok] ZipWith a b c (a' :. u) (b' :. v) (c' :. w) => ZipWith a b c (a :. (a' :. u)) (b :. (b' :. v)) (c :. (c' :. w)) instance [overlap ok] ZipWith a b c (a :. (a :. as)) (b :. ()) (c :. ()) instance [overlap ok] ZipWith a b c (a :. ()) (b :. (b :. bs)) (c :. ()) instance [overlap ok] ZipWith a b c (a :. ()) (b :. ()) (c :. ()) instance [overlap ok] Map a b (a' :. u) (b' :. v) => Map a b (a :. (a' :. u)) (b :. (b' :. v)) instance [overlap ok] Map a b (a :. ()) (b :. ()) instance [overlap ok] Tail (a :. as) as instance [overlap ok] Head (a :. as) a instance [overlap ok] Access n a v => Access (Succ n) a (a :. v) instance [overlap ok] Access N0 a (a :. v) instance [overlap ok] VecList a (a' :. v) => VecList a (a :. (a' :. v)) instance [overlap ok] VecList a (a :. ()) instance [overlap ok] Vec (Succ n) a (a' :. v) => Vec (Succ (Succ n)) a (a :. (a' :. v)) instance [overlap ok] Vec N1 a (a :. ()) instance [overlap ok] (Show a, ShowVec v) => ShowVec (a :. v) instance [overlap ok] ShowVec () instance [overlap ok] (Show a, ShowVec v) => Show (a :. v) module Data.Vec.LinAlg -- | dot / inner / scalar product dot :: (Num a, Num v, Fold v a) => v -> v -> a -- | vector norm, squared normSq :: (Num a, Num v, Fold v a) => v -> a -- | vector / L2 / Euclidean norm norm :: (Num v, Floating a, Fold v a) => v -> a -- | normalize v is a unit vector in the direction of v. -- v is assumed non-null. normalize :: (Floating a, Num v, Fold v a, Map a a v v) => v -> v -- | 3d cross product. cross :: Num a => Vec3 a -> Vec3 a -> Vec3 a -- | lift a point into homogenous coordinates homPoint :: (Snoc v a v', Num a) => v -> v' -- | point-at-infinity in homogenous coordinates homVec :: (Snoc v a v', Num a) => v -> v' -- | project a vector from homogenous coordinates. Last vector element is -- assumed non-zero. project :: (Reverse' () t1 v', Fractional t1, Vec a t t1, Reverse' () v (t :. t1)) => v -> v' -- | row vector * matrix multvm :: (Transpose m mt, Map v a mt v', Fold v a, Num a, Num v) => v -> m -> v' -- | matrix * column vector multmv :: (Map v a m v', Num v, Fold v a, Num a) => m -> v -> v' -- | matrix * matrix multmm :: (Map v v' m1 m3, Map v a b v', Transpose m2 b, Fold v a, Num v, Num a) => m1 -> m2 -> m3 -- | apply a translation to a projective transformation matrix translate :: (Transpose m mt, Reverse' () mt (v' :. t), Reverse' (v' :. ()) t v'1, Transpose v'1 m, Num v', Num a, Snoc v a v') => v -> m -> m -- | get the n-th column as a vector. n is a type-level -- natural. column :: (Transpose m mt, Access n v mt) => n -> m -> v -- | get the n-th row as a vector. n is a type-level -- natural. row :: Access n a v => n -> v -> a -- | matrix transposition class Transpose a b | a -> b, b -> a transpose :: Transpose a b => a -> b -- | scale v m multiplies the diagonal of matrix m by the -- vector s, component-wise. So scale 5 m multiplies -- the diagonal by 5, whereas scale 2:.1 m only scales the x -- component. scale :: (GetDiagonal' N0 () m r, Num r, Vec n a r, Vec n r m, SetDiagonal' N0 r m) => r -> m -> m -- | diagonal v is a square matrix with the vector v as the -- diagonal, and 0 elsewhere. diagonal :: (Vec n a v, Vec n v m, SetDiagonal v m, Num m) => v -> m -- | identity matrix (square) identity :: (Vec n a v, Vec n v m, Num v, Num m, SetDiagonal v m) => m -- | Determinant by minor expansion, i.e. Laplace's formula. Unfolds into a -- closed form expression. This should be the fastest way for 4x4 and -- smaller, but snd . gaussElim works too. det :: (Vec n a r, Vec n r m, Det' m a) => m -> a -- | cramer'sRule m v computes the solution to -- m`multmv`x=v using the eponymous method. For larger than 3x3 -- you will want to use solve, which uses gaussElim. -- Cramer's rule, however, unfolds into a closed-form expression, with no -- branches or allocations (other than the result). You may need to -- increase the unfolding threshold to see this. cramer'sRule :: (Map a a1 b1 v, Transpose w b1, ZipWith a2 b vv v m w, ReplConsec' a2 () b vv, Vec n b vv, Vec n a2 b, Fractional a1, Det' m a1, Det' a a1) => m -> v -> v -- | Gaussian elimination, adapted from Mirko Rahn: -- http://www.haskell.org/pipermail/glasgow-haskell-users/2007-May/012648.html -- -- This is more of a proof of concept. Using a foreign C function will -- run slightly faster, and compile much faster. But where is the fun in -- that? Set your unfolding threshold as high as possible. class GaussElim a m | m -> a gaussElim :: GaussElim a m => m -> (m, a) -- | invert m returns Just the inverse of m or -- Nothing if m is singular. invert :: (Num r, Num m, Vec n a r, Vec n r m, Append r r r', ZipWith r r r' m m m', Drop n r' r, Map r' r m' m, SetDiagonal r m, GaussElim a m', BackSubstitute m') => m -> Maybe m -- | inverse and determinant. If det = 0, inverted matrix is garbage. invertAndDet :: (Num a, Num r, Num m, Vec n a r, Vec n r m, Append r r r', ZipWith r r r' m m m', Drop n r' r, Map r' r m' m, SetDiagonal r m, GaussElim a m', BackSubstitute m') => m -> (m, a) -- | Solution of linear system by Gaussian elimination. Returns -- Nothing if no solution. solve :: (Num r, Num m, Vec n a r, Vec n r m, Snoc r a r', ZipWith r a r' m r m', Drop n r' (a :. ()), Map r' a m' r, GaussElim a m', BackSubstitute m') => m -> r -> Maybe r instance [overlap ok] (Map (a :. r) r ((a :. r) :. rs) rs_, Map r (a :. r) rs_ ((a :. r) :. rs), Fold aas (a, a :. r), ZipWith a a a (a :. r) (a :. r) (a :. r), Map a a (a :. r) (a :. r), ZipWith a (a :. r) (a, a :. r) r ((a :. r) :. rs) aas, Num a, BackSubstitute' rs_) => BackSubstitute' ((a :. r) :. ((a :. r) :. rs)) instance [overlap ok] BackSubstitute' ((a :. r) :. ()) instance [overlap ok] (Map (a :. r) r ((a :. r) :. rs) rs_, Map r (a :. r) rs_ ((a :. r) :. rs), Fold aas (a, a :. r), ZipWith a a a (a :. r) (a :. r) (a :. r), Map a a (a :. r) (a :. r), ZipWith a (a :. r) (a, a :. r) r ((a :. r) :. rs) aas, Num a, NearZero a, BackSubstitute rs_) => BackSubstitute ((a :. r) :. ((a :. r) :. rs)) instance [overlap ok] NearZero a => BackSubstitute ((a :. r) :. ()) instance [overlap ok] (Fractional a, Map (a :. r) r ((a :. r) :. rs) rs_, Map r (a :. r) rs_ ((a :. r) :. rs), Pivot a ((a :. r) :. ((a :. r) :. rs)), GaussElim a rs_) => GaussElim a ((a :. r) :. ((a :. r) :. rs)) instance [overlap ok] (Num a, Pivot a (r :. ())) => GaussElim a (r :. ()) instance [overlap ok] (Fractional a, NearZero a, Pivot1 a rs, Tail (a :. r) r, Map (a :. r) r ((a :. r) :. rs) (r :. rs'), Map r (a :. r) (r :. rs') ((a :. r) :. rs), Pivot1 a ((a :. r) :. rs), Pivot a (r :. rs')) => Pivot a ((a :. r) :. rs) instance [overlap ok] Pivot a (() :. v) instance [overlap ok] (Fractional a, NearZero a, Map a a (a :. r) (a :. r), ZipWith a a a (a :. r) (a :. r) (a :. r), Map (a :. r) (a :. r) ((a :. r) :. rs) ((a :. r) :. rs), Pivot1 a ((a :. r) :. rs)) => Pivot1 a ((a :. r) :. ((a :. r) :. rs)) instance [overlap ok] (Fractional a, NearZero a, Map a a (a :. r) (a :. r)) => Pivot1 a ((a :. (a :. r)) :. ()) instance [overlap ok] (Show a, Fractional a, NearZero a) => Pivot1 a ((a :. ()) :. ()) instance [overlap ok] Pivot1 a () instance [overlap ok] NearZero Rational instance [overlap ok] NearZero Double instance [overlap ok] NearZero Float instance [overlap ok] (Append p (a :. v) x, Append p (a :. ()) y, ReplConsec' a y v z) => ReplConsec' a p (a :. v) (x :. z) instance [overlap ok] ReplConsec' a p () () instance [overlap ok] (Vec n a v, Vec n v vv, ReplConsec' a () v vv) => ReplConsec a v vv instance [overlap ok] (Num a, NegateOdds v) => NegateEvens (a :. v) instance [overlap ok] (Num a, NegateEvens v) => NegateOdds (a :. v) instance [overlap ok] NegateEvens () instance [overlap ok] NegateOdds () instance [overlap ok] (Append p (a :. v) x, Append p (a :. ()) y, DropConsec' y (a :. v) z) => DropConsec' p (a :. (a :. v)) (x :. z) instance [overlap ok] DropConsec' p (a :. ()) (p :. ()) instance [overlap ok] (Vec n a v, Pred n n_, Vec n_ a v_, Vec n v_ vv, DropConsec' () v vv) => DropConsec v vv instance [overlap ok] ((a :. (a :. v)) ~ r, ((a :. (a :. v)) :. ((a :. (a :. v)) :. vs)) ~ m, ((a :. v) :. ((a :. v) :. vs_)) ~ m_, (((a :. v) :. vs_) :. (x :. y)) ~ mm, Map (a :. (a :. v)) (a :. v) m m_, DropConsec m_ mm, Det' ((a :. v) :. vs_) a, Map ((a :. v) :. vs_) a mm r, Map r a m r, NegateOdds r, Fold r a, Num r, Num a) => Det' ((a :. (a :. v)) :. ((a :. (a :. v)) :. vs)) a instance [overlap ok] Det' ((a :. ()) :. ()) a instance [overlap ok] (Access n a r, Append p (a :. ()) p', GetDiagonal' (Succ n) p' (r :. m) v) => GetDiagonal' n p (r :. (r :. m)) v instance [overlap ok] (Access n a r, Append p (a :. ()) (a :. p)) => GetDiagonal' n p (r :. ()) (a :. p) instance [overlap ok] (Vec n a v, Vec n v m, GetDiagonal' N0 () m v) => GetDiagonal m v instance [overlap ok] (SetDiagonal' (Succ n) v m, Access n a r) => SetDiagonal' n (a :. v) (r :. m) instance [overlap ok] SetDiagonal' n () m instance [overlap ok] (Vec n a v, Vec n r m, SetDiagonal' N0 v m) => SetDiagonal v m instance [overlap ok] (Head xss_h xss_hh, Map xss_h xss_hh (xss_h :. xss_t) xs', Tail xss_h xss_ht, Map xss_h xss_ht (xss_h :. xss_t) xss_, Transpose' (xs :. xss_) xss') => Transpose' ((x :. xs) :. (xss_h :. xss_t)) ((x :. xs') :. xss') instance [overlap ok] Transpose' ((x :. ()) :. ()) ((x :. ()) :. ()) instance [overlap ok] Transpose' vs vs' => Transpose' (() :. vs) vs' instance [overlap ok] Transpose' () () instance [overlap ok] (Vec (Succ n) s (s :. ra), Vec (Succ m) (s :. ra) ((s :. ra) :. a), Vec (Succ m) s (s :. rb), Vec (Succ n) (s :. rb) ((s :. rb) :. b), Transpose' ((s :. ra) :. a) ((s :. rb) :. b)) => Transpose ((s :. ra) :. a) ((s :. rb) :. b) instance [overlap ok] Transpose () () -- | Packed vectors : use these whenever possible. The polymorphic vector -- type is represented at run-time by a linked list of boxed values. -- Specialized, or packed types, store the vector components -- sequentially in memory, in a single boxed value. Definitions for -- vector operations, given in terms of polymorphic vectors, can be -- (almost) automatically propagated to packed types using the functions -- pack and unpack. The compiler can then specialize the -- definition to the packed type and produce efficient code. -- -- Packed vectors are related to their unpacked representations by way of -- an associated type. An instance of class PackedVec v -- declares that v has a packed representation, and the type of -- that is Packed v. The packed constructors are named -- VecNT where N is 2, 3 or 4 and T is -- I, F or D for Int, Float -- or Double. So the expression Vec3D x y z constructs -- a packed 3-vector of Doubles, the type of which is Packed (Vec3 -- Double). The constructor name is also a synonym for the packed -- type name, i.e., type Vec3D = Packed (Vec3 Double), so the -- packed type acts as if it had been declared data Vec3D = Vec3D x y -- z. -- -- Storable, Num, Fractional, Fold, -- Map, and ZipWith instances are provided for packed -- vectors, so some operations do not require pack/unpack. For example, -- dot does not require pack/unpack because it is defined -- in terms of zipWith and fold. However -- transpose, det, -- gaussElim and most others are recursive (i.e., defined -- in terms of the same operation on lower-dimensional vectors), and so -- you'll still need to use pack/unpack with these. This goes for -- multmm as well because it uses -- transpose. Some functions, like -- multmv, do not need their arguments to be unpacked, -- but the result is a polymorphic vector (:.), so you will need -- to pack it again. I admit that this is awkward, and I'm still looking -- for a better way. -- -- There are also instances for Access, Take, Drop, -- Last, Head, Tail and Snoc. These come in -- handy for things like quaternions and homogenous coordinates. module Data.Vec.Packed -- | PackedVec class : relates a vector type to its space-optimized -- representation. class PackedVec v where data family Packed v pack :: PackedVec v => v -> Packed v unpack :: PackedVec v => Packed v -> v type Vec2B = Packed (Vec2 Bool) type Vec3B = Packed (Vec3 Bool) type Vec4B = Packed (Vec4 Bool) type Vec2I = Packed (Vec2 Int) type Vec3I = Packed (Vec3 Int) type Vec4I = Packed (Vec4 Int) type Vec2F = Packed (Vec2 Float) type Vec3F = Packed (Vec3 Float) type Vec4F = Packed (Vec4 Float) type Vec2D = Packed (Vec2 Double) type Vec3D = Packed (Vec3 Double) type Vec4D = Packed (Vec4 Double) type Mat22D = Vec2 (Vec2D) type Mat23D = Vec2 (Vec3D) type Mat24D = Vec2 (Vec4D) type Mat33D = Vec3 (Vec3D) type Mat34D = Vec3 (Vec4D) type Mat44D = Vec4 (Vec4D) -- | Construct a semi-packed matrix, one whose rows are packed. packMat :: (Map row (Packed row) mat packedMat, PackedVec row) => mat -> packedMat unpackMat :: (Map (Packed row) row packedMat mat, PackedVec row) => packedMat -> mat instance [overlap ok] (VecArrayRW (a :. v), PackedVec (a :. v)) => IArray UArray (Packed (a :. v)) instance [overlap ok] (VecArrayRW (a :. v), PackedVec (a :. v)) => MArray (STUArray s) (Packed (a :. v)) (ST s) instance [overlap ok] (VecList a v, PackedVec v) => VecList a (Packed v) instance [overlap ok] (Access n a v, PackedVec v) => Access n a (Packed v) instance [overlap ok] (Drop n v v', PackedVec v, PackedVec v') => Drop n (Packed v) (Packed v') instance [overlap ok] (Take (Succ n) v v', PackedVec v, PackedVec v') => Take (Succ n) (Packed v) (Packed v') instance [overlap ok] (Reverse' () v v', PackedVec v, PackedVec v') => Reverse' () (Packed v) (Packed v') instance [overlap ok] (Snoc v a v', PackedVec v, PackedVec v') => Snoc (Packed v) a (Packed v') instance [overlap ok] (Last v l, PackedVec v) => Last (Packed v) l instance [overlap ok] (Tail v t, PackedVec v, PackedVec t) => Tail (Packed v) (Packed t) instance [overlap ok] (Head v h, PackedVec v) => Head (Packed v) h instance [overlap ok] (Length v n, PackedVec v) => Length (Packed v) n instance [overlap ok] (Storable v, PackedVec v) => Storable (Packed v) instance [overlap ok] (Fractional v, PackedVec v) => Fractional (Packed v) instance [overlap ok] (Num v, PackedVec v) => Num (Packed v) instance [overlap ok] (ZipWith a b c u v w, PackedVec u, PackedVec v, PackedVec w) => ZipWith a b c (Packed u) (Packed v) (Packed w) instance [overlap ok] (Fold v a, PackedVec v) => Fold (Packed v) a instance [overlap ok] (Map a b u v, PackedVec u, PackedVec v) => Map a b (Packed u) (Packed v) instance [overlap ok] (Show v, PackedVec v) => Show (Packed v) instance [overlap ok] (Ord v, PackedVec v) => Ord (Packed v) instance [overlap ok] (Eq v, PackedVec v) => Eq (Packed v) instance [overlap ok] PackedVec (Vec4 Double) instance [overlap ok] PackedVec (Vec3 Double) instance [overlap ok] PackedVec (Vec2 Double) instance [overlap ok] PackedVec (Vec4 Float) instance [overlap ok] PackedVec (Vec3 Float) instance [overlap ok] PackedVec (Vec2 Float) instance [overlap ok] PackedVec (Vec4 Int) instance [overlap ok] PackedVec (Vec3 Int) instance [overlap ok] PackedVec (Vec2 Int) instance [overlap ok] PackedVec (Vec4 Bool) instance [overlap ok] PackedVec (Vec3 Bool) instance [overlap ok] PackedVec (Vec2 Bool) -- | Vec : a library for fixed-length lists and low-dimensional linear -- algebra -- -- Scott E. Dillard sedillard@gmail.com -- -- The darcs repository is at -- http://graphics.cs.ucdavis.edu/~sdillard/Vec -- -- Some examples can be found at -- http://graphics.cs.ucdavis.edu/~sdillard/Vec/examples -- -- Synopsis -- -- Vectors are represented by lists with type-encoded lengths. The -- constructor is :., which acts like a cons both at the value -- and type levels, with () taking the place of nil. So -- x:.y:.z:.() is a 3d vector. The library provides a set of -- common list-like functions (map, fold, etc) for working with vectors. -- Built up from these functions are a small but useful set of linear -- algebra operations: matrix multiplication, determinants, solving -- linear systems, inverting matrices. -- -- Design -- -- -- -- To the point of simplicity, vectors and matrices are instances of Num -- and Fractional. All arithmetic is done component-wise and literals -- construct uniform vectors and matrices. There are many interesting -- projects aiming to overhaul Haskell's number classes, but for now the -- type of (*) is a -> a -> a so that's what -- we're working with. It is easy to incorporate this library into a more -- mathematically consistent class hierarchy (provided you can design -- one.) -- -- The rule is simple : If the method is unary, it's a map. If it's -- binary, it's a zipWith. -- -- Performance -- -- (:.) is strict in both arguments, but it is also polymorphic, -- so at runtime vectors will be realized as linked lists, albeit with -- less pattern matching. However the library provides packed -- representations for 2,3 and 4d vectors of Ints, Floats and Doubles. -- Vec3F x y z constructs a packed vector of unboxed -- Floats. Functions pack and unpack -- convert between packed and unpacked types. When vector operations are -- bracketed by pack and unpack, GHC can unfold them into -- very efficient code. The Storable and UArray -- instances for vectors also store them efficiently and generate fast -- code. Without optimizations, the code falls back into linked-list -- mode. The optimizations depend on inlining, so you may need to -- increase your unfolding threshold in certain situations. -- -- GHC Extensions -- -- This library makes heavy use of functional dependencies. I have tried -- to tweak things so that they "just work." However, every now and then -- you will get incomprehensible error messages, usually about how this -- isn't an instance of that. These are how type errors typically -- manifest, so first double check to make sure you aren't trying to mix -- vectors of different dimension or component types. If you still get -- these errors, manual type annotations usually make them go away. -- -- Related Work -- -- See previous work by David Menendez, -- http://haskell.org/pipermail/haskell/2005-May/015815.html -- -- and of course Oleg Kiselyov, -- http://okmij.org/ftp/papers/number-parameterized-types.pdf -- -- Other vector and linear algebra packages : -- -- vector-space, by Conal Elliott : -- http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vector-space -- -- hmatrix, by Alberto Ruiz : -- http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmatrix -- -- blas bindings, by Patrick Perry : -- http://hackage.haskell.org/cgi-bin/hackage-scripts/package/blas -- -- templatized geometry library (C++), by Oliver Kreylos : -- http://graphics.cs.ucdavis.edu/~okreylos/ResDev/Geometry/index.html module Data.Vec