{-# LANGUAGE MultiParamTypeClasses, TypeOperators
           , TypeFamilies, UndecidableInstances, CPP
           , FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances  #-}
{-# LANGUAGE DefaultSignatures   #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS_GHC -Wall #-}
----------------------------------------------------------------------
-- |
-- Module      :   Data.VectorSpace
-- Copyright   :  (c) Conal Elliott and Andy J Gill 2008
-- License     :  BSD3
--
-- Maintainer  :  conal@conal.net, andygill@ku.edu
-- Stability   :  experimental
--
-- Vector spaces
--
-- This version uses associated types instead of fundeps and
-- requires ghc-6.10 or later
----------------------------------------------------------------------

-- NB: I'm attempting to replace fundeps with associated types.  See
-- NewVectorSpace.hs.  Ran into trouble with type equality constraints not
-- getting propagated.  Manuel Ch is looking into it.
--
-- Blocking bug: http://hackage.haskell.org/trac/ghc/ticket/2448

module Data.VectorSpace
  ( module Data.AdditiveGroup
  , VectorSpace(..), (^/), (^*)
  , InnerSpace(..)
  , lerp, linearCombo, magnitudeSq, magnitude, normalized, project
  ) where

import Control.Applicative (liftA2)
import Data.Complex hiding (magnitude)
import Foreign.C.Types (CSChar, CInt, CShort, CLong, CLLong, CIntMax, CFloat, CDouble)
import Data.Ratio

import Data.AdditiveGroup
import Data.MemoTrie

import Data.VectorSpace.Generic
import qualified GHC.Generics as Gnrx
import GHC.Generics (Generic, (:*:)(..))

infixr 7 *^

-- | Vector space @v@.
class AdditiveGroup v => VectorSpace v where
  type Scalar v :: *
  type Scalar v = Scalar (VRep v)
  -- | Scale a vector
  (*^) :: Scalar v -> v -> v
  default (*^) :: (Generic v, VectorSpace (VRep v), Scalar (VRep v) ~ Scalar v)
                    => Scalar v -> v -> v
  Scalar v
μ *^ v
v = Rep v Void -> v
forall a x. Generic a => Rep a x -> a
Gnrx.to (Scalar v
Scalar (Rep v Void)
μ Scalar (Rep v Void) -> Rep v Void -> Rep v Void
forall v. VectorSpace v => Scalar v -> v -> v
*^ v -> Rep v Void
forall a x. Generic a => a -> Rep a x
Gnrx.from v
v :: VRep v)
  {-# INLINE (*^) #-}

infixr 7 <.>

-- | Adds inner (dot) products.
class (VectorSpace v, AdditiveGroup (Scalar v)) => InnerSpace v where
  -- | Inner/dot product
  (<.>) :: v -> v -> Scalar v
  default (<.>) :: (Generic v, InnerSpace (VRep v), Scalar (VRep v) ~ Scalar v)
                    => v -> v -> Scalar v
  v
v<.>v
w = (v -> Rep v Void
forall a x. Generic a => a -> Rep a x
Gnrx.from v
v :: VRep v) Rep v Void -> Rep v Void -> Scalar (Rep v Void)
forall v. InnerSpace v => v -> v -> Scalar v
<.> v -> Rep v Void
forall a x. Generic a => a -> Rep a x
Gnrx.from v
w
  {-# INLINE (<.>) #-}

infixr 7 ^/
infixl 7 ^*

-- | Vector divided by scalar
(^/) :: (VectorSpace v, s ~ Scalar v, Fractional s) => v -> s -> v
v
v ^/ :: v -> s -> v
^/ s
s = s -> s
forall a. Fractional a => a -> a
recip s
s Scalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^ v
v
{-# INLINE (^/) #-}

-- | Vector multiplied by scalar
(^*) :: (VectorSpace v, s ~ Scalar v) => v -> s -> v
^* :: v -> s -> v
(^*) = (s -> v -> v) -> v -> s -> v
forall a b c. (a -> b -> c) -> b -> a -> c
flip s -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
(*^)
{-# INLINE (^*) #-}

-- | Linear interpolation between @a@ (when @t==0@) and @b@ (when @t==1@).

-- lerp :: (VectorSpace v, s ~ Scalar v, Num s) => v -> v -> s -> v
lerp :: VectorSpace v => v -> v -> Scalar v -> v
lerp :: v -> v -> Scalar v -> v
lerp v
a v
b Scalar v
t = v
a v -> v -> v
forall v. AdditiveGroup v => v -> v -> v
^+^ Scalar v
t Scalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^ (v
b v -> v -> v
forall v. AdditiveGroup v => v -> v -> v
^-^ v
a)
{-# INLINE lerp #-}

-- | Linear combination of vectors
linearCombo :: VectorSpace v => [(v,Scalar v)] -> v
linearCombo :: [(v, Scalar v)] -> v
linearCombo [(v, Scalar v)]
ps = [v] -> v
forall (f :: * -> *) v. (Foldable f, AdditiveGroup v) => f v -> v
sumV [v
v v -> Scalar v -> v
forall v s. (VectorSpace v, s ~ Scalar v) => v -> s -> v
^* Scalar v
s | (v
v,Scalar v
s) <- [(v, Scalar v)]
ps]
{-# INLINE linearCombo #-}

-- | Square of the length of a vector.  Sometimes useful for efficiency.
-- See also 'magnitude'.
magnitudeSq :: (InnerSpace v, s ~ Scalar v) => v -> s
magnitudeSq :: v -> s
magnitudeSq v
v = v
v v -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
<.> v
v
{-# INLINE magnitudeSq #-}

-- | Length of a vector.   See also 'magnitudeSq'.
magnitude :: (InnerSpace v, s ~ Scalar v, Floating s) =>  v -> s
magnitude :: v -> s
magnitude = s -> s
forall a. Floating a => a -> a
sqrt (s -> s) -> (v -> s) -> v -> s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v -> s
forall v s. (InnerSpace v, s ~ Scalar v) => v -> s
magnitudeSq
{-# INLINE magnitude #-}

-- | Vector in same direction as given one but with length of one.  If
-- given the zero vector, then return it.
normalized :: (InnerSpace v, s ~ Scalar v, Floating s) =>  v -> v
normalized :: v -> v
normalized v
v = v
v v -> s -> v
forall v s.
(VectorSpace v, s ~ Scalar v, Fractional s) =>
v -> s -> v
^/ v -> s
forall v s. (InnerSpace v, s ~ Scalar v, Floating s) => v -> s
magnitude v
v
{-# INLINE normalized #-}

-- | @project u v@ computes the projection of @v@ onto @u@.
project :: (InnerSpace v, s ~ Scalar v, Fractional s) => v -> v -> v
project :: v -> v -> v
project v
u v
v = ((v
v v -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
<.> v
u) s -> s -> s
forall a. Fractional a => a -> a -> a
/ v -> s
forall v s. (InnerSpace v, s ~ Scalar v) => v -> s
magnitudeSq v
u) Scalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^ v
u
{-# INLINE project #-}

#define ScalarType(t) \
  instance VectorSpace (t) where \
    { type Scalar (t) = (t) \
    ; (*^) = (*) } ; \
  instance InnerSpace  (t) where (<.>) = (*)

ScalarType(Int)
ScalarType(Integer)
ScalarType(Double)
ScalarType(Float)
ScalarType(CSChar)
ScalarType(CInt)
ScalarType(CShort)
ScalarType(CLong)
ScalarType(CLLong)
ScalarType(CIntMax)
ScalarType(CDouble)
ScalarType(CFloat)

instance Integral a => VectorSpace (Ratio a) where
  type Scalar (Ratio a) = Ratio a
  *^ :: Scalar (Ratio a) -> Ratio a -> Ratio a
(*^) = Scalar (Ratio a) -> Ratio a -> Ratio a
forall a. Num a => a -> a -> a
(*)
instance Integral a => InnerSpace  (Ratio a) where <.> :: Ratio a -> Ratio a -> Scalar (Ratio a)
(<.>) = Ratio a -> Ratio a -> Scalar (Ratio a)
forall a. Num a => a -> a -> a
(*)

instance (RealFloat v, VectorSpace v) => VectorSpace (Complex v) where
  type Scalar (Complex v) = Scalar v
  Scalar (Complex v)
s*^ :: Scalar (Complex v) -> Complex v -> Complex v
*^(v
u :+ v
v) = Scalar v
Scalar (Complex v)
sScalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^v
u v -> v -> Complex v
forall a. a -> a -> Complex a
:+ Scalar v
Scalar (Complex v)
sScalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^v
v

instance (RealFloat v, InnerSpace v)
     => InnerSpace (Complex v) where
  (v
u :+ v
v) <.> :: Complex v -> Complex v -> Scalar (Complex v)
<.> (v
u' :+ v
v') = (v
u v -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
<.> v
u') Scalar v -> Scalar v -> Scalar v
forall v. AdditiveGroup v => v -> v -> v
^+^ (v
v v -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
<.> v
v')

-- Hm.  The 'RealFloat' constraint is unfortunate here.  It's due to a
-- questionable decision to place 'RealFloat' into the definition of the
-- 'Complex' /type/, rather than in functions and instances as needed.

-- instance (VectorSpace u,VectorSpace v, s ~ Scalar u, s ~ Scalar v)
--          => VectorSpace (u,v) where
--   type Scalar (u,v) = Scalar u
--   s *^ (u,v) = (s*^u,s*^v)

instance ( VectorSpace u, s ~ Scalar u
         , VectorSpace v, s ~ Scalar v )
      => VectorSpace (u,v) where
  type Scalar (u,v) = Scalar u
  Scalar (u, v)
s *^ :: Scalar (u, v) -> (u, v) -> (u, v)
*^ (u
u,v
v) = (Scalar u
Scalar (u, v)
sScalar u -> u -> u
forall v. VectorSpace v => Scalar v -> v -> v
*^u
u,Scalar v
Scalar (u, v)
sScalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^v
v)

instance ( InnerSpace u, s ~ Scalar u
         , InnerSpace v, s ~ Scalar v )
    => InnerSpace (u,v) where
  (u
u,v
v) <.> :: (u, v) -> (u, v) -> Scalar (u, v)
<.> (u
u',v
v') = (u
u u -> u -> Scalar u
forall v. InnerSpace v => v -> v -> Scalar v
<.> u
u') s -> s -> s
forall v. AdditiveGroup v => v -> v -> v
^+^ (v
v v -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
<.> v
v')

instance ( VectorSpace u, s ~ Scalar u
         , VectorSpace v, s ~ Scalar v
         , VectorSpace w, s ~ Scalar w )
    => VectorSpace (u,v,w) where
  type Scalar (u,v,w) = Scalar u
  Scalar (u, v, w)
s *^ :: Scalar (u, v, w) -> (u, v, w) -> (u, v, w)
*^ (u
u,v
v,w
w) = (Scalar u
Scalar (u, v, w)
sScalar u -> u -> u
forall v. VectorSpace v => Scalar v -> v -> v
*^u
u,Scalar v
Scalar (u, v, w)
sScalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^v
v,Scalar w
Scalar (u, v, w)
sScalar w -> w -> w
forall v. VectorSpace v => Scalar v -> v -> v
*^w
w)

instance ( InnerSpace u, s ~ Scalar u
         , InnerSpace v, s ~ Scalar v
         , InnerSpace w, s ~ Scalar w )
    => InnerSpace (u,v,w) where
  (u
u,v
v,w
w) <.> :: (u, v, w) -> (u, v, w) -> Scalar (u, v, w)
<.> (u
u',v
v',w
w') = u
uu -> u -> Scalar u
forall v. InnerSpace v => v -> v -> Scalar v
<.>u
u' s -> s -> s
forall v. AdditiveGroup v => v -> v -> v
^+^ v
vv -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
<.>v
v' s -> s -> s
forall v. AdditiveGroup v => v -> v -> v
^+^ w
ww -> w -> Scalar w
forall v. InnerSpace v => v -> v -> Scalar v
<.>w
w'

instance ( VectorSpace u, s ~ Scalar u
         , VectorSpace v, s ~ Scalar v
         , VectorSpace w, s ~ Scalar w
         , VectorSpace x, s ~ Scalar x )
    => VectorSpace (u,v,w,x) where
  type Scalar (u,v,w,x) = Scalar u
  Scalar (u, v, w, x)
s *^ :: Scalar (u, v, w, x) -> (u, v, w, x) -> (u, v, w, x)
*^ (u
u,v
v,w
w,x
x) = (Scalar u
Scalar (u, v, w, x)
sScalar u -> u -> u
forall v. VectorSpace v => Scalar v -> v -> v
*^u
u,Scalar v
Scalar (u, v, w, x)
sScalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^v
v,Scalar w
Scalar (u, v, w, x)
sScalar w -> w -> w
forall v. VectorSpace v => Scalar v -> v -> v
*^w
w,Scalar x
Scalar (u, v, w, x)
sScalar x -> x -> x
forall v. VectorSpace v => Scalar v -> v -> v
*^x
x)

instance ( InnerSpace u, s ~ Scalar u
         , InnerSpace v, s ~ Scalar v
         , InnerSpace w, s ~ Scalar w
         , InnerSpace x, s ~ Scalar x )
    => InnerSpace (u,v,w,x) where
  (u
u,v
v,w
w,x
x) <.> :: (u, v, w, x) -> (u, v, w, x) -> Scalar (u, v, w, x)
<.> (u
u',v
v',w
w',x
x') = u
uu -> u -> Scalar u
forall v. InnerSpace v => v -> v -> Scalar v
<.>u
u' s -> s -> s
forall v. AdditiveGroup v => v -> v -> v
^+^ v
vv -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
<.>v
v' s -> s -> s
forall v. AdditiveGroup v => v -> v -> v
^+^ w
ww -> w -> Scalar w
forall v. InnerSpace v => v -> v -> Scalar v
<.>w
w' s -> s -> s
forall v. AdditiveGroup v => v -> v -> v
^+^ x
xx -> x -> Scalar x
forall v. InnerSpace v => v -> v -> Scalar v
<.>x
x'


-- 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
  *^ :: Scalar (Maybe v) -> Maybe v -> Maybe v
(*^) Scalar (Maybe v)
s = (v -> v) -> Maybe v -> Maybe v
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Scalar v
Scalar (Maybe v)
s Scalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^)

-- instance VectorSpace v => VectorSpace (a -> v) where
--   type Scalar (a -> v) = Scalar v
--   (*^) s = fmap (s *^)

-- No 'InnerSpace' instance for @a -> v@.

-- Or the following definition, which is useful for the higher-order
-- shading dsel in Shady (borrowed from Vertigo).

instance VectorSpace v => VectorSpace (a -> v) where
  type Scalar (a -> v) = a -> Scalar v
  *^ :: Scalar (a -> v) -> (a -> v) -> a -> v
(*^) = (Scalar v -> v -> v) -> (a -> Scalar v) -> (a -> v) -> a -> v
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Scalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
(*^)

instance InnerSpace v => InnerSpace (a -> v) where
  <.> :: (a -> v) -> (a -> v) -> Scalar (a -> v)
(<.>) = (v -> v -> Scalar v) -> (a -> v) -> (a -> v) -> a -> Scalar v
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 v -> v -> Scalar v
forall v. InnerSpace v => v -> v -> Scalar v
(<.>)



instance (HasTrie a, VectorSpace v) => VectorSpace (a :->: v) where
  type Scalar (a :->: v) = Scalar v
  *^ :: Scalar (a :->: v) -> (a :->: v) -> a :->: v
(*^) Scalar (a :->: v)
s = (v -> v) -> (a :->: v) -> a :->: v
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Scalar v
Scalar (a :->: v)
s Scalar v -> v -> v
forall v. VectorSpace v => Scalar v -> v -> v
*^)



instance InnerSpace a => InnerSpace (Maybe a) where
  -- dotting with zero (vector) yields zero (scalar)
  Maybe a
Nothing <.> :: Maybe a -> Maybe a -> Scalar (Maybe a)
<.> Maybe a
_     = Scalar (Maybe a)
forall v. AdditiveGroup v => v
zeroV
  Maybe a
_ <.> Maybe a
Nothing     = Scalar (Maybe a)
forall v. AdditiveGroup v => v
zeroV
  Just a
u <.> Just a
v = a
u a -> a -> Scalar a
forall v. InnerSpace v => v -> v -> Scalar v
<.> a
v

--   mu <.> mv = fromMaybe zeroV (liftA2 (<.>) mu mv)

--   (<.>) = (fmap.fmap) (fromMaybe zeroV) (liftA2 (<.>))


instance VectorSpace a => VectorSpace (Gnrx.Rec0 a s) where
  type Scalar (Gnrx.Rec0 a s) = Scalar a
  Scalar (Rec0 a s)
μ *^ :: Scalar (Rec0 a s) -> Rec0 a s -> Rec0 a s
*^ Gnrx.K1 a
v = a -> Rec0 a s
forall k i c (p :: k). c -> K1 i c p
Gnrx.K1 (a -> Rec0 a s) -> a -> Rec0 a s
forall a b. (a -> b) -> a -> b
$ Scalar a
Scalar (Rec0 a s)
μScalar a -> a -> a
forall v. VectorSpace v => Scalar v -> v -> v
*^a
v
  {-# INLINE (*^) #-}
instance VectorSpace (f p) => VectorSpace (Gnrx.M1 i c f p) where
  type Scalar (Gnrx.M1 i c f p) = Scalar (f p)
  Scalar (M1 i c f p)
μ *^ :: Scalar (M1 i c f p) -> M1 i c f p -> M1 i c f p
*^ Gnrx.M1 f p
v = f p -> M1 i c f p
forall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f p
Gnrx.M1 (f p -> M1 i c f p) -> f p -> M1 i c f p
forall a b. (a -> b) -> a -> b
$ Scalar (f p)
Scalar (M1 i c f p)
μScalar (f p) -> f p -> f p
forall v. VectorSpace v => Scalar v -> v -> v
*^f p
v
  {-# INLINE (*^) #-}
instance (VectorSpace (f p), VectorSpace (g p), Scalar (f p) ~ Scalar (g p))
         => VectorSpace ((f :*: g) p) where
  type Scalar ((f:*:g) p) = Scalar (f p)
  Scalar ((:*:) f g p)
μ *^ :: Scalar ((:*:) f g p) -> (:*:) f g p -> (:*:) f g p
*^ (f p
x:*:g p
y) = Scalar (f p)
Scalar ((:*:) f g p)
μScalar (f p) -> f p -> f p
forall v. VectorSpace v => Scalar v -> v -> v
*^f p
x f p -> g p -> (:*:) f g p
forall k (f :: k -> *) (g :: k -> *) (p :: k).
f p -> g p -> (:*:) f g p
:*: Scalar (g p)
Scalar ((:*:) f g p)
μScalar (g p) -> g p -> g p
forall v. VectorSpace v => Scalar v -> v -> v
*^g p
y
  {-# INLINE (*^) #-}

instance InnerSpace a => InnerSpace (Gnrx.Rec0 a s) where
  Gnrx.K1 a
v <.> :: Rec0 a s -> Rec0 a s -> Scalar (Rec0 a s)
<.> Gnrx.K1 a
w = a
va -> a -> Scalar a
forall v. InnerSpace v => v -> v -> Scalar v
<.>a
w
  {-# INLINE (<.>) #-}
instance InnerSpace (f p) => InnerSpace (Gnrx.M1 i c f p) where
  Gnrx.M1 f p
v <.> :: M1 i c f p -> M1 i c f p -> Scalar (M1 i c f p)
<.> Gnrx.M1 f p
w = f p
vf p -> f p -> Scalar (f p)
forall v. InnerSpace v => v -> v -> Scalar v
<.>f p
w
  {-# INLINE (<.>) #-}
instance ( InnerSpace (f p), InnerSpace (g p)
         , Scalar (f p) ~ Scalar (g p), Num (Scalar (f p)) )
         => InnerSpace ((f :*: g) p) where
  (f p
x:*:g p
y) <.> :: (:*:) f g p -> (:*:) f g p -> Scalar ((:*:) f g p)
<.> (f p
ξ:*:g p
υ) = f p
xf p -> f p -> Scalar (f p)
forall v. InnerSpace v => v -> v -> Scalar v
<.>f p
ξ Scalar (g p) -> Scalar (g p) -> Scalar (g p)
forall a. Num a => a -> a -> a
+ g p
yg p -> g p -> Scalar (g p)
forall v. InnerSpace v => v -> v -> Scalar v
<.>g p
υ
  {-# INLINE (<.>) #-}