vector-space-map (empty) → 0.1.0.0

raw patch · 4 files changed

+136/−0 lines, 4 filesdep +basedep +containersdep +vector-spacesetup-changed

Dependencies added: base, containers, vector-space

Files

LICENSE +7/−0
Setup.hs +2/−0
src/Data/Map/Vector.hs +96/−0
vector-space-map.cabal +31/−0

+ LICENSE view

@@ -0,0 +1,7 @@+Copyright (c) 2013 Christian Conkle
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple
+main = defaultMain

+ src/Data/Map/Vector.hs view

@@ -0,0 +1,96 @@+{-# LANGUAGE TypeFamilies, FlexibleContexts #-}
+{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable, DeriveDataTypeable #-}
+module Data.Map.Vector (MapVector(..)) where
+
+import Prelude hiding (foldr)
+import Data.Foldable
+import Data.Traversable
+import Data.Data
+import Control.Applicative
+import Data.AdditiveGroup
+import Data.VectorSpace
+import Data.Map (Map)
+import qualified Data.Map as Map
+
+-- TODO: Clean up overlong >>> examples.
+
+-- | Note: '<*>' in the 'Applicative' instance operates under /intersection/.  i.e.:
+--
+-- >>> (MapVector $ Map.fromList [("x", id)]) <*> (MapVector $ Map.fromList [("y", 3)])
+-- MapVector (Map.fromList [])
+--  
+-- '*' in the 'Num' instance performs elementwise multiplication.  It is defined in terms of
+-- '<*>' and therefore also operates under intersection:
+--   
+-- >>> (MapVector $ Map.fromList [("x", 2), ("y", 3)]) * (MapVector $ Map.fromList [("x", 5),("y", 7)])
+-- MapVector (Map.fromList [("x", 10), ("y", 21)])
+--   
+-- >>> (MapVector $ Map.fromList [("x", 2), ("y", 3)]) * (MapVector $ Map.fromList [("y", 7)])
+-- MapVector (Map.fromList [("y", 21)])
+--
+-- '*^' in the 'VectorSpace' instance multiplies by the scalar of v.  Nesting MapVectors preserves
+-- the scalar type, e.g. @Scalar (MapVector k (MapVector k' v))@ = @Scalar v@.
+--
+-- >>> 2 *^ (ConstantMap $ MapVector $ Map.fromList [("x", 3 :: Int), ("y", 5)])
+-- ConstantMap (MapVector (fromList [("x",6),("y",10)]))
+--
+-- Finally, '<.>' in 'InnerSpace' is the dot-product operator.  Again, it operates under intersection.
+--
+-- >>> (MapVector $ Map.fromList [("x", 2 :: Int), ("y", 3)]) <.> (MapVector $ Map.fromList [("x", 5),("y", 7)])
+-- 31
+--
+-- >>> (pure . MapVector $ Map.fromList [("x", 2 :: Int), ("y", 3)]) <.> (MapVector $ Map.fromList [("a", pure (5::Int))])
+-- 25
+--
+-- Addition, using either '+' or '^+^', operates under union.
+
+data MapVector k v = 
+      MapVector (Map k v) 
+    | ConstantMap v -- ^ An infinite-dimensional vector with the same value on all dimensions
+    deriving (Eq, Functor, Show, Read, Foldable, Traversable, Typeable, Data)
+
+instance (Ord k) => Applicative (MapVector k) where 
+    pure = ConstantMap
+    (ConstantMap f) <*> (ConstantMap v) = ConstantMap $ f v
+    (ConstantMap f) <*> (MapVector vs)  = MapVector   $ f     <$> vs
+    (MapVector fs)  <*> (ConstantMap v) = MapVector   $ ($ v) <$> fs
+    (MapVector fs)  <*> (MapVector vs)  = MapVector   $ Map.intersectionWith ($) fs vs
+
+instance (AdditiveGroup v, Ord k) => AdditiveGroup (MapVector k v) where
+    zeroV = MapVector Map.empty
+    negateV = fmap negateV
+    (ConstantMap v) ^+^ (ConstantMap v') = ConstantMap $ v ^+^ v'
+    (ConstantMap v) ^+^ (MapVector vs)   = MapVector   $ (v ^+^) <$> vs
+    (MapVector vs)  ^+^ (ConstantMap v)  = MapVector   $ (^+^ v) <$> vs
+    (MapVector vs)  ^+^ (MapVector vs')  = MapVector   $ Map.unionWith (^+^) vs vs'
+    
+instance (Ord k, VectorSpace v) => VectorSpace (MapVector k v) where
+    type Scalar (MapVector k v) = Scalar v  -- therefore Scalar (MapVector k (Mapvector k' v))
+                                            --   = Scalar v
+    s *^ v  = (s *^) <$> v 
+
+instance (Ord k, VectorSpace v, InnerSpace v, AdditiveGroup (Scalar v)) => InnerSpace (MapVector k v) where
+    (ConstantMap v) <.> (ConstantMap v') =                      v <.> v'
+    (ConstantMap v) <.> (MapVector vs)   = foldl' (^+^) zeroV $ (v <.>) <$> vs
+    (MapVector vs)  <.> (ConstantMap v)  = foldl' (^+^) zeroV $ (<.> v) <$> vs
+    (MapVector vs)  <.> (MapVector vs')  = foldl' (^+^) zeroV $ Map.intersectionWith (<.>) vs vs'
+
+instance (Ord k, AdditiveGroup v, Num v) => Num (MapVector k v) where
+    (+) = (^+^)
+    x * y = (*) <$> x <*> y
+    abs = fmap abs
+    fromInteger = pure . fromInteger
+    signum = error "no signum for MapVectors"
+
+
+-- It looks like a HasBasis instance should be possible; 
+-- I just haven't spent the time to figure it out.
+
+-- (Remember to tighten version bounds on vector-space if this is implemented.)
+
+--instance (Ord k, HasBasis v) => HasBasis (MapVector k v) where
+--    type Basis (MapVector k v) = (k, Basis v)
+--    basisValue (k, v) = MapVector $ Map.fromList $ (k, basisValue v):[]
+--    
+--    decompose (ConstantMap _) = error "decompose: not defined for ConstantMap"
+--    decompose (MapVector vs) =

+ vector-space-map.cabal view

@@ -0,0 +1,31 @@+-- Initial vector-space-map.cabal generated by cabal init.  For further 
+-- documentation, see http://haskell.org/cabal/users-guide/
+
+name:                vector-space-map
+version:             0.1.0.0
+synopsis:            vector-space operations for finite maps using Data.Map
+description:         Data.Map.Vector provides @MapVector@, a wrapper around @Map@ from @containers@ which supports constant maps, i.e. maps containing only one value.  This allows an identity under intersection and an @Applicative@ instance.  It also has instances of @AdditiveGroup@, @VectorSpace@, @InnerSpace@, and @Num@ with appropriate value types.  Provides operations for addition, subtraction, element-wise multiplication (through @Num@), scalar multiplication (through @VectorSpace@), and dot product.
+homepage:            https://github.com/conklech/vector-space-map
+license:             MIT
+license-file:        LICENSE
+author:              Christian Conkle
+maintainer:          christian@conkle.org
+
+category:            Math
+build-type:          Simple
+cabal-version:       >=1.6
+
+source-repository    head
+  type:              git
+  location:          git://github.com/conklech/vector-space-map.git
+
+source-repository    this
+  type:              git
+  location:          git://github.com/conklech/vector-space-map.git  
+  tag:               0.1.0.0
+
+library
+  hs-source-dirs:    src
+  exposed-modules:   Data.Map.Vector 
+  build-depends:     base < 5, containers < 0.6, vector-space < 0.9
+