{-
 -      ``Data/Random/Internal/Find''
 -  Utilities for searching fractional domains.  Needs cleanup, testing,
 -  and such.  Used for constructing generic ziggurats.
 -}

module Data.Random.Internal.Find where

findMax :: (Fractional a, Ord a) => (a -> Bool) -> a
findMax :: (a -> Bool) -> a
findMax p :: a -> Bool
p = a -> a
forall a. Num a => a -> a
negate ((a -> Bool) -> a
forall a. (Fractional a, Ord a) => (a -> Bool) -> a
findMin (a -> Bool
p(a -> Bool) -> (a -> a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> a
forall a. Num a => a -> a
negate))

-- |Given an upward-closed predicate on an ordered Fractional type,
-- find the smallest value satisfying the predicate.
findMin :: (Fractional a, Ord a) => (a -> Bool) -> a
findMin :: (a -> Bool) -> a
findMin = a -> a -> (a -> Bool) -> a
forall a. (Fractional a, Ord a) => a -> a -> (a -> Bool) -> a
findMinFrom 0 1

-- |Given an upward-closed predicate on an ordered Fractional type,
-- find the smallest value satisfying the predicate.  Starts at the
-- specified point with the specified stepsize, performs an exponential
-- search out from there until it finds an interval bracketing the
-- change-point of the predicate, and then performs a bisection search
-- to isolate the change point.  Note that infinitely-divisible domains 
-- such as 'Rational' cannot be searched by this function because it does
-- not terminate until it reaches a point where further subdivision of the
-- interval has no effect.
findMinFrom :: (Fractional a, Ord a) => a -> a -> (a -> Bool) -> a
findMinFrom :: a -> a -> (a -> Bool) -> a
findMinFrom z0 :: a
z0 0 p :: a -> Bool
p = a -> a -> (a -> Bool) -> a
forall a. (Fractional a, Ord a) => a -> a -> (a -> Bool) -> a
findMinFrom a
z0 1 a -> Bool
p
findMinFrom z0 :: a
z0 step1 :: a
step1 p :: a -> Bool
p
    | a -> Bool
p a
z0      = a -> a -> a
descend (a
z0a -> a -> a
forall a. Num a => a -> a -> a
-a
step1) a
z0
    | Bool
otherwise = a -> a
forall p. (Eq p, Num p) => p -> p
fixZero (a -> a -> a
ascend a
z0 (a
z0a -> a -> a
forall a. Num a => a -> a -> a
+a
step1))
    where
        -- eliminate negative zero, which, in many domains, is technically
        -- a feasible answer
        fixZero :: p -> p
fixZero 0 = 0
        fixZero z :: p
z = p
z
        
        -- preconditions:
        -- not (p l)
        -- 0 <= l < x
        ascend :: a -> a -> a
ascend l :: a
l x :: a
x 
            | a -> Bool
p a
x       = a -> a -> a
bisect a
l a
x
            | Bool
otherwise = a -> a -> a
ascend a
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! 2a -> a -> a
forall a. Num a => a -> a -> a
*a
xa -> a -> a
forall a. Num a => a -> a -> a
-a
z0
        
        -- preconditions:
        -- p h
        -- x < h <= 0
        descend :: a -> a -> a
descend x :: a
x h :: a
h 
            | a -> Bool
p a
x       = (a -> a -> a
descend (a -> a -> a) -> a -> a -> a
forall a b. (a -> b) -> a -> b
$! 2a -> a -> a
forall a. Num a => a -> a -> a
*a
xa -> a -> a
forall a. Num a => a -> a -> a
-a
z0) a
x
            | Bool
otherwise = a -> a -> a
bisect a
x a
h
        
        -- preconditions:
        -- not (p l)
        -- p h
        -- l <= h
        bisect :: a -> a -> a
bisect l :: a
l h :: a
h 
            | a
l a -> a -> Bool
forall a. Ord a => a -> a -> Bool
/< a
h    = a
h
            | a
l a -> a -> Bool
forall a. Ord a => a -> a -> Bool
/< a
mid Bool -> Bool -> Bool
|| a
mid a -> a -> Bool
forall a. Ord a => a -> a -> Bool
/< a
h
            = if a -> Bool
p a
mid then a
mid else a
h
            | a -> Bool
p a
mid     = a -> a -> a
bisect a
l a
mid
            | Bool
otherwise = a -> a -> a
bisect a
mid a
h
            where 
                a :: a
a /< :: a -> a -> Bool
/< b :: a
b = Bool -> Bool
not (a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
b)
                mid :: a
mid = (a
la -> a -> a
forall a. Num a => a -> a -> a
+a
h)a -> a -> a
forall a. Num a => a -> a -> a
*0.5