-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A playground of sparse linear algebra primitives using Morton ordering
--
@package sparse
@version 0.9.2
-- | 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.Array
class (Vector (Arr a) a, Monoid (Arr a a)) => Arrayed a where type family Arr a :: * -> * type instance Arr a = Vector
type Array a = Arr a a
data V_Complex :: * -> *
V_Complex :: {-# UNPACK #-} !Int -> !(Array a) -> !(Array a) -> V_Complex (Complex a)
data MV_Complex :: * -> * -> *
MV_Complex :: {-# UNPACK #-} !Int -> !(Mutable (Arr a) s a) -> !(Mutable (Arr a) s a) -> MV_Complex s (Complex a)
data V_Pair :: * -> *
V_Pair :: {-# UNPACK #-} !Int -> !(Array a) -> !(Array b) -> V_Pair (a, b)
data MV_Pair :: * -> * -> *
MV_Pair :: {-# UNPACK #-} !Int -> !(Mutable (Arr a) s a) -> !(Mutable (Arr b) s b) -> MV_Pair s (a, b)
instance (Arrayed a, RealFloat a) => Arrayed (Complex a)
instance (Arrayed a, RealFloat a, b ~ Complex a) => Monoid (V_Complex b)
instance (Arrayed a, RealFloat a, Eq a, b ~ Complex a) => Eq (V_Complex b)
instance (Arrayed a, RealFloat a, Read a, b ~ Complex a) => Read (V_Complex b)
instance (Arrayed a, RealFloat a, Show a, b ~ Complex a) => Show (V_Complex b)
instance (Arrayed a, RealFloat a) => Vector V_Complex (Complex a)
instance (Arrayed a, RealFloat a) => MVector MV_Complex (Complex a)
instance (Arrayed a, Arrayed b) => Arrayed (a, b)
instance (Arrayed a, Arrayed b, c ~ (a, b)) => Monoid (V_Pair c)
instance (Arrayed a, Arrayed b, Eq a, Eq b, c ~ (a, b)) => Eq (V_Pair c)
instance (Arrayed a, Arrayed b, Read a, Read b, c ~ (a, b)) => Read (V_Pair c)
instance (Arrayed a, Arrayed b, Show a, Show b, c ~ (a, b)) => Show (V_Pair c)
instance (Arrayed a, Arrayed b) => Vector V_Pair (a, b)
instance (Arrayed a, Arrayed b) => MVector MV_Pair (a, b)
instance Arrayed Integer
instance Arrayed Word64
instance Arrayed Word32
instance Arrayed Word16
instance Arrayed Word8
instance Arrayed Word
instance Arrayed Key
instance Arrayed Int64
instance Arrayed Int32
instance Arrayed Int16
instance Arrayed Int8
instance Arrayed Int
instance Arrayed Float
instance Arrayed Double
instance Arrayed ()
-- | 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)
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) -> !(Array 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 :: Arrayed a => [(Key, a)] -> Mat a
-- | singleton makes a matrix with a singleton value at a given
-- location
singleton :: Arrayed a => Key -> a -> Mat a
-- | Transpose a matrix
transpose :: Arrayed 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 :: (Arrayed a, Num a) => Int -> Mat a
-- | The empty matrix
--
--
-- >>> empty :: Mat Int
-- fromList []
--
empty :: Arrayed 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 (Arrayed 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 :: Arrayed a => (a -> a -> a) -> Mat a -> Mat a -> Mat a
-- | Multiply two matrices using the specified multiplication and addition
-- operation.
multiplyWith :: Arrayed a => (a -> a -> a) -> (Maybe (Heap a) -> Stream (Key, a)) -> Mat a -> Mat a -> Mat a
class (Vector (Arr a) a, Monoid (Arr a a)) => Arrayed a where type family Arr a :: * -> * type instance Arr a = Vector
-- | bundle up the matrix in a form suitable for vector-algorithms
_Mat :: Arrayed a => Iso' (Mat a) (Vector Vector (Arr a) (Key, a))
-- | Access the keys of the non-zero entries of our matrix
keys :: Lens' (Mat a) (Vector Key)
-- | Access the values of the non-zero entries of our matrix
values :: Lens (Mat a) (Mat b) (Array a) (Array b)
instance (Arrayed a, Ord (Array a)) => Ord (Mat a)
instance (Arrayed a, Eq (Array a)) => Eq (Mat a)
instance (Arrayed a, Eq0 a) => Num (Mat a)
instance (Arrayed a, Eq0 a) => Eq0 (Mat a)
instance Arrayed a => Arrayed (Mat a)
instance Arrayed a => Ixed (Mat a)
instance (Arrayed a, a ~ b) => Each (Mat a) (Mat b) a b
instance NFData (Array a) => NFData (Mat a)
instance (Arrayed a, Read a) => Read (Mat a)
instance (Arrayed 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