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))
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
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
fixZero :: p -> p
fixZero 0 = 0
fixZero z :: p
z = p
z
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
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
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