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


-- | Root-finding algorithms (1-dimensional)
--   
--   Framework for and a few implementations of (1-dimensional) numerical
--   root-finding algorithms.
--   
--   Changes in 0.1.1.2: More type signature changes to build on GHC 7.6
--   
--   Changes in 0.1.1.1: Added Eq contexts where necessary to build on GHC
--   7.4
@package roots
@version 0.1.1.2

module Math.Root.Finder

-- | General interface for numerical root finders.
class RootFinder r a b where converged xacc r = abs (estimateError r) <= abs xacc defaultNSteps = Tagged 250
initRootFinder :: RootFinder r a b => (a -> b) -> a -> a -> r a b
stepRootFinder :: RootFinder r a b => (a -> b) -> r a b -> r a b
estimateRoot :: RootFinder r a b => r a b -> a
estimateError :: RootFinder r a b => r a b -> a
converged :: (RootFinder r a b, Num a, Ord a) => a -> r a b -> Bool
defaultNSteps :: RootFinder r a b => Tagged (r a b) Int

-- | Convenience function to access <a>defaultNSteps</a> for a root finder,
--   which requires a little bit of type-gymnastics.
--   
--   This function does not evaluate its argument.
getDefaultNSteps :: RootFinder r a b => r a b -> Int

-- | General-purpose driver for stepping a root finder. Given a "control"
--   function, the function being searched, and an initial
--   <a>RootFinder</a> state, <tt>runRootFinder step f state</tt>
--   repeatedly steps the root-finder and passes each intermediate state,
--   along with a count of steps taken, to <tt>step</tt>.
--   
--   The <tt>step</tt> funtion will be called with the following arguments:
--   
--   <ul>
--   <li><i><tt> n :: <a>Int</a> </tt></i> The number of steps taken thus
--   far</li>
--   <li><i><tt> currentState :: r a b </tt></i> The current state of the
--   root finder</li>
--   <li><i><tt> continue :: c </tt></i> The result of the "rest" of the
--   iteration</li>
--   </ul>
--   
--   For example, the following function simply iterates a root finder and
--   returns every intermediate state (similar to <a>traceRoot</a>):
--   
--   <pre>
--   iterateRoot :: RootFinder r a b =&gt; (a -&gt; b) -&gt; a -&gt; a -&gt; [r a b]
--   iterateRoot f a b = runRootFinder (const (:)) f (initRootFinder f a b)
--   </pre>
--   
--   And the following function simply iterates the root finder to
--   convergence or throws an error after a given number of steps:
--   
--   <pre>
--   solve :: (RootFinder r a b, RealFloat a)
--         =&gt; Int -&gt; (a -&gt; b) -&gt; a -&gt; a -&gt; r a b
--   solve maxN f a b = runRootFinder step f (initRootFinder f a b)
--      where
--          step n x continue
--              | converged eps x   = x
--              | n &gt; maxN          = error "solve: step limit exceeded"
--              | otherwise         = continue
--   </pre>
runRootFinder :: RootFinder r a b => (Int -> r a b -> c -> c) -> (a -> b) -> r a b -> c

-- | <tt>traceRoot f x0 x1 mbEps</tt> initializes a root finder and
--   repeatedly steps it, returning each step of the process in a list. No
--   step limit is imposed.
--   
--   Termination criteria depends on <tt>mbEps</tt>; if it is of the form
--   <tt>Just eps</tt> then convergence to <tt>eps</tt> is used (using the
--   <tt>converged</tt> method of the root finder). Otherwise, the trace is
--   not terminated until subsequent states are equal (according to
--   <a>==</a>). This is a stricter condition than convergence to 0;
--   subsequent states may have converged to zero but as long as any
--   internal state changes the trace will continue.
traceRoot :: (Eq (r a b), RootFinder r a b, Num a, Ord a) => (a -> b) -> a -> a -> Maybe a -> [r a b]

-- | <tt>findRoot f x0 x1 eps</tt> initializes a root finder and repeatedly
--   steps it. When the algorithm converges to <tt>eps</tt> or the
--   <a>defaultNSteps</a> limit is exceeded, the current best guess is
--   returned, with the <tt>Right</tt> constructor indicating successful
--   convergence or the <tt>Left</tt> constructor indicating failure to
--   converge.
findRoot :: (RootFinder r a b, Num a, Ord a) => (a -> b) -> a -> a -> a -> Either (r a b) (r a b)

-- | Like <a>findRoot</a> but with a specified limit on the number of steps
--   (rather than using <a>defaultNSteps</a>).
findRootN :: (RootFinder r a b, Num a, Ord a) => Int -> (a -> b) -> a -> a -> a -> Either (r a b) (r a b)

-- | A useful constant: <a>eps</a> is (for most <a>RealFloat</a> types) the
--   smallest positive number such that <tt>1 + eps /= 1</tt>.
eps :: RealFloat a => a

-- | For <a>RealFloat</a> types, computes a suitable default step limit
--   based on the precision of the type and a margin of error.
realFloatDefaultNSteps :: RealFloat a => Float -> Tagged (r a b) Int

module Math.Root.Finder.Bisection

-- | Bisect an interval in search of a root. At all times, <tt>f
--   (estimateRoot _)</tt> is less than or equal to 0 and <tt>f
--   (estimateRoot _ + estimateError _)</tt> is greater than or equal to 0.
data Bisect a b

-- | Using bisection, return a root of a function known to lie between x1
--   and x2. The root will be refined till its accuracy is +-xacc. If
--   convergence fails, returns the final state of the search.
bisection :: (Ord a, Fractional a, Ord b, Num b) => (a -> b) -> a -> a -> a -> Either (Bisect a b) a
instance (Eq a, Eq b) => Eq (Bisect a b)
instance (Ord a, Ord b) => Ord (Bisect a b)
instance (Show a, Show b) => Show (Bisect a b)
instance (Fractional a, Eq a, Ord b, Num b) => RootFinder Bisect a b

module Math.Root.Finder.Dekker
data Dekker a b

-- | <tt>dekker f x1 x2 xacc</tt>: attempt to find a root of a function
--   known to lie between x1 and x2, using Dekker's method. The root will
--   be refined till its accuracy is +-xacc. If convergence fails, returns
--   the final state of the search.
dekker :: RealFloat a => (a -> a) -> a -> a -> a -> Either (Dekker a a) a
instance (Eq a, Eq b) => Eq (Dekker a b)
instance (Show a, Show b) => Show (Dekker a b)
instance (Fractional a, Ord a, Real b, Fractional b, Ord b) => RootFinder Dekker a b

module Math.Root.Finder.FalsePosition

-- | Iteratively refine a bracketing interval [x1, x2] of a root of f until
--   total convergence (which may or may not ever be achieved) using the
--   false-position method.
data FalsePosition a b

-- | <tt>falsePosition f x1 x2 xacc</tt>: Using the false-position method,
--   return a root of a function known to lie between x1 and x2. The root
--   is refined until its accuracy is += xacc.
falsePosition :: (Ord a, Fractional a) => (a -> a) -> a -> a -> a -> Either (FalsePosition a a) a
instance Eq a => Eq (FalsePosition a b)
instance Show a => Show (FalsePosition a b)
instance (Fractional a, Ord a) => RootFinder FalsePosition a a

module Math.Root.Finder.InverseQuadratic
data InverseQuadratic a b

-- | <tt>inverseQuadratic f x1 x2 xacc</tt>: attempt to find a root of a
--   function known to lie between x1 and x2, using the inverse quadratic
--   interpolation method. The root will be refined till its accuracy is
--   +-xacc. If convergence fails, returns the final state of the search.
inverseQuadratic :: RealFloat a => (a -> a) -> a -> a -> a -> Either (InverseQuadratic a a) a
instance (Eq a, Eq b) => Eq (InverseQuadratic a b)
instance (Show a, Show b) => Show (InverseQuadratic a b)
instance (Fractional a, Ord a, Real b, Fractional b) => RootFinder InverseQuadratic a b

module Math.Root.Finder.Newton
data Newton a b

-- | <tt>newton f x1 x2 xacc</tt>: using Newton's method, return a root of
--   a function known to lie between x1 and x2. The root is refined until
--   its accuracy is += xacc.
--   
--   The function passed should return a pair containing the value of the
--   function and its derivative, respectively.
newton :: (Ord a, Fractional a) => (a -> (a, a)) -> a -> a -> a -> Either (Newton a (a, a)) a
instance Eq a => Eq (Newton a b)
instance Show a => Show (Newton a b)
instance Fractional a => RootFinder Newton a (a, a)

module Math.Root.Finder.Ridders
data RiddersMethod a b

-- | <tt>ridders f x1 x2 xacc</tt>: attempt to find a root of a function
--   known to lie between x1 and x2, using Ridders' method. The root will
--   be refined till its accuracy is +-xacc. If convergence fails, returns
--   the final state of the search.
ridders :: (Ord a, Floating a) => (a -> a) -> a -> a -> a -> Either (RiddersMethod a a) a
instance (Eq a, Eq b) => Eq (RiddersMethod a b)
instance (Show a, Show b) => Show (RiddersMethod a b)
instance (Floating a, Ord a) => RootFinder RiddersMethod a a

module Math.Root.Finder.Secant

-- | Iteratively refine 2 estimates x1, x2 of a root of f until total
--   convergence (which may or may not ever be achieved) using the secant
--   method.
data SecantMethod a b

-- | <tt>secant f x1 x2 xacc</tt>: Using the secant method, return the root
--   of a function thought to lie between x1 and x2. The root is refined
--   until its accuracy is +-xacc.
secant :: (Ord a, Fractional a) => (a -> a) -> a -> a -> a -> Either (SecantMethod a a) a
instance (Eq a, Eq b) => Eq (SecantMethod a b)
instance (Show a, Show b) => Show (SecantMethod a b)
instance (Fractional a, Ord a) => RootFinder SecantMethod a a

module Math.Root.Bracket

-- | Predicate that returns <a>True</a> whenever the given pair of points
--   brackets a root of the given function.
brackets :: (Eq a, Eq b, Num b) => (a -> b) -> (a, a) -> Bool

-- | <tt>bracket f x1 x2</tt>: Given a function and an initial guessed
--   range x1 to x2, this function expands the range geometrically until a
--   root is bracketed by the returned values, returning a list of the
--   successively expanded ranges. The list will be finite if and only if
--   the sequence yields a bracketing pair.
bracket :: (Fractional a, Eq a, Num b, Ord b) => (a -> b) -> a -> a -> [(a, a)]

-- | <tt>subdivideAndBracket f x1 x2 n</tt>: Given a function defined on
--   the interval [x1,x2], subdivide the interval into n equally spaced
--   segments and search for zero crossings of the function. The returned
--   list will contain all bracketing pairs found.
subdivideAndBracket :: (Num b, Eq b, Fractional a, Integral c) => (a -> b) -> a -> a -> c -> [(a, a)]

module Math.Root.Finder.Brent

-- | Working state for Brent's root-finding method.
data Brent a b

-- | <tt>brent f x1 x2 xacc</tt>: attempt to find a root of a function
--   known to lie between x1 and x2, using Brent's method. The root will be
--   refined till its accuracy is +-xacc. If convergence fails, returns the
--   final state of the search.
brent :: RealFloat a => (a -> a) -> a -> a -> a -> Either (Brent a a) a
instance (Eq a, Eq b) => Eq (Brent a b)
instance (Show a, Show b) => Show (Brent a b)
instance (RealFloat a, Real b, Fractional b) => RootFinder Brent a b