Vec 0.9.4 → 0.9.5

raw patch · 4 files changed

+124/−128 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/Vec/Base.hs +16/−16
• Data/Vec/LinAlg.hs +86/−96
• Data/Vec/Packed.hs +20/−15
• Vec.cabal +2/−1

@@ -38,7 +38,7 @@   show (a:.v) = "(" ++ show a ++ "):." ++ showVec v  --- | Helper to keep parentheses at bay. Just use @show@ as usual.+-- Helper to keep parentheses at bay. Just use @show@ as usual. class ShowVec  v where   showVec :: v -> String @@ -243,23 +243,23 @@  -- | Fold a function over a vector.  -class Fold a v | v -> a where+class Fold v a | v -> a where   fold  :: (a -> a -> a) -> v -> a   foldl :: (b -> a -> b) -> b -> v -> b   foldr :: (a -> b -> b) -> b -> v -> b -instance Fold a (a:.()) where+instance Fold (a:.()) a where   fold  f   (a:._) = a -  foldl f z (a:._) = (f $! z) $! a-  foldr f z (a:._) = (f $! a) $! z+  foldl f z (a:._) = seq z $ f z a+  foldr f z (a:._) = f a z   {-# INLINE fold #-}   {-# INLINE foldl #-}   {-# INLINE foldr #-} -instance Fold a (a':.u) => Fold a (a:.a':.u) where-  fold  f   (a:.v) = (f $! a) $! (fold f v)-  foldl f z (a:.v) = (f $! (foldl f z v)) $! a-  foldr f z (a:.v) = (f $! a) $! (foldr f z v)+instance Fold (a':.u) a => Fold (a:.a':.u) a where+  fold  f   (a:.v) = f a (fold f v)+  foldl f z (a:.v) = seq z $ f (foldl f z v) a+  foldr f z (a:.v) = f a (foldr f z v)   {-# INLINE fold #-}   {-# INLINE foldl #-}   {-# INLINE foldr #-}@@ -376,26 +376,26 @@   -- | sum of vector elements-sum ::  (Fold a v, Num a) => v -> a+sum ::  (Fold v a, Num a) => v -> a sum x     = fold (+) x {-# INLINE sum #-}  -- | product of vector elements-product ::  (Fold a v, Num a) => v -> a+product ::  (Fold v a, Num a) => v -> a product x = fold (*) x {-# INLINE product #-}  -- | maximum vector element-maximum ::  (Fold a v, Ord a) => v -> a+maximum ::  (Fold v a, Ord a) => v -> a maximum x = fold max x {-# INLINE maximum #-}  -- | minimum vector element-minimum ::  (Fold a v, Ord a) => v -> a+minimum ::  (Fold v a, Ord a) => v -> a minimum x = fold min x {-# INLINE minimum #-} -toList ::  (Fold a v) => v -> [a]+toList ::  (Fold v a) => v -> [a] toList = foldr (:) []  {-# INLINE toList #-} @@ -426,12 +426,12 @@ type Mat48 a = Vec4 (Vec8 a)  -- | convert a matrix to a list-of-lists-matToLists ::  (Fold a v, Fold v m) => m -> [[a]]+matToLists ::  (Fold v a, Fold m v) => m -> [[a]] matToLists   = (P.map toList) . toList {-# INLINE matToLists   #-}  -- | convert a matrix to a list in row-major order-matToList  ::  (Fold a v, Fold v m) => m -> [a]+matToList  ::  (Fold v a, Fold m v) => m -> [a] matToList    = concat . matToLists {-# INLINE matToList    #-} 

@@ -9,8 +9,8 @@ {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TypeOperators #-} {-# LANGUAGE TypeSynonymInstances #-}-{-# LANGUAGE OverlappingInstances #-} {-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE TypeFamilies #-}  {-# OPTIONS_HADDOCK ignore-exports,prune #-} @@ -58,30 +58,30 @@ import Unsafe.Coerce  --- | dot / inner / scalar product-dot ::  (Num a, Num v, Fold a v) => v -> v -> a+-- | dot \/ inner \/ scalar product+dot ::  (Num a, Num v, Fold v a) => v -> v -> a dot u v = sum (u*v) {-# INLINE dot #-}  -- | vector norm, squared-normSq ::  (Num a, Num v, Fold a v) => v -> a+normSq ::  (Num a, Num v, Fold v a) => v -> a normSq v = dot v v {-# INLINE normSq #-} --- | vector / L2 / Euclidean norm-norm ::  (Num v, Floating a, Fold a v) => v -> a+-- | vector \/ L2 \/ Euclidean norm+norm ::  (Num v, Floating a, Fold v a) => v -> a norm v = sqrt (dot v v) {-# INLINE norm #-}  -- | @normalize v@ is a unit vector in the direction of @v@. @v@ is assumed -- non-null.-normalize :: (Floating a, Num v, Fold a v, Map a a v v) => v -> v+normalize :: (Floating a, Num v, Fold v a, Map a a v v) => v -> v normalize v = map (/(norm v)) v {-# INLINE normalize #-}  -- | 3d cross product. cross :: Num a => Vec3 a -> Vec3 a -> Vec3 a-cross (ux:.uy:.uz:.()) (vx:.vy:.vz:.()) =+cross (ux:.uy:.uz:._) (vx:.vy:.vz:._) =   (uy*vz-uz*vy):.(uz*vx-ux*vz):.(ux*vy-uy*vx):.() {-# INLINE cross #-} @@ -111,7 +111,7 @@ multvm ::    ( Transpose m mt   , Map v a mt v'-  , Fold a v+  , Fold v a   , Num a   , Num v   ) => v -> m -> v'@@ -122,7 +122,7 @@ multmv ::    ( Map v a m v'   , Num v-  , Fold a v+  , Fold v a   , Num a   ) => m -> v -> v' multmv m v = map (dot v) m@@ -133,7 +133,7 @@   (Map v v' m1 m3   ,Map v a b v'   ,Transpose m2 b-  ,Fold a v+  ,Fold v a   ,Num v   ,Num a   ) => m1 -> m2 -> m3@@ -307,9 +307,59 @@ {-# INLINE identity #-}  --- DropConsec: this is a helper function for computing determinants. Given an--- n-vector v, drop each element from v and collect the remaning (n-1)-vectors--- into an n-vector (ie an n-by-(n-1) matrix)+++++-- Det' needs help inferring that all of the matrix elements are the same type.++-- | 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 :: forall n a r m. (Vec n a r, Vec n r m, Det' m a) => m -> a+det = det'+{-# INLINE det #-}++++-- The Determinant of a square matrix, by minor expansion. +class Det' m a | m -> a where+  det' :: m -> a+++instance Det' ((a:.()):.()) a where+  det' ((a:._):._) = a++++instance +  ( (a:.a:.v) ~ r                  -- a row of the matrix, an n-vector+  , ((a:.a:.v):.(a:.a:.v):.vs) ~ m -- an n*n matrix, n >= 2+  , ((a:.v):.(a:.v):.vs_) ~ m_     -- an n*(n-1) matrix+  , (((a:.v):.vs_):.(x:.y)) ~ mm   -- an n-vector of (n-1)*(n-1) matrices to recurse upon+  , Map (a:.a:.v) (a:.v) m m_      -- drop the first column of m to get m_+  , DropConsec m_ mm               -- an n-vector of (n-1)*(n-1) matrices+  , Det' ((a:.v):.vs_) a           -- determinant of (n-1)*(n-1) matrix+  , Map ((a:.v):.vs_) a mm r       -- dets of all n of the (n-1)*(n-1) matrices, the result is same type as a row+  , Map r a m r                    -- grab the first column using "map head" the result is same type as a row+  , NegateOdds r                   -- flip sign of odd elements of first column+  , Fold r a                       -- add evertyhing up...+  , Num r+  , Num a+  ) => Det' ((a:.a:.v):.(a:.a:.v):.vs) a                    -- et voila+  where+  det' m =+    sum $ (negateOdds $ map head m) * map det' (dropConsec $ map tail m)+++-- DropConsec: Drop consecutive elements, collecting the results. Given an+-- n-vector v, drop each element from v, one at a time in sequence, and collect+-- the resulting (n-1)-vectors into an n-vector (ie an n-by-(n-1) matrix).+-- This is used for determinants.+-- +-- dropConsec [1,2,3,4] = [[2,3,4],[1,3,4],[1,2,4],[1,2,3]]+-- class DropConsec v vv | v -> vv where   dropConsec :: v -> vv @@ -344,95 +394,35 @@   ---Alternating: vector of alternating positive/negative values. This is also a---helper for computing determinants-class Alternating n a v | v -> n a where-  alternating :: n -> a -> v+-- Negate the odd or even elements of a vector.+-- Used for determinants. -instance Alternating N1 a (a:.()) where-  alternating _ a = a:.()-  {-# INLINE alternating #-}+class NegateOdds v where+  negateOdds :: v -> v  -instance (Num a, Alternating n a (a:.v)) => Alternating (Succ n) a (a:.a:.v) where-  alternating _ a = a:.(alternating (undefined::n) (negate a))-  {-# INLINE alternating #-}+class NegateEvens v where+  negateEvens :: v -> v  +instance NegateOdds  () where +  negateOdds  () = () +  {-# INLINE negateOdds #-}+instance NegateEvens () where +  negateEvens () = () +  {-# INLINE negateEvens #-} --- The Determinant of a square matrix, by minor expansion. -class Det' a m | m -> a where-  det' :: m -> a+instance (Num a, NegateEvens v) => NegateOdds (a:.v) where+  negateOdds (a:.v) = a :. negateEvens v+  {-# INLINE negateOdds #-} -instance Num a => Det' a ((a:.a:.()):.(a:.a:.()):.()) where-  det' ( (a:.b:.()) :. (c:.d:.()) :. () ) = a*d-b*c-  {-# INLINE det' #-}+instance (Num a, NegateOdds v) => NegateEvens (a:.v) where+  negateEvens (a:.v) = negate a :. negateOdds v+  {-# INLINE negateEvens #-}  ---This is the only overlapping instance in the whole library (goddamnit)-instance-    (Num a-    ,Fold a v-    ,Num v-    ,Head m v-    ,Vec n a v-    ,Map m__ a vm v-    ,Transpose vmt vm-    ,DropConsec v vv-    ,Map v vv m_ vmt-    ,Tail m m_-    ,Alternating n a v-    ,Det' a m__-    )-    => Det' a m-  where-    det' m =-      sum ((alternating undefined 1) * (head m) *-           (map det' (transpose(map(dropConsec)(tail m)))))-    {-# INLINE det' #-} ---For reference, here is the non-overlapping instance that worked in 6.8. When---I figure out what happened between 6.8 and 6.10, hopefully we can go back to---a non-overlapping instance. -{--instance-    (Num a-    ,Num (a:.a:.a:.v)-    ,Fold a (a:.a:.a:.v)-    ,Alternating (Succ (Succ (Succ n))) a (a:.a:.a:.v)-    ,DropConsec (a:.a:.a:.v) vv-    ,Map (a:.a:.a:.v) vv ((a:.a:.a:.v):.(a:.a:.a:.v):.m) vmt-    ,Transpose vmt vm-    ,Map ((a:.a:.v):.(a:.a:.v):.m_) a vm (a:.a:.a:.v)-    ,Det' a ((a:.a:.v):.(a:.a:.v):.m_)-    ,Vec (Succ (Succ (Succ n))) a (a:.a:.a:.v)-    ,Vec (Succ (Succ (Succ n))) (a:.a:.a:.v) ((a:.a:.a:.v):.(a:.a:.a:.v):.(a:.a:.a:.v):.m)-    )-     => -    Det' a ((a:.a:.a:.v):.(a:.a:.a:.v):.(a:.a:.a:.v):.m)-  where-    det' (mh:.mt) =-      sum ((alternating undefined 1) * mh *-          (map det' (transpose (map dropConsec mt :: vmt))))-    {-# INLINE det' #-}--}  ---- For now, use wrapper class to allow type inference. I think maybe the--- squareness of the matrix is keeping Det' from inferring properly, so we'll--- enforce that here. But really I have no clue.----- | Determinant by minor expansion. Unfolds into a closed form expression.--- This should be the fastest way for 4x4 and smaller, but @snd . gaussElim@--- works too.--det :: forall n a r m. (Vec n a r, Vec n r m, Det' a m) => m -> a-det = det'-{-# INLINE det #-}--- --ReplConsec : this is a helper for implementing Cramer's rule.  Given an --n-vector v and a value r, replace each consecutive element from v with r, --and collect the resulting n-vectors into an n-vector (ie an n-by-n matrix)@@ -484,8 +474,8 @@   ,Vec n b vv   ,Vec n a2 b   ,Fractional a1-  ,Det' a1 m-  ,Det' a1 a+  ,Det' m a1+  ,Det' a a1   ) => m -> v -> v cramer'sRule m b =   case map (\m' -> (det' m')/(det' m)) @@ -645,7 +635,7 @@ instance      ( Map (a:.r) r ((a:.r):.rs) rs_ --map tail     , Map r (a:.r) rs_ ((a:.r):.rs) --map cons-    , Fold (a,a:.r) aas+    , 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@@ -677,7 +667,7 @@ instance      ( Map (a:.r) r ((a:.r):.rs) rs_ --map tail     , Map r (a:.r) rs_ ((a:.r):.rs) --map cons-    , Fold (a,a:.r) aas+    , 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

@@ -12,12 +12,13 @@ {-# LANGUAGE TypeSynonymInstances      #-} {-# LANGUAGE UndecidableInstances      #-} --- | Packed vectors : use these whenever possible. The generic vector type is--- is represented at run-time by a linked list of boxed values. Packed types,--- however, store the vector components sequentially in memory. Vector--- operations can be defined using the generic types, and the compiler will--- inline and specialize these definitions for the packed types, avoiding any--- list cells or unnecessary heap allocations.+-- | 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@@ -33,15 +34,17 @@ -- 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, 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. +-- @'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.+-- 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 where @@ -63,6 +66,8 @@   pack   :: v -> Packed v   unpack :: Packed v -> v ++--who knows if this even does anything {-# RULES        "Vec pack/unpack" forall x.         pack (unpack x) = x; @@ -191,7 +196,7 @@   map f = pack . map f . unpack   {-# INLINE map #-} -instance (Fold a v, PackedVec v) => Fold a (Packed v) +instance (Fold v a, PackedVec v) => Fold (Packed v) a   where   fold f = fold f . unpack   foldl f z = foldl f z . unpack

@@ -1,9 +1,10 @@ Name:                Vec-Version:             0.9.4+Version:             0.9.5 License:             BSD3 License-file:        LICENSE Author:              Scott E. Dillard Maintainer:          Scott E. Dillard <sedillard@gmail.com>+Homepage:            http://graphics.cs.ucdavis.edu/~sdillard/Vec Stability:           Experimental Synopsis:            Fixed-length lists and low-dimensional linear algebra. Description: