-- 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 describe in the following articles on FP
-- Complete's School of Haskell.
--
--
--
-- - https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication-part-1
--
-- - https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication-part-2
--
-- - https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication-part-3
--
-- - https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication-part-4
--
-- - https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication-part-5
--
@package sparse
@version 0.6
-- | 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
-- | 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
module Sparse.Matrix
data Mat v a
Mat :: {-# UNPACK #-} !Int -> !(Vector Word) -> !(Vector Word) -> !(v a) -> Mat v 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 :: Vector v a => [(Key, a)] -> Mat v a
-- | singleton makes a matrix with a singleton value at a given
-- location
singleton :: Vector v a => Key -> a -> Mat v a
-- | Transpose a matrix
transpose :: Vector v a => Mat v a -> Mat v a
-- | ident n makes an n x n identity matrix
--
--
-- >>> ident 4 :: Mat U.Vector Int
-- fromList [(Key 0 0,1),(Key 1 1,1),(Key 2 2,1),(Key 3 3,1)]
--
ident :: (Vector v a, Num a) => Int -> Mat v a
-- | The empty matrix
--
--
-- >>> empty :: Mat U.Vector Int
-- fromList []
--
empty :: Vector v a => Mat v a
-- | Count the number of non-zero entries in the matrix
--
--
-- >>> size (ident 4 :: Mat U.Vector Int)
-- 4
--
size :: Mat v a -> Int
-- |
-- >>> null (empty :: Mat U.Vector Int)
-- True
--
null :: Mat v a -> Bool
class 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, Vector v a) => Mat v a -> Mat v a -> Mat v 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 :: Vector v a => (a -> a -> a) -> Mat v a -> Mat v a -> Mat v a
-- | Multiply two matrices using the specified multiplication and addition
-- operation.
multiplyWith :: Vector v a => (a -> a -> a) -> (Maybe (Heap a) -> Stream (Key, a)) -> Mat v a -> Mat v a -> Mat v a
-- | bundle up the matrix in a form suitable for vector-algorithms
_Mat :: Iso (Mat u a) (Mat v b) (Vector Vector u (Key, a)) (Vector Vector v (Key, b))
-- | Access the keys of a matrix
keys :: Lens' (Mat v a) (Vector Key)
-- | Access the keys of a matrix
values :: Lens (Mat u a) (Mat v b) (u a) (v b)
instance Eq (v a) => Eq (Mat v a)
instance Ord (v a) => Ord (Mat v a)
instance (Vector v a, Num a, Eq0 a) => Num (Mat v a)
instance (Vector v a, Num a, Eq0 a) => Eq0 (Mat v a)
instance (Applicative f, Vector v a) => Ixed f (Mat v a)
instance (Functor f, Contravariant f, Vector v a) => Contains f (Mat v a)
instance (Applicative f, Vector v a, Vector v b) => Each f (Mat v a) (Mat v b) a b
instance Traversable v => Traversable (Mat v)
instance Foldable v => Foldable (Mat v)
instance Functor v => Functor (Mat v)
instance NFData (v a) => NFData (Mat v a)
instance (Vector v a, Read a) => Read (Mat v a)
instance (Vector v a, Show a) => Show (Mat v a)
instance (RealFloat a, Eq0 a) => Eq0 (Complex a)
instance Eq0 Double
instance Eq0 Float
instance Eq0 Integer
instance Eq0 Word
instance Eq0 Int