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


-- | Small library for effective linear algebra on sparse matrices
--   
--   Sparse matrices and vectors are represented using IntMaps, which store
--   non-zero values. There are some useful functions for computations on
--   them. Also some linear algebra algorithms will be included. At the
--   moment, the only is reduction of the matrix to the staircase form.
@package sparse-lin-alg
@version 0.3

module Math.LinearAlgebra.Sparse.Vector

-- | Dot product of two <a>IntMap</a>s (for internal use)
(··) :: Num α => IntMap α -> IntMap α -> α

-- | Shifts (re-enumerates) keys of IntMap by given number
shiftKeys :: Int -> IntMap α -> IntMap α

-- | Adds element to the map at given index, shifting all keys after it
addElem :: Maybe α -> Int -> IntMap α -> IntMap α

-- | Deletes element of the map at given index, shifting all keys after it
delElem :: Int -> IntMap α -> IntMap α

-- | Splits map using predicate and returns a pair with filtered map and
--   re-enumereted second part (that doesn't satisfy predicate). For
--   example:
--   
--   <pre>
--   &gt;&gt;&gt; partitionMap (&gt;0) (fromList [(1,1),(2,-1),(3,-2),(4,3),(5,-4)])
--   ( fromList [(1,1),(4,3)], fromList [(1,-1),(2,-2),(3,-4)] )
--   </pre>
partitionMap :: (α -> Bool) -> IntMap α -> (IntMap α, IntMap α)
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, isNotZeroVec :: SparseVector α -> Bool

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

-- | This is like cons (<tt>:</tt>) operator for lists.
--   
--   <pre>
--   x .&gt; v = singVec x &lt;&gt; v
--   </pre>
(.>) :: (Eq α, Num α) => α -> SparseVector α -> 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 α
vecIns :: (Eq t, Num t) => SparseVector t -> (Index, t) -> SparseVector t

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

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

-- | 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, 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, isNotZeroMx :: SparseMatrix α -> Bool

-- | Identity matrix of given size
idMx :: (Num α, Eq α) => Int -> 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 α

-- | WARNING: doesn't work with empty rows
--   
--   Partitions matrix, using pedicate on rows and returns two <i>new</i>
--   matrices, one constructed from rows satisfying predicate, and another
--   from rows that don't
partitionMx :: Num α => (SparseVector α -> Bool) -> SparseMatrix α -> (SparseMatrix α, SparseMatrix α)
separateMx :: Num α => (SparseVector α -> Bool) -> SparseMatrix α -> (SparseMatrix α, SparseMatrix α)
popRow :: Num α => Index -> SparseMatrix α -> (SparseVector α, SparseMatrix α)
(|>) :: Num α => SparseVector α -> SparseMatrix α -> SparseMatrix α
(<|) :: Num α => SparseMatrix α -> SparseVector α -> SparseMatrix α
replaceRow :: Num t => SparseVector t -> Index -> SparseMatrix t -> SparseMatrix t
exchangeRows :: Num t => Index -> Index -> SparseMatrix t -> SparseMatrix t

-- | 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]

-- | 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 list of rows
fromRows :: Num α => [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, 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 α
showSparseMatrix :: (Show α, Eq α, Num α) => [[α]] -> String
column :: (Show α, Eq α, Num α) => [α] -> [String]

-- | 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 (Eq α, Num α) => Num (SparseMatrix α)
instance Functor SparseMatrix

module Math.LinearAlgebra.Sparse.Algorithms.Staircase

-- | 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 α)

-- | 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)

-- | Fills column with zeroes
clearColumn :: Integral t => Index -> Index -> SparseMatrix t -> SparseMatrix t -> (SparseMatrix t, SparseMatrix t)

-- | Extended Euclid algorithm
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>
--   
--   So, <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 system in form:
--   
--   <pre>
--   &gt;&gt;&gt; 4x3       3x5         4x5
--   
--   &gt;&gt;&gt; [     ]   [       ]   [       ]
--   
--   &gt;&gt;&gt; [  m  ] × [   x   ] = [   b   ]
--   
--   &gt;&gt;&gt; [     ]   [       ]   [       ]
--   
--   &gt;&gt;&gt; [     ]               [       ]
--   </pre>
--   
--   <tt>solveLinSystems m b</tt> returns solution matrix <tt>x</tt>
solveLinSystems :: Integral α => SparseMatrix α -> SparseMatrix α -> SparseMatrix α

module Math.LinearAlgebra.Sparse.Algorithms

module Math.LinearAlgebra.Sparse