-- |
-- Module      : Data.VectorSpace.Free.Sequence
-- Copyright   : (c) Justus Sagemüller 2016
-- License     : GPL v3
-- 
-- Maintainer  : (@) jsag $ hvl.no
-- Stability   : experimental
-- Portability : portable
-- 
{-# LANGUAGE TypeFamilies            #-}
{-# LANGUAGE FlexibleInstances       #-}
{-# LANGUAGE FlexibleContexts        #-}
{-# LANGUAGE ConstrainedClassMethods #-}
{-# LANGUAGE StandaloneDeriving      #-}
{-# LANGUAGE DeriveFunctor           #-}

module Data.VectorSpace.Free.Sequence (
                             Sequence, BoxSequence, GSequence (..), minimumChunkSize
                             ) where

import Data.VectorSpace.Free.FiniteSupportedSequence

import Data.AffineSpace
import Data.VectorSpace
import Data.Basis

import qualified Data.Foldable as Foldable

import qualified Data.Vector as Arr
import qualified Data.Vector.Unboxed as UArr
import qualified Data.Vector.Generic as GArr
import qualified Data.Vector.Generic.Mutable as MArr

import GHC.Exts (IsList(..))




-- | The space of possibly-infinite sequences, isomorphic to the space of all lists
--   but implemented more efficiently (with exponentially-growing chunks of unboxed data,
--   so the overhead is amortised). In other words, this is a type of spine-lazy
--   but element-strict arrays.
-- 
--   This space is dual to 'FinSuppSeq', which is completely strict.
data GSequence array n
    = Sequence {
        GSequence array n -> array n
sequenceHeads :: !(array n)
            -- ^ Length must be at most 'minimumChunkSize' in the outer constructor and
            --   double in each deeper layer. (Specification subject to future change!)
            --   If the length at depth 𝑑 is less than 2^𝑑, the remaining entries are
            --   treated as zeroes.
      , GSequence array n -> GSequence array n
sequenceRemain :: GSequence array n
      }
    | SoloChunk {
        GSequence array n -> Int
chunkOffset :: !Int
      , GSequence array n -> array n
soloChunk :: !(array n)
            -- ^ Length plus offset must be at most 'minimumChunkSize' if this is
            --   the outer constructor and can double in each deeper layer.
      }
    

type Sequence = GSequence UArr.Vector
type BoxSequence = GSequence Arr.Vector

deriving instance Functor BoxSequence

reboxSequence :: (GArr.Vector a n, GArr.Vector b n) => GSequence a n -> GSequence b n
reboxSequence :: GSequence a n -> GSequence b n
reboxSequence (SoloChunk Int
o a n
c) = Int -> b n -> GSequence b n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
o (b n -> GSequence b n) -> b n -> GSequence b n
forall a b. (a -> b) -> a -> b
$ a n -> b n
forall (v :: * -> *) a (w :: * -> *).
(Vector v a, Vector w a) =>
v a -> w a
Arr.convert a n
c
reboxSequence (Sequence a n
h GSequence a n
r) = b n -> GSequence b n -> GSequence b n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence (a n -> b n
forall (v :: * -> *) a (w :: * -> *).
(Vector v a, Vector w a) =>
v a -> w a
Arr.convert a n
h) (GSequence b n -> GSequence b n) -> GSequence b n -> GSequence b n
forall a b. (a -> b) -> a -> b
$ GSequence a n -> GSequence b n
forall (a :: * -> *) n (b :: * -> *).
(Vector a n, Vector b n) =>
GSequence a n -> GSequence b n
reboxSequence GSequence a n
r

mapSequence :: (UArr.Unbox n, UArr.Unbox m) => (n -> m) -> Sequence n -> Sequence m
mapSequence :: (n -> m) -> Sequence n -> Sequence m
mapSequence n -> m
f (SoloChunk Int
i₀ Vector n
chunk) = Int -> Vector m -> Sequence m
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
i₀ ((n -> m) -> Vector n -> Vector m
forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
UArr.map n -> m
f Vector n
chunk)
mapSequence n -> m
f (Sequence Vector n
hd Sequence n
rm) = Vector m -> Sequence m -> Sequence m
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence ((n -> m) -> Vector n -> Vector m
forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
UArr.map n -> m
f Vector n
hd) ((n -> m) -> Sequence n -> Sequence m
forall n m.
(Unbox n, Unbox m) =>
(n -> m) -> Sequence n -> Sequence m
mapSequence n -> m
f Sequence n
rm)

{-# INLINE liftU2Seq #-}
liftU2Seq :: UArr.Unbox n => n -> (n -> n -> n) -> Sequence n -> Sequence n -> Sequence n
liftU2Seq :: n -> (n -> n -> n) -> Sequence n -> Sequence n -> Sequence n
liftU2Seq n
defaultVal n -> n -> n
f (Sequence Vector n
hu Sequence n
ru) (Sequence Vector n
hv Sequence n
rv)
  = (Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
`Sequence`n -> (n -> n -> n) -> Sequence n -> Sequence n -> Sequence n
forall n.
Unbox n =>
n -> (n -> n -> n) -> Sequence n -> Sequence n -> Sequence n
liftU2Seq n
defaultVal n -> n -> n
f Sequence n
ru Sequence n
rv) (Vector n -> Sequence n) -> Vector n -> Sequence n
forall a b. (a -> b) -> a -> b
$ case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
lu Int
lv of
-- Adapted from:
-- http://hackage.haskell.org/package/linear-1.20.5/docs/src/Linear.Vector.html#line-200 
    Ordering
LT | Int
lu Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0   -> Vector n
hv
       | Bool
otherwise -> (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
           (\ MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
luInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hu Int
i)
                                               (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hv Int
i)) Vector n
hv
    Ordering
EQ -> (n -> n -> n) -> Vector n -> Vector n -> Vector n
forall a b c.
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector a -> Vector b -> Vector c
UArr.zipWith n -> n -> n
f Vector n
hu Vector n
hv
    Ordering
GT | Int
lv Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0   -> Vector n
hu
       | Bool
otherwise -> (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
            (\ MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
lvInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hu Int
i)
                                               (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hv Int
i)) Vector n
hu
 where lu :: Int
lu = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
hu
       lv :: Int
lv = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
hv
liftU2Seq n
defaultVal n -> n -> n
f (Sequence Vector n
hu Sequence n
ru) (SoloChunk Int
ov Vector n
cv)
   | Int
lu Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0, Int
lv Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0  = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence Vector n
forall a. Unbox a => Vector a
UArr.empty Sequence n
ru
   | Int
lu Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0      = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence (Int -> n -> Vector n
forall a. Unbox a => Int -> a -> Vector a
UArr.replicate Int
ov n
defaultVal Vector n -> Vector n -> Vector n
forall a. Unbox a => Vector a -> Vector a -> Vector a
UArr.++ Vector n
cv) Sequence n
ru
   | Int
lv Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0      = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence Vector n
hu Sequence n
ru
   | Int
lu Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
lvInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
ov  = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence ((forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
                                (\MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
lvInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                                   \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
ov)
                                            (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hu (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
ov))
                                                (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cv Int
i)) Vector n
hu)
                             Sequence n
ru
   | Int
ov Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0      = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence ((forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
                                (\MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
luInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                                   \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i
                                            (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hu Int
i)
                                                (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cv Int
i)) Vector n
cv)
                             Sequence n
ru
   | Bool
otherwise    = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence (Int -> Vector n -> Vector n
forall a. Unbox a => Int -> Vector a -> Vector a
UArr.take Int
ov Vector n
hu Vector n -> Vector n -> Vector n
forall a. Unbox a => Vector a -> Vector a -> Vector a
UArr.++ (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
                                (\MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
ov..Int
luInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                                   \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i
                                            (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hu Int
i)
                                                (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cv (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
ov))) Vector n
cv)
                             Sequence n
ru
 where lu :: Int
lu = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
hu
       lv :: Int
lv = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
cv
liftU2Seq n
defaultVal n -> n -> n
f (SoloChunk Int
ou Vector n
cu) (Sequence Vector n
hv Sequence n
rv)
   | Int
lu Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0, Int
lv Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0  = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence Vector n
forall a. Unbox a => Vector a
UArr.empty Sequence n
rv
   | Int
lu Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0      = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence Vector n
hv Sequence n
rv
   | Int
lv Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0      = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence (Int -> n -> Vector n
forall a. Unbox a => Int -> a -> Vector a
UArr.replicate Int
ou n
defaultVal Vector n -> Vector n -> Vector n
forall a. Unbox a => Vector a -> Vector a -> Vector a
UArr.++ Vector n
cu) Sequence n
rv
   | Int
luInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
ou Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
lv  = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence ((forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
                                (\MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
luInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                                   \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
ou)
                                            (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cu Int
i)
                                                (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hv (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
ou))) Vector n
hv)
                             Sequence n
rv
   | Int
ou Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0      = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence ((forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
                                (\MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
lvInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                                   \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i
                                            (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cu Int
i)
                                                (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hv Int
i)) Vector n
cu)
                             Sequence n
rv
   | Bool
otherwise    = Vector n -> Sequence n -> Sequence n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence (Int -> Vector n -> Vector n
forall a. Unbox a => Int -> Vector a -> Vector a
UArr.take Int
ou Vector n
hv Vector n -> Vector n -> Vector n
forall a. Unbox a => Vector a -> Vector a -> Vector a
UArr.++ (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
                                (\MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
ou..Int
lvInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                                   \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i
                                            (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cu (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
ou))
                                                (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
hv Int
i)) Vector n
cu)
                             Sequence n
rv
 where lu :: Int
lu = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
cu
       lv :: Int
lv = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
hv
liftU2Seq n
_ n -> n -> n
f (SoloChunk Int
ou Vector n
cu) (SoloChunk Int
ov Vector n
cv)
   | Int
lu Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0  = Int -> Vector n -> Sequence n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
ov Vector n
cv
   | Int
lv Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0  = Int -> Vector n -> Sequence n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
ou Vector n
cu
   | Int
ou Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
ov, Int
ouInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lu Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
ovInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lv
        = Int -> Vector n -> Sequence n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
ov (Vector n -> Sequence n) -> Vector n -> Sequence n
forall a b. (a -> b) -> a -> b
$ (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
           (\ MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
luInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cu Int
i)
                                               (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cv (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
δo))) Vector n
cv
   | Int
ou Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
ov, Int
ouInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lu Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
ovInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lv
        = Int -> Vector n -> Sequence n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
ou (Vector n -> Sequence n) -> Vector n -> Sequence n
forall a b. (a -> b) -> a -> b
$ (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
           (\ MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
0..Int
lvInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cu (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
δo))
                                               (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cv Int
i)) Vector n
cu
   | Int
ou Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
ov
        = Int -> Vector n -> Sequence n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
ov (Vector n -> Sequence n) -> Vector n -> Sequence n
forall a b. (a -> b) -> a -> b
$ Int -> Vector n -> Vector n
forall a. Unbox a => Int -> Vector a -> Vector a
UArr.take Int
δo Vector n
cv Vector n -> Vector n -> Vector n
forall a. Unbox a => Vector a -> Vector a -> Vector a
UArr.++ (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
           (\ MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [Int
δo..Int
lvInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cu (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
δo))
                                               (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cv Int
i)) Vector n
cu
   | Int
ou Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
ov
        = Int -> Vector n -> Sequence n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
ou (Vector n -> Sequence n) -> Vector n -> Sequence n
forall a b. (a -> b) -> a -> b
$ Int -> Vector n -> Vector n
forall a. Unbox a => Int -> Vector a -> Vector a
UArr.take (-Int
δo) Vector n
cu Vector n -> Vector n -> Vector n
forall a. Unbox a => Vector a -> Vector a -> Vector a
UArr.++ (forall s. MVector s n -> ST s ()) -> Vector n -> Vector n
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
UArr.modify
           (\ MVector s n
w -> [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
Foldable.forM_ [-Int
δo..Int
luInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$
                \Int
i -> MVector (PrimState (ST s)) n -> Int -> n -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MArr.unsafeWrite MVector s n
MVector (PrimState (ST s)) n
w Int
i (n -> ST s ()) -> n -> ST s ()
forall a b. (a -> b) -> a -> b
$ n -> n -> n
f (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cu Int
i)
                                               (Vector n -> Int -> n
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector n
cv (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
δo))) Vector n
cv
 where lu :: Int
lu = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
cu
       lv :: Int
lv = Vector n -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector n
cv
       δo :: Int
δo = Int
ouInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
ov


instance (Num n, UArr.Unbox n) => AffineSpace (Sequence n) where
  type Diff (Sequence n) = Sequence n
  .-. :: Sequence n -> Sequence n -> Diff (Sequence n)
(.-.) = Sequence n -> Sequence n -> Diff (Sequence n)
forall v. AdditiveGroup v => v -> v -> v
(^-^)
  .+^ :: Sequence n -> Diff (Sequence n) -> Sequence n
(.+^) = Sequence n -> Diff (Sequence n) -> Sequence n
forall v. AdditiveGroup v => v -> v -> v
(^+^)
  
instance (Num n, UArr.Unbox n) => AdditiveGroup (Sequence n) where
  zeroV :: Sequence n
zeroV = Int -> Vector n -> Sequence n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
0 Vector n
forall a. Unbox a => Vector a
UArr.empty
  ^+^ :: Sequence n -> Sequence n -> Sequence n
(^+^) = n -> (n -> n -> n) -> Sequence n -> Sequence n -> Sequence n
forall n.
Unbox n =>
n -> (n -> n -> n) -> Sequence n -> Sequence n -> Sequence n
liftU2Seq n
1 n -> n -> n
forall a. Num a => a -> a -> a
(+)
  negateV :: Sequence n -> Sequence n
negateV = (n -> n) -> Sequence n -> Sequence n
forall n m.
(Unbox n, Unbox m) =>
(n -> m) -> Sequence n -> Sequence m
mapSequence n -> n
forall a. Num a => a -> a
negate
  
instance (Num n, UArr.Unbox n) => VectorSpace (Sequence n) where
  type Scalar (Sequence n) = n
  Scalar (Sequence n)
μ*^ :: Scalar (Sequence n) -> Sequence n -> Sequence n
*^Sequence n
v = (n -> n) -> Sequence n -> Sequence n
forall n m.
(Unbox n, Unbox m) =>
(n -> m) -> Sequence n -> Sequence m
mapSequence (n
Scalar (Sequence n)
μn -> n -> n
forall a. Num a => a -> a -> a
*) Sequence n
v

instance (Num n, UArr.Unbox n) => HasBasis (Sequence n) where
  type Basis (Sequence n) = Int
  basisValue :: Basis (Sequence n) -> Sequence n
basisValue = Int -> Int -> Sequence n
forall n. (Unbox n, Num n) => Int -> Int -> GSequence Vector n
bv Int
minimumChunkSize
   where bv :: Int -> Int -> GSequence Vector n
bv Int
chunkSize Int
i
          | Int
iInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<Int
chunkSize  = Int -> Vector n -> GSequence Vector n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
i (n -> Vector n
forall a. Unbox a => a -> Vector a
UArr.singleton n
1)
          | Bool
otherwise    = Vector n -> GSequence Vector n -> GSequence Vector n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence (Vector n
forall a. Unbox a => Vector a
UArr.empty) (GSequence Vector n -> GSequence Vector n)
-> GSequence Vector n -> GSequence Vector n
forall a b. (a -> b) -> a -> b
$ Int -> Int -> GSequence Vector n
bv (Int
chunkSizeInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
chunkSize)
  decompose :: Sequence n -> [(Basis (Sequence n), Scalar (Sequence n))]
decompose = [Int] -> [n] -> [(Int, n)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0..] ([n] -> [(Int, n)])
-> (Sequence n -> [n]) -> Sequence n -> [(Int, n)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Sequence n -> [n]
forall l. IsList l => l -> [Item l]
toList
  decompose' :: Sequence n -> Basis (Sequence n) -> Scalar (Sequence n)
decompose' = Int -> Sequence n -> Int -> n
forall b. (Num b, Unbox b) => Int -> GSequence Vector b -> Int -> b
dc Int
minimumChunkSize
   where dc :: Int -> GSequence Vector b -> Int -> b
dc Int
_ (SoloChunk Int
o Vector b
v) Int
i
           | Int
ir Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0              = b
0
           | Int
ir Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Vector b -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector b
v  = Vector b -> Int -> b
forall a. Unbox a => Vector a -> Int -> a
UArr.unsafeIndex Vector b
v Int
ir
           | Bool
otherwise           = b
0
          where ir :: Int
ir = Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
o
         dc Int
chunkSize (Sequence Vector b
h GSequence Vector b
r) Int
i
           | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
chunkSize  = b -> (b -> b) -> Maybe b -> b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe b
0 b -> b
forall a. a -> a
id (Maybe b -> b) -> Maybe b -> b
forall a b. (a -> b) -> a -> b
$ Vector b
h Vector b -> Int -> Maybe b
forall a. Unbox a => Vector a -> Int -> Maybe a
UArr.!? Int
i
           | Bool
otherwise      = Int -> GSequence Vector b -> Int -> b
dc (Int
chunkSizeInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) GSequence Vector b
r (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
chunkSize)

instance (UArr.Unbox n, Num n) => IsList (Sequence n) where
  type Item (Sequence n) = n
  fromListN :: Int -> [Item (Sequence n)] -> Sequence n
fromListN = Int -> Int -> [n] -> Sequence n
forall n. Unbox n => Int -> Int -> [n] -> GSequence Vector n
fln Int
minimumChunkSize
   where fln :: Int -> Int -> [n] -> GSequence Vector n
fln Int
chunkSize Int
l [n]
ns
           | Int
lInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
chunkSize  = let ([n]
h,[n]
r) = Int -> [n] -> ([n], [n])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
chunkSize [n]
ns
                            in Vector n -> GSequence Vector n -> GSequence Vector n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence ([n] -> Vector n
forall a. Unbox a => [a] -> Vector a
UArr.fromList [n]
h)
                                   (GSequence Vector n -> GSequence Vector n)
-> GSequence Vector n -> GSequence Vector n
forall a b. (a -> b) -> a -> b
$ Int -> Int -> [n] -> GSequence Vector n
fln (Int
chunkSizeInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
chunkSize) [n]
r
           | Bool
otherwise  = Int -> Vector n -> GSequence Vector n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
0 (Vector n -> GSequence Vector n) -> Vector n -> GSequence Vector n
forall a b. (a -> b) -> a -> b
$ [n] -> Vector n
forall a. Unbox a => [a] -> Vector a
UArr.fromList [n]
ns
  fromList :: [Item (Sequence n)] -> Sequence n
fromList = Int -> [n] -> Sequence n
forall n. Unbox n => Int -> [n] -> GSequence Vector n
fln Int
minimumChunkSize
   where fln :: Int -> [n] -> GSequence Vector n
fln Int
chunkSize [n]
ns
           | [n] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [n]
r     = Int -> Vector n -> GSequence Vector n
forall (array :: * -> *) n. Int -> array n -> GSequence array n
SoloChunk Int
0 (Vector n -> GSequence Vector n) -> Vector n -> GSequence Vector n
forall a b. (a -> b) -> a -> b
$ [n] -> Vector n
forall a. Unbox a => [a] -> Vector a
UArr.fromList [n]
ns
           | Bool
otherwise  = Vector n -> GSequence Vector n -> GSequence Vector n
forall (array :: * -> *) n.
array n -> GSequence array n -> GSequence array n
Sequence ([n] -> Vector n
forall a. Unbox a => [a] -> Vector a
UArr.fromList [n]
h)
                               (GSequence Vector n -> GSequence Vector n)
-> GSequence Vector n -> GSequence Vector n
forall a b. (a -> b) -> a -> b
$ Int -> [n] -> GSequence Vector n
fln (Int
chunkSizeInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) [n]
r
          where ([n]
h,[n]
r) = Int -> [n] -> ([n], [n])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
chunkSize [n]
ns
  toList :: Sequence n -> [Item (Sequence n)]
toList = Int -> Sequence n -> [n]
forall a. (Num a, Unbox a) => Int -> GSequence Vector a -> [a]
tl Int
minimumChunkSize
   where tl :: Int -> GSequence Vector a -> [a]
tl Int
_ (SoloChunk Int
o Vector a
c) = Int -> a -> [a]
forall a. Int -> a -> [a]
replicate Int
o a
0 [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ Vector a -> [Item (Vector a)]
forall l. IsList l => l -> [Item l]
toList Vector a
c
         tl Int
chunkSize (Sequence Vector a
h GSequence Vector a
r)
             = Vector a -> [Item (Vector a)]
forall l. IsList l => l -> [Item l]
toList Vector a
h [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ Int -> a -> [a]
forall a. Int -> a -> [a]
replicate (Int
chunkSize Int -> Int -> Int
forall a. Num a => a -> a -> a
- Vector a -> Int
forall a. Unbox a => Vector a -> Int
UArr.length Vector a
h) a
0
                  [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ Int -> GSequence Vector a -> [a]
tl (Int
chunkSizeInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) GSequence Vector a
r

instance (UArr.Unbox n, Show n, Num n) => Show (Sequence n) where
  show :: Sequence n -> String
show = (String
"fromList "String -> ShowS
forall a. [a] -> [a] -> [a]
++) ShowS -> (Sequence n -> String) -> Sequence n -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [n] -> String
forall a. Show a => a -> String
show ([n] -> String) -> (Sequence n -> [n]) -> Sequence n -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Sequence n -> [n]
forall l. IsList l => l -> [Item l]
toList



minimumChunkSize :: Int
minimumChunkSize :: Int
minimumChunkSize = Int
1