-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Effective linear algebra on sparse matrices
--   
--   Sparse matrices and vectors are represented using IntMaps, which store
--   non-zero values. This library provides some useful functions for
--   computations on them. Also some linear algebra algorithms are
--   included. At the moment, they work only on integer domain.
@package sparse-lin-alg
@version 0.4.2


-- | This module provides common funtions for manipulating sparse vectors
module Math.LinearAlgebra.Sparse.Vector
type Index = Int

-- | Type of internal vector storage
type SVec α = IntMap α

-- | Sparse vector is just indexed map of non-zero values
data SparseVector α
SV :: Int -> SVec α -> SparseVector α

-- | real size of vector (with zeroes)
dim :: SparseVector α -> Int

-- | IntMap storing non-zero values
vec :: SparseVector α -> SVec α

-- | Sets vector's size
setLength :: Int -> SparseVector α -> SparseVector α

-- | Vector of zero size with no values
emptyVec :: SparseVector α

-- | Vector of given size with no non-zero values
zeroVec :: Int -> SparseVector α

-- | Checks if vector has no non-zero values (i.e. is empty)
isZeroVec :: SparseVector α -> Bool

-- | Checks if vector has no non-zero values (i.e. is empty)
isNotZeroVec :: SparseVector α -> Bool

-- | Vector of length 1 with given value
singVec :: (Eq α, Num α) => α -> SparseVector α

-- | Splits vector using predicate and returns a pair with filtered values
--   and re-enumereted second part (that doesn't satisfy predicate). For
--   example:
--   
--   <pre>
--   &gt;&gt;&gt; partitionVec (&gt;0) (sparseList [0,1,-1,2,3,0,-4,5,-6,0,7])
--   ( sparseList [0,1,0,2,3,0,0,5,0,0,7], sparseList [-1,-4,-6] )
--   </pre>
partitionVec :: Num α => (α -> Bool) -> SparseVector α -> (SparseVector α, SparseVector α)

-- | Looks up an element in the vector (if not found, zero is returned)
(!) :: Num α => SparseVector α -> Index -> α

-- | Deletes element of vector at given index (size of vector doesn't
--   change)
eraseInVec :: Num α => SparseVector α -> Index -> SparseVector α

-- | Updates value at given index
vecIns :: (Eq α, Num α) => SparseVector α -> (Index, α) -> SparseVector α

-- | Unions non-zero values of vectors and applies given function on
--   intersection
unionVecsWith :: (α -> α -> α) -> SparseVector α -> SparseVector α -> SparseVector α

-- | Intersects non-zero values of vectors and applies given function on
--   them
intersectVecsWith :: (α -> α -> α) -> SparseVector α -> SparseVector α -> SparseVector α

-- | Returns plain list with all zeroes restored
fillVec :: Num α => SparseVector α -> [α]

-- | Converts plain list to sparse vector, throwing out all zeroes
sparseList :: (Num α, Eq α) => [α] -> SparseVector α

-- | Converts sparse vector to an associative list, adding fake zero
--   element, to save real size for inverse conversion
vecToAssocList :: (Num α, Eq α) => SparseVector α -> [(Index, α)]

-- | Converts associative list to sparse vector, of given size
vecFromAssocListWithSize :: (Num α, Eq α) => Int -> [(Index, α)] -> SparseVector α

-- | Converts associative list to sparse vector, using maximal index as
--   it's size
vecFromAssocList :: (Num α, Eq α) => [(Index, α)] -> SparseVector α

-- | Dot product of two sparse vectors
dot :: (Eq α, Num α) => SparseVector α -> SparseVector α -> α

-- | Unicode alias for <a>dot</a>
(·) :: (Eq α, Num α) => SparseVector α -> SparseVector α -> α
instance Eq α => Eq (SparseVector α)
instance (Show α, Eq α, Num α) => Show (SparseVector α)
instance Monoid (SparseVector α)
instance (Eq α, Num α) => Num (SparseVector α)
instance Foldable SparseVector
instance Functor SparseVector

module Math.LinearAlgebra.Sparse.Matrix

-- | Internal storage of matrix
type SMx α = SVec (SVec α)

-- | Sparse matrix is indexed map of non-zero rows,
data SparseMatrix α
SM :: (Int, Int) -> SMx α -> SparseMatrix α

-- | real height and width of filled matrix
dims :: SparseMatrix α -> (Int, Int)

-- | IntMap (IntMap α) representing non-zero values
mx :: SparseMatrix α -> SMx α

-- | Matrix real height and width
height :: SparseMatrix α -> Int

-- | Matrix real height and width
width :: SparseMatrix α -> Int

-- | Sets height and width of matrix
setSize :: Num α => (Int, Int) -> SparseMatrix α -> SparseMatrix α

-- | Matrix of zero size with no values
emptyMx :: SparseMatrix α

-- | Zero matrix of given size
zeroMx :: Num α => (Int, Int) -> SparseMatrix α

-- | Checks if matrix has no non-zero values (i.e. is empty)
isZeroMx :: SparseMatrix α -> Bool

-- | Checks if matrix has no non-zero values (i.e. is empty)
isNotZeroMx :: SparseMatrix α -> Bool

-- | Identity matrix of given size
idMx :: (Num α, Eq α) => Int -> SparseMatrix α

-- | Vertical concatenation
(//) :: SparseMatrix α -> SparseMatrix α -> SparseMatrix α

-- | Batch horisontal/vertical concatenation
hconcat :: [SparseMatrix α] -> SparseMatrix α

-- | Batch horisontal/vertical concatenation
vconcat :: [SparseMatrix α] -> SparseMatrix α

-- | Takes size of each block and matrix of sparse matrices and constructs
--   sparse matrix from this blocks
sizedBlockMx :: Num α => (Int, Int) -> [[SparseMatrix α]] -> SparseMatrix α

-- | Fills sparse matrix of blocks and then applies <a>sizedBlockMx</a>
sizedBlockSMx :: (Eq α, Num α) => (Int, Int) -> SparseMatrix (SparseMatrix α) -> SparseMatrix α
blockMx :: [[SparseMatrix α]] -> SparseMatrix α
blockSMx :: (Eq α, Num α) => SparseMatrix (SparseMatrix α) -> SparseMatrix α

-- | Adds row at given index, increasing matrix height by 1 and shifting
--   indexes after it
addRow :: Num α => SparseVector α -> Index -> SparseMatrix α -> SparseMatrix α

-- | Adds column at given index, increasing matrix width by 1 and shifting
--   indexes after it
addCol :: Num α => SparseVector α -> Index -> SparseMatrix α -> SparseMatrix α

-- | Just adds zero row at given index
addZeroRow :: Num α => Index -> SparseMatrix α -> SparseMatrix α

-- | Just adds zero column at given index
addZeroCol :: Num α => Index -> SparseMatrix α -> SparseMatrix α

-- | Deletes row at given index, decreasing matrix height by 1 and shifting
--   indexes after it
delRow :: Num α => Index -> SparseMatrix α -> SparseMatrix α

-- | Deletes column at given index, decreasing matrix width by 1 and
--   shifting indexes after it
delCol :: Num α => Index -> SparseMatrix α -> SparseMatrix α

-- | Deletes row and column at given indexes
delRowCol :: Num α => Index -> Index -> SparseMatrix α -> SparseMatrix α

-- | Separates matrix, using pedicate on rows and returns two matrices of
--   the same size, one only with rows satisfying predicate, and another
--   with the rest rows
separateMx :: Num α => (SparseVector α -> Bool) -> SparseMatrix α -> (SparseMatrix α, SparseMatrix α)

-- | Looks up an element in the matrix (if not found, zero is returned)
(#) :: Num α => SparseMatrix α -> (Index, Index) -> α

-- | Returns row of matrix at given index
row :: Num α => SparseMatrix α -> Index -> SparseVector α

-- | Returns column of matrix at given index
col :: (Num α, Eq α) => SparseMatrix α -> Index -> SparseVector α

-- | Updates values in row using given function
updRow :: Num α => (SparseVector α -> SparseVector α) -> Index -> SparseMatrix α -> SparseMatrix α

-- | Fills row with zeroes (i.e. deletes it, but size of matrix doesn't
--   change)
eraseRow :: Num α => Index -> SparseMatrix α -> SparseMatrix α

-- | Erases matrix element at given index
erase :: Num α => SparseMatrix α -> (Index, Index) -> SparseMatrix α

-- | Inserts new element to the sparse matrix (replaces old value)
ins :: (Num α, Eq α) => SparseMatrix α -> ((Index, Index), α) -> SparseMatrix α

-- | Finds indices of rows, that satisfy given predicate. Searches from
--   left to right (in ascending order of indices)
findRowIndices :: (SparseVector α -> Bool) -> SparseMatrix α -> [Int]

-- | Finds indices of rows, that satisfy given predicate. Searches from
--   right to left (in descending order of indices)
findRowIndicesR :: (SparseVector α -> Bool) -> SparseMatrix α -> [Int]

-- | Returns a row at given index and matrix without it
popRow :: Num α => Index -> SparseMatrix α -> (SparseVector α, SparseMatrix α)

-- | Adds row to matrix at the top
(|>) :: Num α => SparseVector α -> SparseMatrix α -> SparseMatrix α

-- | Adds row to matrix at the bottom
(<|) :: Num α => SparseMatrix α -> SparseVector α -> SparseMatrix α

-- | Replaces row at given index with given vector
replaceRow :: Num α => SparseVector α -> Index -> SparseMatrix α -> SparseMatrix α

-- | Exchanges positions of two rows
exchangeRows :: Num α => Index -> Index -> SparseMatrix α -> SparseMatrix α

-- | Applies vector-function on matrix rows
mapOnRows :: (SparseVector α -> SparseVector β) -> SparseMatrix α -> SparseMatrix β

-- | Returns vector with matrix rows
rows :: SparseMatrix α -> SparseVector (SparseVector α)

-- | Returns vector with matrix columns (<tt>rows . trans</tt>)
columns :: (Eq α, Num α) => SparseMatrix α -> SparseVector (SparseVector α)

-- | Constructs square matrix with given elements on diagonal
diagonalMx :: (Num α, Eq α) => [α] -> SparseMatrix α

-- | Collects main diagonal of matrix
mainDiag :: (Eq α, Num α) => SparseMatrix α -> SparseVector α

-- | Constructs matrix from a set (list<i>vector</i>etc.) of rows
fromRows :: (Num α, Foldable φ) => φ (SparseVector α) -> SparseMatrix α

-- | Converts sparse matrix to associative list, adding fake zero element,
--   to save real size for inverse conversion
toAssocList :: (Num α, Eq α) => SparseMatrix α -> [((Index, Index), α)]

-- | Converts associative list to sparse matrix, of given size
fromAssocListWithSize :: (Num α, Eq α) => (Int, Int) -> [((Index, Index), α)] -> SparseMatrix α

-- | Converts associative list to sparse matrix, using maximal index as
--   matrix size
fromAssocList :: (Num α, Eq α) => [((Index, Index), α)] -> SparseMatrix α

-- | Converts sparse matrix to plain list-matrix with all zeroes restored
fillMx :: Num α => SparseMatrix α -> [[α]]

-- | Converts plain list-matrix to sparse matrix, throwing out all zeroes
sparseMx :: (Num α, Eq α) => [[α]] -> SparseMatrix α

-- | Transposes matrix (rows become columns)
trans :: (Num α, Eq α) => SparseMatrix α -> SparseMatrix α

-- | Matrix-by-vector multiplication
mulMV :: (Num α, Eq α) => SparseMatrix α -> SparseVector α -> SparseVector α

-- | Unicode alias for <a>mulMV</a>
(×·) :: (Num α, Eq α) => SparseMatrix α -> SparseVector α -> SparseVector α

-- | Vector-by-matrix multiplication
mulVM :: (Num α, Eq α) => SparseVector α -> SparseMatrix α -> SparseVector α

-- | Unicode alias for <a>mulVM</a>
(·×) :: (Num α, Eq α) => SparseVector α -> SparseMatrix α -> SparseVector α

-- | Sparse matrices multiplication
mul :: (Num α, Eq α) => SparseMatrix α -> SparseMatrix α -> SparseMatrix α

-- | Unicode alias for <a>mul</a>
(×) :: (Num α, Eq α) => SparseMatrix α -> SparseMatrix α -> SparseMatrix α
instance Eq α => Eq (SparseMatrix α)
instance (Show α, Eq α, Num α) => Show (SparseMatrix α)
instance Monoid (SparseMatrix α)
instance (Eq α, Num α) => Num (SparseMatrix α)
instance Functor SparseMatrix

module Math.LinearAlgebra.Sparse.Algorithms.Staircase

-- | Staircase Form of matrix.
--   
--   It takes matrix itself and initial protocol matrix and applies all
--   transformations to both of them in the same way, and then returns
--   matrix in the staircase form and a transformation matrix.
--   
--   Usage of <a>divMod</a> causes <a>Integral</a> context. (TODO:
--   eliminate it)
--   
--   Method: Gauss method applied to the rows of matrix. Though α may be
--   not a field, we repeat the remainder division to obtain zeroes down in
--   the column.
staircase' :: Integral a => SparseMatrix a -> SparseMatrix a -> (SparseMatrix a, SparseMatrix a)

-- | Staircase Form of matrix.
--   
--   It uses an identity matrix as initial protocol matrix for
--   <a>staircase'</a>.
--   
--   It returns also transformation matrix:
--   
--   <pre>
--   &gt;&gt;&gt; let (s, t) = staircase m  in  t × m == s
--   True
--   </pre>
--   
--   Usage of <a>divMod</a> causes <a>Integral</a> context. (TODO:
--   eliminate it)
--   
--   Method: Gauss method applied to the rows of matrix. Though α may be
--   not a field, we repeat the remainder division to obtain zeroes down in
--   the column.
staircase :: Integral α => SparseMatrix α -> (SparseMatrix α, SparseMatrix α)

-- | Extended Euclid algorithm
--   
--   <tt>extGCD a b</tt> returns <tt>(x,y)</tt>, such that
--   
--   <pre>
--   x · (a &lt;&gt; b) == gcd a b
--   </pre>
--   
--   <pre>
--   y · (a &lt;&gt; b) == 0
--   </pre>
extGCD :: (Num α, Integral α) => α -> α -> (SparseVector α, SparseVector α)

module Math.LinearAlgebra.Sparse.Algorithms.Diagonal

-- | Checks if matrix has diagonal form
isDiag :: SparseMatrix α -> Bool

-- | Transforms matrix to diagonal form and returns also two protocol
--   matrices:
--   
--   <pre>
--   &gt;&gt;&gt; let (d,t,u) = toDiag m  in t × m × (trans u) == d
--   True
--   </pre>
--   
--   <tt>t</tt> stores rows transformations and <tt>u</tt> — columns
--   transformations
toDiag :: Integral α => SparseMatrix α -> (SparseMatrix α, SparseMatrix α, SparseMatrix α)

module Math.LinearAlgebra.Sparse.Algorithms.SolveLinear

-- | Just solves system of linear equations in matrix form for given
--   left-side matrix and right-side vector
solveLinear :: Integral α => SparseMatrix α -> SparseVector α -> Maybe (SparseVector α)

-- | Solves a set of systems for given left-side matrix and each right-side
--   vector of given set (sparse vector)
solveLinSystems :: Integral α => SparseMatrix α -> SparseVector (SparseVector α) -> Maybe (SparseVector (SparseVector α))

module Math.LinearAlgebra.Sparse.Algorithms

module Math.LinearAlgebra.Sparse