vector-space 0.5.2 → 0.5.3

raw patch · 5 files changed

+127/−72 lines, 5 filesdep ~MemoTriedep ~basePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: MemoTrie, base

API changes (from Hackage documentation)

Files

• src/Data/AdditiveGroup.hs +10/−0
• src/Data/LinearMap.hs +40/−10
• src/Data/Maclaurin.hs +51/−52
• src/Data/VectorSpace.hs +23/−7
• vector-space.cabal +3/−3

@@ -84,6 +84,16 @@   (^+^)   = liftA2 (^+^)   negateV = fmap   negateV ++-- Maybe is handled like the Maybe-of-Sum monoid+instance AdditiveGroup a => AdditiveGroup (Maybe a) where+  zeroV = Nothing+  Nothing ^+^ b'      = b'+  a' ^+^ Nothing      = a'+  Just a' ^+^ Just b' = Just (a' ^+^ b')+  negateV = fmap negateV++ -- Memo tries instance (HasTrie u, AdditiveGroup v) => AdditiveGroup (u :->: v) where   zeroV   = pure   zeroV

@@ -1,4 +1,4 @@-{-# LANGUAGE TypeOperators, FlexibleContexts, TypeFamilies #-}+{-# LANGUAGE TypeOperators, FlexibleContexts, TypeFamilies, CPP #-} {-# OPTIONS_GHC -Wall -fno-warn-orphans #-} -- {-# OPTIONS_GHC -funbox-strict-fields #-} -- {-# OPTIONS_GHC -ddump-simpl-stats -ddump-simpl #-}@@ -12,33 +12,63 @@ -- Stability   :  experimental --  -- Linear maps--- This version uses ABasis, which requires ghc-6.10 or later. ----------------------------------------------------------------------  module Data.LinearMap-  ( (:-*) , linear, lapply+  ( (:-*) , linear, lapply, idL, compL   ) where  import Control.Arrow (first)-import Data.Function -import Data.MemoTrie-import Data.VectorSpace-import Data.Basis+import Data.MemoTrie    ((:->:)(..))+import Data.VectorSpace (VectorSpace(..))+import Data.Basis       (HasBasis(..), linearCombo)  +-- Linear maps are almost but not quite a Control.Category.  The type+-- class constraints interfere.  They're almost an Arrow also, but for the+-- constraints and the generality of arr.+ -- | Linear map, represented as a memo-trie from basis to values. type u :-* v = Basis u :->: v + -- TODO: Use a regular function from @Basis u@, but memoize it.  -- | Function (assumed linear) as linear map.-linear :: (VectorSpace u, VectorSpace v, HasBasis u, HasTrie (Basis u)) =>+linear :: (HasBasis u, HasTrie (Basis u)) =>           (u -> v) -> (u :-* v) linear f = trie (f . basisValue)  -- | Apply a linear map to a vector.-lapply :: ( VectorSpace u, VectorSpace v, Scalar u ~ Scalar v+lapply :: ( VectorSpace v, Scalar u ~ Scalar v           , HasBasis u, HasTrie (Basis u) ) =>           (u :-* v) -> (u -> v)-lapply lm = linearCombo . fmap (first (untrie lm)) . decompose+lapply tr = linearCombo . fmap (first (untrie tr)) . decompose+++-- Identity linear map+idL :: (HasBasis u, HasTrie (Basis u)) => +       u :-* u+idL = linear id++-- | Compose linear maps+compL :: ( HasBasis u, HasTrie (Basis u)+         , HasBasis v, HasTrie (Basis v)+         , VectorSpace w, Scalar v ~ Scalar w ) =>+         (v :-* w) -> (u :-* v) -> (u :-* w)++compL vw = fmap (lapply vw)++-- It may be helpful that @lapply vw@ is evaluated just once and not+-- once per uv.  'untrie' can strip off all of its trie constructors.++-- Less efficient definition:+-- +--   vw `compL` uv = linear (lapply vw . lapply uv)+-- +--   i.e., compL = inL2 (.)+-- +-- The problem with these definitions is that basis elements get converted+-- to values and then decomposed, followed by recombination of the+-- results.

@@ -31,7 +31,7 @@ module Data.Maclaurin   (     (:>), powVal, derivative-  , (:~>), dZero, pureD+  , (:~>), pureD   , fmapD, (<$>>){-, (<*>>)-}, liftD2, liftD3   , idD, fstD, sndD   , linearD, distrib@@ -60,44 +60,51 @@ noOv :: String -> a noOv op = error (op ++ ": not defined on a :> b") --- | Derivative tower full of 'zeroV'.-dZero :: (AdditiveGroup b, HasBasis a, HasTrie (Basis a)) => a:>b-dZero = pureD zeroV+-- -- | Derivative tower full of 'zeroV'.+-- dZero :: (AdditiveGroup b, HasBasis a, HasTrie (Basis a)) => a:>b+-- dZero = pureD zeroV  -- | Constant derivative tower. pureD :: (AdditiveGroup b, HasBasis a, HasTrie (Basis a)) => b -> a:>b-pureD b = b `D` pure dZero+pureD b = b `D` zeroV +-- pureD b = b `D` pure dZero + infixl 4 <$>> -- | Map a /linear/ function over a derivative tower.-fmapD, (<$>>) :: (HasTrie (Basis a), VectorSpace b) =>+fmapD, (<$>>) :: (HasTrie (Basis a)) =>                  (b -> c) -> (a :> b) -> (a :> c) fmapD f (D b0 b') = D (f b0) ((fmap.fmapD) f b')  (<$>>) = fmapD --- infixl 4 <*>>--- -- | Like '(<*>)' for derivative towers.--- (<*>>) :: (HasTrie (Basis a), VectorSpace b s, VectorSpace c s) =>---           (a :> (b -> c)) -> (a :> b) -> (a :> c)--- D f0 f' <*>> D x0 x' = D (f0 x0) (liftA2 (<*>>) f' x')- -- | Apply a /linear/ binary function over derivative towers.-liftD2 :: (HasTrie (Basis a), VectorSpace b, VectorSpace c, VectorSpace d) =>+liftD2 :: HasTrie (Basis a) =>           (b -> c -> d) -> (a :> b) -> (a :> c) -> (a :> d) liftD2 f (D b0 b') (D c0 c') = D (f b0 c0) (liftA2 (liftD2 f) b' c') + -- | Apply a /linear/ ternary function over derivative towers.-liftD3 :: ( HasTrie (Basis a)-          , VectorSpace b, VectorSpace c-          , VectorSpace d, VectorSpace e ) =>+liftD3 :: HasTrie (Basis a) =>           (b -> c -> d -> e)        -> (a :> b) -> (a :> c) -> (a :> d) -> (a :> e) liftD3 f (D b0 b') (D c0 c') (D d0 d') = D (f b0 c0 d0) (liftA3 (liftD3 f) b' c' d') --- TODO: try defining liftD2, liftD3 in terms of (<*>>) above+-- TODO: Define liftD2, liftD3 in terms of (<*>>) Compare generated code+-- for speed. +-- infixl 4 <*>>+-- -- | Like '(<*>)' for derivative towers.+-- (<*>>) :: (HasTrie (Basis a)) =>+--           (a :> (b -> c)) -> (a :> b) -> (a :> c)+-- D f0 f' <*>> D x0 x' = D (f0 x0) (liftA2 (<*>>) f' x')++-- liftD2 f a b = (f <$>> a) <*>> b++-- liftD3 f a b c = liftD2 f a b <*>> c++ -- | Differentiable identity function.  Sometimes called "the -- derivation variable" or similar, but it's not really a variable. idD :: ( VectorSpace u, s ~ Scalar u@@ -111,24 +118,11 @@  -- | Every linear function has a constant derivative equal to the function -- itself (as a linear map).-linearD :: ( HasBasis u, HasTrie (Basis u)-           , VectorSpace v ) =>+linearD :: (HasBasis u, HasTrie (Basis u), AdditiveGroup v) =>            (u -> v) -> (u :~> v) --- f :: u -> v---- pureD . f :: u -> u:>v---- linear (pureD . f) :: - -- linearD f u = f u `D` linear (pureD . f) --- data a :> b = D { powVal :: b, derivative :: a :-* (a :> b) }---- linear :: (VectorSpace u s, VectorSpace v s, HasBasis u s, HasTrie (Basis u)) =>---           (u -> v) -> (u :-* v)-- -- HEY!  I think there's a hugely wasteful recomputation going on in -- 'linearD' above.  Note the definition of 'linear': -- @@ -142,8 +136,6 @@  -- Look for similar problems. --- - linearD f = \ u -> f u `D` d  where    d = linear (pureD . f)@@ -172,41 +164,47 @@ -- | Derivative tower for applying a binary function that distributes over -- addition, such as multiplication.  A bit weaker assumption than -- bilinearity.-distrib :: ( HasBasis a, HasTrie (Basis a), VectorSpace u-           -- , VectorSpace b, VectorSpace c-           ) => (b -> c -> u) -> (a :> b) -> (a :> c) -> (a :> u)+distrib :: forall a b c u.+           (HasBasis a, HasTrie (Basis a), AdditiveGroup u) =>+           (b -> c -> u) -> (a :> b) -> (a :> c) -> (a :> u) -distrib op u@(D u0 u') v@(D v0 v') =-  D (u0 `op` v0) (trie (\ da -> distrib op u (v' `untrie` da) ^+^-                                distrib op (u' `untrie` da) v))+-- distrib op u@(D u0 u') v@(D v0 v') =+--   D (u0 `op` v0) (trie (\ e -> distrib op u (v' `untrie` e) ^+^+--                                distrib op (u' `untrie` e) v)) +distrib op u@(D u0 u') v@(D v0 v') = D (u0 `op` v0) (inTrie2 comb u' v')+ where+   -- comb :: (Basis a -> a :> b) -> (Basis a -> a :> c) -> (Basis a -> a :> u)+   comb uf vf (e :: Basis a) =+     distrib op u (vf e) ^+^ distrib op (uf e) v --- TODO: look for a simpler definition of distrib.  See the applicative--- instance for @(:->:) a@, or define @inTrie2@.+--   comb uf vf = distrib op u . vf ^+^ flip (distrib op) v . uf --- TODO: This distrib is exponential in increasing degree.  Switch to the--- Horner representation.  See /The Music of Streams/ by Doug McIlroy.+-- TODO: Look for a formulation of distrib that eliminates the explicit+-- conversion between functions and tries.  Maybe something with trie addition.  +-- TODO: I think this distrib is exponential in increasing degree.  Switch+-- to the Horner representation.  See /The Music of Streams/ by Doug+-- McIlroy.++ instance Show b => Show (a :> b) where show    = noOv "show" instance Eq   b => Eq   (a :> b) where (==)    = noOv "(==)" instance Ord  b => Ord  (a :> b) where compare = noOv "compare" -instance (HasBasis a, HasTrie (Basis a), VectorSpace u) => AdditiveGroup (a :> u) where+instance (HasBasis a, HasTrie (Basis a), AdditiveGroup u) => AdditiveGroup (a :> u) where   zeroV   = pureD  zeroV    -- or dZero   negateV = fmapD  negateV   (^+^)   = liftD2 (^+^) -instance ( HasBasis a, HasTrie (Basis a)-         , VectorSpace u, s ~ Scalar u-         -- , VectorSpace s, s ~ Scalar s-         )-        => VectorSpace (a :> u) where+instance (HasBasis a, HasTrie (Basis a), VectorSpace u)+      => VectorSpace (a :> u) where   type Scalar (a :> u) = (a :> Scalar u)   (*^) = distrib (*^)                      -instance ( InnerSpace u, s ~ Scalar u, InnerSpace s, s ~ Scalar s-         , HasBasis a, HasTrie (Basis a)) =>+instance ( InnerSpace u, s ~ Scalar u, AdditiveGroup s+         , HasBasis a, HasTrie (Basis a) ) =>      InnerSpace (a :> u) where   (<.>) = distrib (<.>) @@ -231,7 +229,8 @@ -- TODO: express '(>-<)' in terms of '(@.)'.  If I can't, then understand why not.  instance ( HasBasis a, s ~ Scalar a, HasTrie (Basis a)-         , Num s, VectorSpace s, Scalar s ~ s)+         , Num s, VectorSpace s, Scalar s ~ s+         )       => Num (a:>s) where   fromInteger = pureD . fromInteger   (+) = liftD2  (+)

@@ -68,9 +68,6 @@ lerp :: VectorSpace v => v -> v -> Scalar v -> v lerp a b t = a ^+^ t *^ (b ^-^ a) --- lerp :: (VectorSpace v, s ~ Scalar v, Num s) => v -> v -> s -> v--- lerp a b t = (1-t)*^a ^+^ t*^b- -- | Square of the length of a vector.  Sometimes useful for efficiency. -- See also 'magnitude'. magnitudeSq :: (InnerSpace v, s ~ Scalar v) => v -> s@@ -139,14 +136,33 @@   (u,v,w) <.> (u',v',w') = u<.>u' ^+^ v<.>v' ^+^ w<.>w'  --- Standard instance for an applicative functor applied to a vector space.+-- Standard instances for a functor applied to a vector space.++-- For 'Maybe', Nothing represents 'zeroV'.  Useful for optimization, since+-- we might not be able to test for 'zeroV', e.g., functions and infinite+-- derivative towers.+instance VectorSpace v => VectorSpace (Maybe v) where+  type Scalar (Maybe v) = Scalar v+  (*^) s = fmap (s *^)+ instance VectorSpace v => VectorSpace (a -> v) where   type Scalar (a -> v) = Scalar v   (*^) s = fmap (s *^) --- No 'InnerSpace' instance for @(a -> v)@.- instance (HasTrie a, VectorSpace v)          => VectorSpace (a :->: v) where   type Scalar (a :->: v) = Scalar v-  (*^) s = fmap ((*^) s)+  (*^) s = fmap (s *^)++-- No 'InnerSpace' instance for @a -> v@.+++instance (InnerSpace a, AdditiveGroup (Scalar a)) => InnerSpace (Maybe a) where+  -- dotting with zero (vector) yields zero (scalar)+  Nothing <.> _     = zeroV+  _ <.> Nothing     = zeroV+  Just u <.> Just v = u <.> v++--   mu <.> mv = fromMaybe zeroV (liftA2 (<.>) mu mv)++--   (<.>) = (fmap.fmap) (fromMaybe zeroV) (liftA2 (<.>))

@@ -1,7 +1,7 @@ Name:                vector-space-Version:             0.5.2+Version:             0.5.3 Cabal-Version:       >= 1.2-Synopsis:            Vector & affine spaces, linear maps, and derivatives (requires ghc 6.9)+Synopsis:            Vector & affine spaces, linear maps, and derivatives (requires ghc 6.9 or better) Category:            math Description:   /vector-space/ provides classes and generic operations for vector@@ -28,7 +28,7 @@ Library   hs-Source-Dirs:      src   Extensions:          -  Build-Depends:       base, MemoTrie+  Build-Depends:       base, MemoTrie >= 0.4.2   Exposed-Modules:                           Data.AdditiveGroup                      Data.VectorSpace