Copyright | (c) Kristof Bastiaensen, 2015 |
---|---|
License | BSD-3 |
Maintainer | kristof@resonata.be |
Stability | unstable |
Portability | ghc |
Safe Haskell | None |
Language | Haskell98 |
This module implements an equation solver that solves and evaluates expressions on the fly. It is based on Prof. D.E.Knuth's metafont. The goal of mfsolve is to make the solver useful in an interactive program, by enhancing the bidirectionality of the solver. Like metafont, it can solve linear equations, and evaluate nonlinear expressions. In addition to metafont, it also solves for angles, and makes the solution independend of the order of the equations.
The Expr
datatype allows for calculations with constants and unknown
variables. The Dependencies
datatype contains all dependencies and known equations.
Examples:
Let's define some variables. The SimpleVar
type is a simple wrapper
around String
to provide nice output.
let [x, y, t, a] = map (makeVariable . SimpleVar) ["x", "y", "t", "a"]
Solve linear equations:
showVars $ flip execSolver noDeps $ do 2*x + y === 5 x - y === 1
x = 2.0 y = 1.0
Solve for angle (pi/4):
showVars $ flip execSolver noDeps $ sin(t) === 1/sqrt(2)
t = 0.7853981633974484
Solve for angle (pi/3) and amplitude:
showVars $ flip execSolver noDeps $ do a*sin(x) === sqrt 3 a*cos(x) === 1
x = 1.0471975511965979 a = 2.0
Allow nonlinear expression with unknown variables:
showVars $ flip execSolver noDeps $ do sin(sqrt(x)) === y x === 2
x = 2.0 y = 0.9877659459927355
Find the angle and amplitude when using a rotation matrix:
showVars $ flip execSolver noDeps $ do a*cos t*x - a*sin t*y === 30 a*sin t*x + a*cos t*y === 40 x === 10 y === 10
x = 10.0 y = 10.0 t = 0.14189705460416402 a = 3.5355339059327373
- data MFSolver v n a
- data SimpleExpr v n
- = SEBin BinaryOp (SimpleExpr v n) (SimpleExpr v n)
- | SEUn UnaryOp (SimpleExpr v n)
- | Var v
- | Const n
- data Expr v n
- data LinExpr v n = LinExpr n [(v, n)]
- data UnaryOp
- data BinaryOp
- data Dependencies v n
- data DepError v n
- = UndefinedVar v
- | UnknownVar v n
- | InconsistentEq n
- | RedundantEq
- newtype SimpleVar = SimpleVar String
- evalSimple :: Floating m => (n -> m) -> (v -> m) -> SimpleExpr v n -> m
- evalExpr :: Floating n => (v -> n) -> SimpleExpr v n -> n
- fromSimple :: (Floating n, Ord n, Ord v) => SimpleExpr v n -> Expr v n
- toSimple :: (Num n, Eq n) => Expr v n -> SimpleExpr v n
- makeVariable :: Num n => v -> Expr v n
- makeConstant :: n -> Expr v n
- hasVar :: (Num t, Eq v, Eq t) => v -> Expr v t -> Bool
- getKnown :: (Eq v, Hashable v) => v -> Dependencies v n -> Either [v] n
- knownVars :: Dependencies v n -> [(v, n)]
- varDefined :: (Eq v, Hashable v) => v -> Dependencies v n -> Bool
- nonlinearEqs :: (Ord n, Ord v, Floating n) => Dependencies v n -> [Expr v n]
- dependendVars :: Eq n => Dependencies v n -> [(v, LinExpr v n)]
- noDeps :: Dependencies v n
- eliminate :: (Hashable n, Show n, Hashable v, RealFrac (Phase n), Ord v, Show v, Floating n) => Dependencies v n -> v -> (Dependencies v n, [Expr v n])
- addEquation :: (Hashable n, Hashable v, RealFrac (Phase n), Ord v, Floating n) => Dependencies v n -> Expr v n -> Either (DepError v n) (Dependencies v n)
- dependencies :: MonadState (Dependencies v n) m => m (Dependencies v n)
- getValue :: (MonadState (Dependencies v n) m, MonadError (DepError v n) m, Eq v, Hashable v) => v -> m n
- getKnownM :: (MonadState (Dependencies v n) m, Hashable v, Eq v) => v -> m (Either [v] n)
- varDefinedM :: (MonadState (Dependencies v n) m, Hashable v, Eq v) => v -> m Bool
- eliminateM :: (MonadState (Dependencies v n) m, Hashable n, Hashable v, Show n, Show v, RealFrac n, Ord v, Floating n) => v -> m [Expr v n]
- (=&=) :: (MonadState (Dependencies v n) m, MonadError (DepError v n) m, Eq v, Hashable v, Hashable n, RealFrac n, Floating n, Ord v) => (Expr v n, Expr v n) -> (Expr v n, Expr v n) -> m ()
- (===) :: (MonadState (Dependencies v n) m, MonadError (DepError v n) m, Eq v, Hashable v, Hashable n, RealFrac n, Floating n, Ord v) => Expr v n -> Expr v n -> m ()
- ignore :: MonadError (DepError v n) m => m () -> m ()
- runSolver :: MFSolver v n a -> Dependencies v n -> Either (DepError v n) (Dependencies v n, a)
- evalSolver :: MFSolver v n a -> Dependencies v n -> Either (DepError v n) a
- execSolver :: MFSolver v n a -> Dependencies v n -> Either (DepError v n) (Dependencies v n)
- unsafeSolve :: (Typeable n, Typeable v, Show n, Show v) => MFSolver v n a -> Dependencies v n -> a
- showVars :: (Show n, Show v, Ord n, Ord v, Floating n) => Either (DepError v n) (Dependencies v n) -> IO ()
Types
A monad for solving equations. Basicly just a state and exception monad.
Monad (MFSolver v n) | |
Functor (MFSolver v n) | |
Applicative (MFSolver v n) | |
MonadError (DepError v n) (MFSolver v n) | |
MonadState (Dependencies v n) (MFSolver v n) |
data SimpleExpr v n Source
A simplified datatype representing an expression
SEBin BinaryOp (SimpleExpr v n) (SimpleExpr v n) | |
SEUn UnaryOp (SimpleExpr v n) | |
Var v | |
Const n |
An mathematical expression of several variables.
A linear expression of several variables.
For example: 2*a + 3*b + 2
would be represented as
LinExpr 2 [(a, 2), (b, 3)]
.
LinExpr n [(v, n)] |
data Dependencies v n Source
An opaque datatype containing the dependencies of each variable. A variable who's dependency is just a number is called known. A variables which depends on other variables is called dependend. A variable which is neither known or dependend is called independend. A variable can only depend on other independend variables. It also contains nonlinear equations which it couldn't reduce to a linear equation yet.
(Show n, Floating n, Ord n, Ord v, Show v) => Show (Dependencies v n) | |
MonadState (Dependencies v n) (MFSolver v n) |
UndefinedVar v |
|
UnknownVar v n |
|
InconsistentEq n |
|
RedundantEq |
|
Expressions
evalSimple :: Floating m => (n -> m) -> (v -> m) -> SimpleExpr v n -> m Source
evaluate a simple expression using the given substitution.
evalExpr :: Floating n => (v -> n) -> SimpleExpr v n -> n Source
Evaluate the expression given a variable substitution.
fromSimple :: (Floating n, Ord n, Ord v) => SimpleExpr v n -> Expr v n Source
Make a expression from a simple expression.
toSimple :: (Num n, Eq n) => Expr v n -> SimpleExpr v n Source
Convert an Expr
to a SimpleExpr
.
makeVariable :: Num n => v -> Expr v n Source
Create an expression from a variable
makeConstant :: n -> Expr v n Source
Create an expression from a constant
hasVar :: (Num t, Eq v, Eq t) => v -> Expr v t -> Bool Source
The expression contains the given variable.
Dependencies
getKnown :: (Eq v, Hashable v) => v -> Dependencies v n -> Either [v] n Source
Return the value of the variable, or a list of variables it depends on. Only linear dependencies are shown.
knownVars :: Dependencies v n -> [(v, n)] Source
Return all known variables.
varDefined :: (Eq v, Hashable v) => v -> Dependencies v n -> Bool Source
Return True if the variable is known or dependend.
nonlinearEqs :: (Ord n, Ord v, Floating n) => Dependencies v n -> [Expr v n] Source
Return all nonlinear equations e_i
, where e_i = 0
.
dependendVars :: Eq n => Dependencies v n -> [(v, LinExpr v n)] Source
Return all dependend variables with their dependencies.
noDeps :: Dependencies v n Source
An empty set of dependencies.
eliminate :: (Hashable n, Show n, Hashable v, RealFrac (Phase n), Ord v, Show v, Floating n) => Dependencies v n -> v -> (Dependencies v n, [Expr v n]) Source
Eliminate an variable from the equations. Returns the eliminated equations. Before elimination it performs substitution to minimize the number of eliminated equations.
addEquation :: (Hashable n, Hashable v, RealFrac (Phase n), Ord v, Floating n) => Dependencies v n -> Expr v n -> Either (DepError v n) (Dependencies v n) Source
addEquation e d
: Add the equation e = 0
to the system d.
Monadic Interface
dependencies :: MonadState (Dependencies v n) m => m (Dependencies v n) Source
Get the dependencies from a state monad. Specialized version of get
.
getValue :: (MonadState (Dependencies v n) m, MonadError (DepError v n) m, Eq v, Hashable v) => v -> m n Source
Return the value of the variable or throw an error.
getKnownM :: (MonadState (Dependencies v n) m, Hashable v, Eq v) => v -> m (Either [v] n) Source
Monadic version of getKnown
.
varDefinedM :: (MonadState (Dependencies v n) m, Hashable v, Eq v) => v -> m Bool Source
Monadic version of varDefined
.
eliminateM :: (MonadState (Dependencies v n) m, Hashable n, Hashable v, Show n, Show v, RealFrac n, Ord v, Floating n) => v -> m [Expr v n] Source
Monadic version of eliminate
.
(=&=) :: (MonadState (Dependencies v n) m, MonadError (DepError v n) m, Eq v, Hashable v, Hashable n, RealFrac n, Floating n, Ord v) => (Expr v n, Expr v n) -> (Expr v n, Expr v n) -> m () infixr 1 Source
Make the pairs of expressions on both sides equal. No error is
signaled if the equation for one of the sides is Redundant
for
example in (x, 0) == (y, 0).
(===) :: (MonadState (Dependencies v n) m, MonadError (DepError v n) m, Eq v, Hashable v, Hashable n, RealFrac n, Floating n, Ord v) => Expr v n -> Expr v n -> m () infixr 1 Source
Make the expressions on both sides equal
ignore :: MonadError (DepError v n) m => m () -> m () Source
Succeed even when trowing a RedundantEq
error.
runSolver :: MFSolver v n a -> Dependencies v n -> Either (DepError v n) (Dependencies v n, a) Source
Unwrap a solver monad as a function.
evalSolver :: MFSolver v n a -> Dependencies v n -> Either (DepError v n) a Source
Return the result of solving the equations or an error.
execSolver :: MFSolver v n a -> Dependencies v n -> Either (DepError v n) (Dependencies v n) Source
Run the solver and return the dependencies or an error.
unsafeSolve :: (Typeable n, Typeable v, Show n, Show v) => MFSolver v n a -> Dependencies v n -> a Source
Return the result of solving the equations, or throw the error as an exception.