-- 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.2.1

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 α

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

-- | 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 :: Num α => SparseVector α -> SparseVector α -> α

-- | Unicode alias for <a>dot</a>
(·) :: 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 vector has no non-zero values (i.e. is empty)
isZeroVec, isNotZeroVec :: SparseVector α -> Bool

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

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

-- | 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 α => SparseMatrix α -> (SparseVector α -> SparseVector α) -> Index -> SparseMatrix α

-- | Fills row with zeroes (i.e. deletes it, but size of matrix doesn't
--   change)
eraseRow :: Num α => SparseMatrix α -> Index -> 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 α
findRowIndices :: (SparseVector α -> Bool) -> SparseMatrix α -> [Key]
findRowIndicesR :: (SparseVector α -> Bool) -> SparseMatrix α -> [Key]

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

-- | 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 became 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. Using 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 :: (Num α, Integral α) => SparseMatrix α -> SparseMatrix α

-- | clearColumn m --&gt; m' From the start, length(m) &gt; 1. m'(1,1) =
--   gcd(firstColumn(m)), m'(i,1)==0 for i&gt;1. m'(1,1) = 0 means that
--   column was zero.
clearColumn :: (Num α, Integral α) => SparseMatrix α -> SparseMatrix α

-- | extGCD a b --&gt; (gcd(a,b), tt) a,b are divided repeatedly with
--   remainder, like in extended gcd method. tt is a protocol 2x2 matrix
--   so, [a,b] ·× tt = [gcd(a,b),0]
extGCD :: (Num α, Integral α) => α -> α -> (α, SparseMatrix α)