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


-- | Use SMT solvers to solve linear systems of equations over integers and rationals.
--   
--   Express and solve linear systems of equations over integers and
--   rationals, using an SMT solver to do the actual solving. By default,
--   we use Microsoft's Z3 SMT solver
--   (<a>http://research.microsoft.com/en-us/um/redmond/projects/z3/</a>).
--   
--   linearEqSolver is hosted at GitHub:
--   <a>http://github.com/LeventErkok/linearEqSolver</a>. Comments, bug
--   reports, and patches are always welcome.
--   
--   Release notes can be seen at:
--   <a>http://github.com/LeventErkok/linearEqSolver/blob/master/RELEASENOTES</a>.
@package linearEqSolver
@version 1.1


-- | (The linear equation solver library is hosted at
--   <a>http://github.com/LeventErkok/linearEqSolver</a>. Comments, bug
--   reports, and patches are always welcome.)
--   
--   Solvers for linear equations over integers and rationals. Both single
--   solution and all solution variants are supported.
module Math.LinearEquationSolver

-- | Solve a system of linear integer equations. The first argument is the
--   matrix of coefficients, known as <tt>A</tt>, of size <tt>mxn</tt>. The
--   second argument is the vector of results, known as <tt>B</tt>, of size
--   <tt>mx1</tt>. The result will be either <a>Nothing</a>, if there is no
--   solution, or <tt>Just x</tt> -- such that <tt>Ax = B</tt> holds.
--   (Naturally, the result <tt>x</tt> will be a vector of size
--   <tt>nx1</tt> in this case.)
--   
--   Here's an example call, to solve the following system of equations:
--   
--   <pre>
--   2x + 3y + 4z = 20
--   6x - 3y + 9z = -6
--   2x      +  z = 8
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; solveIntegerLinearEqs [[2, 3, 4],[6, -3, 9],[2, 0, 1]] [20, -6, 8]
--   Just [5,6,-2]
--   </pre>
--   
--   In case there are no solutions, we will get <a>Nothing</a>:
--   
--   <pre>
--   &gt;&gt;&gt; solveIntegerLinearEqs [[1], [1]] [2, 3]
--   Nothing
--   </pre>
--   
--   Note that there are no solutions to this second system as it
--   stipulates the unknown is equal to both 2 and 3. (Overspecified.)
solveIntegerLinearEqs :: [[Integer]] -> [Integer] -> IO (Maybe [Integer])

-- | Similar to <a>solveIntegerLinearEqs</a>, except returns all possible
--   solutions. Note that there might be an infinite number of solutions if
--   the system is underspecified, in which case the result will be a lazy
--   list of solutions that the caller can consume as much as needed.
--   
--   Here's an example call, where we underspecify the system and hence
--   there are multiple (in this case an infinite number of) solutions.
--   Here, we only take the first 3 elements, for testing purposes, but all
--   such results can be computed lazily. Our system is:
--   
--   <pre>
--   2x + 3y + 4z = 20
--   6x - 3y + 9z = -6
--   </pre>
--   
--   We have:
--   
--   <pre>
--   &gt;&gt;&gt; take 3 `fmap` solveIntegerLinearEqsAll [[2, 3, 4],[6, -3, 9]] [20, -6]
--   [[5,6,-2],[-8,4,6],[18,8,-10]]
--   </pre>
solveIntegerLinearEqsAll :: [[Integer]] -> [Integer] -> IO [[Integer]]

-- | Solve a system of linear equations over rationals. Same as the integer
--   version <a>solveIntegerLinearEqs</a>, except it takes rational
--   coefficients and returns rational results.
--   
--   Here's an example call, to solve the following system of equations:
--   
--   <pre>
--   2.4x + 3.6y = 12
--   7.2x - 5y   = -8.5
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; solveRationalLinearEqs [[2.4, 3.6],[7.2, -5]] [12, -8.5]
--   Just [245 % 316,445 % 158]
--   </pre>
solveRationalLinearEqs :: [[Rational]] -> [Rational] -> IO (Maybe [Rational])

-- | Solve a system of linear equations over rationals. Similar to
--   <a>solveRationalLinearEqs</a>, except it returns all solutions lazily.
--   
--   Example system:
--   
--   <pre>
--   2.4x + 3.6y = 12
--   </pre>
--   
--   In this case, the system has infinitely many solutions. We can compute
--   three of them as follows:
--   
--   <pre>
--   &gt;&gt;&gt; take 3 `fmap` solveRationalLinearEqsAll [[2.4, 3.6]] [12]
--   [[5 % 1,0 % 1],[0 % 1,10 % 3],[3 % 2,7 % 3]]
--   </pre>
solveRationalLinearEqsAll :: [[Rational]] -> [Rational] -> IO [[Rational]]