-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A playground of sparse linear algebra primitives using Morton ordering
--
-- A playground of sparse linear algebra primitives using Morton ordering
--
-- The design of this library is described in the series "Revisiting
-- Matrix Multiplication" on FP Complete's School of Haskell.
--
--
-- https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/
@package sparse
@version 0.7.0.1
-- | Keys in Morton order
--
-- This module provides combinators for shuffling together the bits of
-- two key components to get a key that is based on their interleaved
-- bits.
--
-- See http://en.wikipedia.org/wiki/Z-order_curve for more
-- information about Morton order.
--
-- How to perform the comparison without interleaving is described in
--
--
-- https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-2
module Sparse.Matrix.Internal.Key
-- | Key i j logically orders the keys as if the bits of the keys
-- i and j were interleaved. This is equivalent to
-- storing the keys in "Morton Order".
--
--
-- >>> Key 100 200 ^. _1
-- 100
--
--
--
-- >>> Key 100 200 ^. _2
-- 200
--
data Key
Key :: {-# UNPACK #-} !Word -> {-# UNPACK #-} !Word -> Key
-- | Swaps the key components around
--
--
-- >>> swap (Key 100 200)
-- Key 200 100
--
swap :: Key -> Key
-- | compare the position of the most significant bit of two words
--
--
-- >>> compares 4 7
-- EQ
--
--
--
-- >>> compares 7 9
-- LT
--
--
--
-- >>> compares 9 7
-- GT
--
compares :: Word -> Word -> Ordering
-- | lts a b returns True when the position of the
-- most significant bit of a is less than the position of the
-- most signficant bit of b.
--
--
-- >>> lts 4 10
-- True
--
--
--
-- >>> lts 4 7
-- False
--
--
--
-- >>> lts 7 8
-- True
--
lts :: Word -> Word -> Bool
-- | les a b returns True when the position of the
-- most significant bit of a is less than or equal to the
-- position of the most signficant bit of b.
--
--
-- >>> les 4 10
-- True
--
--
--
-- >>> les 4 7
-- True
--
--
--
-- >>> les 7 4
-- True
--
--
--
-- >>> les 10 4
-- False
--
les :: Word -> Word -> Bool
-- | eqs a b returns True when the position of the
-- most significant bit of a is equal to the position of the
-- most signficant bit of b.
--
--
-- >>> eqs 4 7
-- True
--
--
--
-- >>> eqs 4 8
-- False
--
--
--
-- >>> eqs 7 4
-- True
--
--
--
-- >>> eqs 8 4
-- False
--
eqs :: Word -> Word -> Bool
-- | nes a b returns True when the position of the
-- most significant bit of a is not equal to the position of the
-- most signficant bit of b.
--
--
-- >>> nes 4 7
-- False
--
--
--
-- >>> nes 4 8
-- True
--
--
--
-- >>> nes 7 4
-- False
--
--
--
-- >>> nes 8 4
-- True
--
nes :: Word -> Word -> Bool
-- | gts a b returns True when the position of the
-- most significant bit of a is greater than or equal to the
-- position of the most signficant bit of b.
--
--
-- >>> ges 4 10
-- False
--
--
--
-- >>> ges 4 7
-- True
--
--
--
-- >>> ges 7 4
-- True
--
--
--
-- >>> ges 10 4
-- True
--
ges :: Word -> Word -> Bool
-- | gts a b returns True when the position of the
-- most significant bit of a is greater than to the position of
-- the most signficant bit of b.
--
--
-- >>> gts 4 10
-- False
--
--
--
-- >>> gts 4 7
-- False
--
--
--
-- >>> gts 7 4
-- False
--
--
--
-- >>> gts 10 4
-- True
--
gts :: Word -> Word -> Bool
instance Show Key
instance Read Key
instance Eq Key
instance Vector Vector Key
instance MVector MVector Key
instance Unbox Key
instance (a ~ Word, b ~ Word) => Field2 Key Key a b
instance (a ~ Word, b ~ Word) => Field1 Key Key a b
instance Ord Key
module Sparse.Matrix.Internal.Vectored
class (Vector (Vec a) a, Monoid (Vec a a)) => Vectored a where type family Vec a :: * -> * type instance Vec a = Vector
type Vector a = Vec a a
data V_Complex :: * -> *
V_Complex :: {-# UNPACK #-} !Int -> !(Vector a) -> !(Vector a) -> V_Complex (Complex a)
data MV_Complex :: * -> * -> *
MV_Complex :: {-# UNPACK #-} !Int -> !(Mutable (Vec a) s a) -> !(Mutable (Vec a) s a) -> MV_Complex s (Complex a)
instance (Vectored a, RealFloat a) => Vectored (Complex a)
instance (Vectored a, RealFloat a, b ~ Complex a) => Monoid (V_Complex b)
instance (Vectored a, RealFloat a, Eq a, b ~ Complex a) => Eq (V_Complex b)
instance (Vectored a, RealFloat a, Read a, b ~ Complex a) => Read (V_Complex b)
instance (Vectored a, RealFloat a, Show a, b ~ Complex a) => Show (V_Complex b)
instance (Vectored a, RealFloat a) => Vector V_Complex (Complex a)
instance (Vectored a, RealFloat a) => MVector MV_Complex (Complex a)
instance Vectored Integer
instance Vectored Word64
instance Vectored Word32
instance Vectored Word16
instance Vectored Word8
instance Vectored Word
instance Vectored Key
instance Vectored Int64
instance Vectored Int32
instance Vectored Int16
instance Vectored Int8
instance Vectored Int
instance Vectored Float
instance Vectored Double
instance Vectored ()
-- | Bootstrapped catenable non-empty pairing heaps as described in
--
--
-- https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-5
module Sparse.Matrix.Internal.Heap
-- | Bootstrapped catenable non-empty pairing heaps
data Heap a
Heap :: {-# UNPACK #-} !Key -> a -> [Heap a] -> [Heap a] -> [Heap a] -> Heap a
-- | Append two heaps where we know every key in the first occurs before
-- every key in the second
--
--
-- >>> head $ singleton (Key 1 1) 1 `fby` singleton (Key 2 2) 2
-- (Key 1 1,1)
--
fby :: Heap a -> Heap a -> Heap a
-- | Interleave two heaps making a new Heap
--
--
-- >>> head $ singleton (Key 1 1) 1 `mix` singleton (Key 2 2) 2
-- (Key 1 1,1)
--
mix :: Heap a -> Heap a -> Heap a
-- |
-- >>> singleton (Key 1 1) 1
-- Heap (Key 1 1) 1 [] [] []
--
singleton :: Key -> a -> Heap a
-- |
-- >>> head $ singleton (Key 1 1) 1
-- (Key 1 1,1)
--
head :: Heap a -> (Key, a)
-- |
-- >>> tail $ singleton (Key 1 1) 1
-- Nothing
--
tail :: Heap a -> Maybe (Heap a)
-- | Build a Heap from a jumbled up list of elements.
fromList :: [(Key, a)] -> Heap a
-- | Build a Heap from an list of elements that must be in strictly
-- ascending Morton order.
fromAscList :: [(Key, a)] -> Heap a
-- | Convert a Heap into a Stream folding together values
-- with identical keys using the supplied addition operator.
streamHeapWith :: Monad m => (a -> a -> a) -> Maybe (Heap a) -> Stream m (Key, a)
-- | Convert a Heap into a Stream folding together values
-- with identical keys using the supplied addition operator that is
-- allowed to return a sparse 0, by returning Nothing.
streamHeapWith0 :: Monad m => (a -> a -> Maybe a) -> Maybe (Heap a) -> Stream m (Key, a)
-- | This is an internal Heap fusion combinator used to multiply on
-- the right by a singleton Key/value pair.
timesSingleton :: (a -> b -> c) -> Stream Id (Key, a) -> Key -> b -> Maybe (Heap c)
-- | This is an internal Heap fusion combinator used to multiply on
-- the right by a singleton Key/value pair.
singletonTimes :: (a -> b -> c) -> Key -> a -> Stream Id (Key, b) -> Maybe (Heap c)
instance Show a => Show (Heap a)
instance Read a => Read (Heap a)
instance TraversableWithIndex Key Heap
instance Traversable Heap
instance FoldableWithIndex Key Heap
instance Foldable Heap
instance FunctorWithIndex Key Heap
instance Functor Heap
-- | Matrix stream fusion internals
module Sparse.Matrix.Internal.Fusion
-- | This is the internal stream fusion combinator used to merge streams
-- for addition.
mergeStreamsWith :: Monad m => (a -> a -> a) -> Stream m (Key, a) -> Stream m (Key, a) -> Stream m (Key, a)
-- | This is the internal stream fusion combinator used to merge streams
-- for addition.
--
-- This form permits cancellative addition.
mergeStreamsWith0 :: Monad m => (a -> a -> Maybe a) -> Stream m (Key, a) -> Stream m (Key, a) -> Stream m (Key, a)
-- | Sparse Matrices in Morton order
--
-- The design of this library is described in the series "Revisiting
-- Matrix Multiplication" on FP Complete's School of Haskell.
--
--
-- https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/
module Sparse.Matrix
data Mat a
Mat :: {-# UNPACK #-} !Int -> !(Vector Word) -> !(Vector Word) -> !(Vector a) -> Mat a
-- | Key i j logically orders the keys as if the bits of the keys
-- i and j were interleaved. This is equivalent to
-- storing the keys in "Morton Order".
--
--
-- >>> Key 100 200 ^. _1
-- 100
--
--
--
-- >>> Key 100 200 ^. _2
-- 200
--
data Key
Key :: {-# UNPACK #-} !Word -> {-# UNPACK #-} !Word -> Key
-- | Build a sparse matrix.
fromList :: Vectored a => [(Key, a)] -> Mat a
-- | singleton makes a matrix with a singleton value at a given
-- location
singleton :: Vectored a => Key -> a -> Mat a
-- | Transpose a matrix
transpose :: Vectored a => Mat a -> Mat a
-- | ident n makes an n x n identity matrix
--
--
-- >>> ident 4
-- fromList [(Key 0 0,1),(Key 1 1,1),(Key 2 2,1),(Key 3 3,1)]
--
ident :: (Vectored a, Num a) => Int -> Mat a
-- | The empty matrix
--
--
-- >>> empty :: Mat Int
-- fromList []
--
empty :: Vectored a => Mat a
-- | Count the number of non-zero entries in the matrix
--
--
-- >>> size (ident 4)
-- 4
--
size :: Mat a -> Int
-- |
-- >>> null (empty :: Mat Int)
-- True
--
null :: Mat a -> Bool
class (Vectored a, Num a) => Eq0 a where isZero = (0 ==) nonZero f a b = case f a b of { c | isZero c -> Nothing | otherwise -> Just c } addMats = addWith0 $ nonZero (+) addHeap = streamHeapWith0 $ nonZero (+)
isZero :: Eq0 a => a -> Bool
nonZero :: Eq0 a => (x -> y -> a) -> x -> y -> Maybe a
addMats :: Eq0 a => Mat a -> Mat a -> Mat a
addHeap :: Eq0 a => Maybe (Heap a) -> Stream (Key, a)
-- | Merge two matrices where the indices coincide into a new matrix. This
-- provides for generalized addition, but where the summation of two
-- non-zero entries is necessarily non-zero.
addWith :: Vectored a => (a -> a -> a) -> Mat a -> Mat a -> Mat a
-- | Multiply two matrices using the specified multiplication and addition
-- operation.
multiplyWith :: Vectored a => (a -> a -> a) -> (Maybe (Heap a) -> Stream (Key, a)) -> Mat a -> Mat a -> Mat a
class (Vector (Vec a) a, Monoid (Vec a a)) => Vectored a where type family Vec a :: * -> * type instance Vec a = Vector
-- | bundle up the matrix in a form suitable for vector-algorithms
_Mat :: Vectored a => Iso' (Mat a) (Vector Vector (Vec a) (Key, a))
-- | Access the keys of a matrix
keys :: Lens' (Mat a) (Vector Key)
-- | Access the keys of a matrix
values :: Lens (Mat a) (Mat b) (Vector a) (Vector b)
instance (Vectored a, Ord (Vector a)) => Ord (Mat a)
instance (Vectored a, Eq (Vector a)) => Eq (Mat a)
instance (Vectored a, Eq0 a) => Num (Mat a)
instance (Vectored a, Eq0 a) => Eq0 (Mat a)
instance Vectored a => Vectored (Mat a)
instance (Applicative f, Vectored a) => Ixed f (Mat a)
instance (Functor f, Contravariant f, Vectored a) => Contains f (Mat a)
instance (Applicative f, Vectored a, a ~ b) => Each f (Mat a) (Mat b) a b
instance NFData (Vector a) => NFData (Mat a)
instance (Vectored a, Read a) => Read (Mat a)
instance (Vectored a, Show a) => Show (Mat a)
instance (RealFloat a, Eq0 a) => Eq0 (Complex a)
instance Eq0 Double
instance Eq0 Float
instance Eq0 Integer
instance Eq0 Word
instance Eq0 Int