{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE NamedFieldPuns #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}

{-|
Copyright   : Predictable Network Solutions Ltd., 2020-2024
License     : BSD-3-Clause
Description : Instances via piecewise polynomials.

@'DQ'@ is a probability distribution of completion time
using the numeric type @Rational@.
This type represents a mixed discrete / continuous probability distribution
where the continuous part is represented in terms of piecewise polynomials.
-}
module DeltaQ.PiecewisePolynomial
    ( -- * Type
      DQ
    , distribution
    , fromPositiveMeasure
    , unsafeFromPositiveMeasure

    -- * Operations
    , meetsQTA
    , Moments (..)
    , moments

    -- * Internal
    , complexity
    ) where

import Algebra.PartialOrd
    ( PartialOrd (..)
    )
import Data.Maybe
    ( fromMaybe
    )
import DeltaQ.Class
    ( DeltaQ (..)
    , Outcome (..)
    , eventuallyFromMaybe
    )
import Control.DeepSeq
    ( NFData
    )
import Numeric.Function.Piecewise
    ( Piecewise
    )
import Numeric.Measure.Finite.Mixed
    ( Measure
    )
import Numeric.Polynomial.Simple
    ( Poly
    )
import Numeric.Probability.Moments
    ( Moments (..)
    )

import qualified Data.Function.Class as Function
import qualified Numeric.Function.Piecewise as Piecewise
import qualified Numeric.Measure.Finite.Mixed as Measure
import qualified Numeric.Measure.Probability as Prob
import qualified Numeric.Polynomial.Simple as Poly

{-----------------------------------------------------------------------------
    Type
------------------------------------------------------------------------------}
-- | Probability distribution of durations.
newtype DQ = DQ (Measure Rational)
    deriving (DQ -> DQ -> Bool
(DQ -> DQ -> Bool) -> (DQ -> DQ -> Bool) -> Eq DQ
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: DQ -> DQ -> Bool
== :: DQ -> DQ -> Bool
$c/= :: DQ -> DQ -> Bool
/= :: DQ -> DQ -> Bool
Eq, Int -> DQ -> ShowS
[DQ] -> ShowS
DQ -> String
(Int -> DQ -> ShowS)
-> (DQ -> String) -> ([DQ] -> ShowS) -> Show DQ
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> DQ -> ShowS
showsPrec :: Int -> DQ -> ShowS
$cshow :: DQ -> String
show :: DQ -> String
$cshowList :: [DQ] -> ShowS
showList :: [DQ] -> ShowS
Show, DQ -> ()
(DQ -> ()) -> NFData DQ
forall a. (a -> ()) -> NFData a
$crnf :: DQ -> ()
rnf :: DQ -> ()
NFData)

-- | Get the distribution function as piecewise function of polynomials.
distribution :: DQ -> Piecewise (Poly Rational)
distribution :: DQ -> Piecewise (Poly Rational)
distribution (DQ Measure Rational
m) = Measure Rational -> Piecewise (Poly Rational)
forall a. (Ord a, Num a) => Measure a -> Piecewise (Poly a)
Measure.distribution Measure Rational
m

-- | Interpret a finite, signed 'Measure' as a probability distribution.
--
-- In order to admit an interpretation as probability, the measure needs
-- to be positive.
-- This condition is checked, and if it does not hold,
-- the function returns 'Nothing'.
fromPositiveMeasure :: Measure Rational -> Maybe DQ
fromPositiveMeasure :: Measure Rational -> Maybe DQ
fromPositiveMeasure Measure Rational
m
    | Measure Rational -> Bool
forall a. (Ord a, Num a, Fractional a) => Measure a -> Bool
Measure.isPositive Measure Rational
m = DQ -> Maybe DQ
forall a. a -> Maybe a
Just (Measure Rational -> DQ
unsafeFromPositiveMeasure Measure Rational
m)
    | Bool
otherwise = Maybe DQ
forall a. Maybe a
Nothing

-- | Interpret a finite, positive 'Measure' as a probability distribution.
--
-- /The precondition that the measure is positive is not checked!/
unsafeFromPositiveMeasure :: Measure Rational -> DQ
unsafeFromPositiveMeasure :: Measure Rational -> DQ
unsafeFromPositiveMeasure = Measure Rational -> DQ
DQ

-- | Helper function for lifting a binary operation on distribution functions.
onDistribution2
    :: (a ~ Rational)
    => String
    -> (Piecewise (Poly a) -> Piecewise (Poly a) -> Piecewise (Poly a))
    -> DQ -> DQ -> DQ
onDistribution2 :: forall a.
(a ~ Rational) =>
String
-> (Piecewise (Poly a) -> Piecewise (Poly a) -> Piecewise (Poly a))
-> DQ
-> DQ
-> DQ
onDistribution2 String
err Piecewise (Poly a) -> Piecewise (Poly a) -> Piecewise (Poly a)
f (DQ Measure Rational
mx) (DQ Measure Rational
my) =
    Measure Rational -> DQ
DQ
    (Measure Rational -> DQ) -> Measure Rational -> DQ
forall a b. (a -> b) -> a -> b
$ Measure Rational -> Maybe (Measure Rational) -> Measure Rational
forall a. a -> Maybe a -> a
fromMaybe Measure Rational
impossible
    (Maybe (Measure Rational) -> Measure Rational)
-> Maybe (Measure Rational) -> Measure Rational
forall a b. (a -> b) -> a -> b
$ Piecewise (Poly a) -> Maybe (Measure a)
forall a. (Ord a, Num a) => Piecewise (Poly a) -> Maybe (Measure a)
Measure.fromDistribution
    (Piecewise (Poly a) -> Maybe (Measure a))
-> Piecewise (Poly a) -> Maybe (Measure a)
forall a b. (a -> b) -> a -> b
$ Piecewise (Poly a) -> Piecewise (Poly a) -> Piecewise (Poly a)
f (Measure a -> Piecewise (Poly a)
forall a. (Ord a, Num a) => Measure a -> Piecewise (Poly a)
Measure.distribution Measure a
Measure Rational
mx) (Measure a -> Piecewise (Poly a)
forall a. (Ord a, Num a) => Measure a -> Piecewise (Poly a)
Measure.distribution Measure a
Measure Rational
my)
  where
    impossible :: Measure Rational
impossible = String -> Measure Rational
forall a. HasCallStack => String -> a
error (String -> Measure Rational) -> String -> Measure Rational
forall a b. (a -> b) -> a -> b
$ String
"impossible: not a finite measure in " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
err

-- | Size of the representation of a probability distribution,
-- i.e. number of pieces of the piecewise function and degrees
-- of the polynomials.
--
-- This quantity is relevant to stating and analyzing
-- the asymptotic time complexity of operations.
complexity :: DQ -> Int
complexity :: DQ -> Int
complexity (DQ Measure Rational
m) = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum (((Rational, Poly Rational) -> Int)
-> [(Rational, Poly Rational)] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Rational, Poly Rational) -> Int
forall {a}. (a, Poly Rational) -> Int
complexityOfPiece [(Rational, Poly Rational)]
[(Domain (Poly Rational), Poly Rational)]
pieces)
  where
    pieces :: [(Domain (Poly Rational), Poly Rational)]
pieces = Piecewise (Poly Rational)
-> [(Domain (Poly Rational), Poly Rational)]
forall o. Ord (Domain o) => Piecewise o -> [(Domain o, o)]
Piecewise.toAscPieces (Piecewise (Poly Rational)
 -> [(Domain (Poly Rational), Poly Rational)])
-> Piecewise (Poly Rational)
-> [(Domain (Poly Rational), Poly Rational)]
forall a b. (a -> b) -> a -> b
$ Measure Rational -> Piecewise (Poly Rational)
forall a. (Ord a, Num a) => Measure a -> Piecewise (Poly a)
Measure.distribution Measure Rational
m
    complexityOfPiece :: (a, Poly Rational) -> Int
complexityOfPiece = (Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int -> Int)
-> ((a, Poly Rational) -> Int) -> (a, Poly Rational) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Int -> Int)
-> ((a, Poly Rational) -> Int) -> (a, Poly Rational) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly Rational -> Int
forall a. (Eq a, Num a) => Poly a -> Int
Poly.degree (Poly Rational -> Int)
-> ((a, Poly Rational) -> Poly Rational)
-> (a, Poly Rational)
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, Poly Rational) -> Poly Rational
forall a b. (a, b) -> b
snd

{-----------------------------------------------------------------------------
    Operations
------------------------------------------------------------------------------}
instance Outcome DQ where
    type Duration DQ = Rational

    never :: DQ
never = Measure Rational -> DQ
DQ Measure Rational
forall a. Num a => Measure a
Measure.zero

    wait :: Duration DQ -> DQ
wait Duration DQ
t = Measure Rational -> DQ
DQ (Measure Rational -> DQ) -> Measure Rational -> DQ
forall a b. (a -> b) -> a -> b
$ Rational -> Measure Rational
forall a. (Ord a, Num a) => a -> Measure a
Measure.dirac Rational
Duration DQ
t

    sequentially :: DQ -> DQ -> DQ
sequentially (DQ Measure Rational
mx) (DQ Measure Rational
my) = Measure Rational -> DQ
DQ (Measure Rational -> Measure Rational -> Measure Rational
forall a.
(Ord a, Num a, Fractional a) =>
Measure a -> Measure a -> Measure a
Measure.convolve Measure Rational
mx Measure Rational
my)

    firstToFinish :: DQ -> DQ -> DQ
firstToFinish = String
-> (Piecewise (Poly Rational)
    -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
-> DQ
-> DQ
-> DQ
forall a.
(a ~ Rational) =>
String
-> (Piecewise (Poly a) -> Piecewise (Poly a) -> Piecewise (Poly a))
-> DQ
-> DQ
-> DQ
onDistribution2 String
"firstToFinish" ((Piecewise (Poly Rational)
  -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
 -> DQ -> DQ -> DQ)
-> (Piecewise (Poly Rational)
    -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
-> DQ
-> DQ
-> DQ
forall a b. (a -> b) -> a -> b
$ \Piecewise (Poly Rational)
x Piecewise (Poly Rational)
y -> Piecewise (Poly Rational)
x Piecewise (Poly Rational)
-> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
forall a. Num a => a -> a -> a
+ Piecewise (Poly Rational)
y Piecewise (Poly Rational)
-> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
forall a. Num a => a -> a -> a
- Piecewise (Poly Rational)
x Piecewise (Poly Rational)
-> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
forall a. Num a => a -> a -> a
* Piecewise (Poly Rational)
y

    lastToFinish :: DQ -> DQ -> DQ
lastToFinish = String
-> (Piecewise (Poly Rational)
    -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
-> DQ
-> DQ
-> DQ
forall a.
(a ~ Rational) =>
String
-> (Piecewise (Poly a) -> Piecewise (Poly a) -> Piecewise (Poly a))
-> DQ
-> DQ
-> DQ
onDistribution2 String
"lastToFinish" Piecewise (Poly Rational)
-> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
forall a. Num a => a -> a -> a
(*)

instance DeltaQ DQ where
    type Probability DQ = Rational

    choice :: Probability DQ -> DQ -> DQ -> DQ
choice Probability DQ
p = String
-> (Piecewise (Poly Rational)
    -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
-> DQ
-> DQ
-> DQ
forall a.
(a ~ Rational) =>
String
-> (Piecewise (Poly a) -> Piecewise (Poly a) -> Piecewise (Poly a))
-> DQ
-> DQ
-> DQ
onDistribution2 String
"choice" ((Piecewise (Poly Rational)
  -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
 -> DQ -> DQ -> DQ)
-> (Piecewise (Poly Rational)
    -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
-> DQ
-> DQ
-> DQ
forall a b. (a -> b) -> a -> b
$ \Piecewise (Poly Rational)
x Piecewise (Poly Rational)
y ->
        Rational -> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
scale Rational
Probability DQ
p Piecewise (Poly Rational)
x Piecewise (Poly Rational)
-> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
forall a. Num a => a -> a -> a
+ Rational -> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
scale (Rational
1 Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
- Rational
Probability DQ
p) Piecewise (Poly Rational)
y
      where
        scale :: Rational -> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
scale = (Poly Rational -> Poly Rational)
-> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
forall o o'.
(Domain o ~ Domain o') =>
(o -> o') -> Piecewise o -> Piecewise o'
Piecewise.mapPieces ((Poly Rational -> Poly Rational)
 -> Piecewise (Poly Rational) -> Piecewise (Poly Rational))
-> (Rational -> Poly Rational -> Poly Rational)
-> Rational
-> Piecewise (Poly Rational)
-> Piecewise (Poly Rational)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rational -> Poly Rational -> Poly Rational
forall a. Num a => a -> Poly a -> Poly a
Poly.scale

    uniform :: Duration DQ -> Duration DQ -> DQ
uniform Duration DQ
a = Measure Rational -> DQ
DQ (Measure Rational -> DQ)
-> (Rational -> Measure Rational) -> Rational -> DQ
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rational -> Rational -> Measure Rational
forall a. (Ord a, Num a, Fractional a) => a -> a -> Measure a
Measure.uniform Rational
Duration DQ
a

    successWithin :: DQ -> Duration DQ -> Probability DQ
successWithin (DQ Measure Rational
m) = Piecewise (Poly Rational)
-> Domain (Piecewise (Poly Rational))
-> Codomain (Piecewise (Poly Rational))
forall f. Function f => f -> Domain f -> Codomain f
Function.eval (Measure Rational -> Piecewise (Poly Rational)
forall a. (Ord a, Num a) => Measure a -> Piecewise (Poly a)
Measure.distribution Measure Rational
m)

    failure :: DQ -> Probability DQ
failure (DQ Measure Rational
m) = Rational
1 Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
- Measure Rational -> Rational
forall a. (Ord a, Num a) => Measure a -> a
Measure.total Measure Rational
m

    quantile :: DQ -> Probability DQ -> Eventually (Duration DQ)
quantile (DQ Measure Rational
m) Probability DQ
p =
        Maybe (Duration DQ) -> Eventually (Duration DQ)
forall a. Maybe a -> Eventually a
eventuallyFromMaybe
        (Maybe (Duration DQ) -> Eventually (Duration DQ))
-> Maybe (Duration DQ) -> Eventually (Duration DQ)
forall a b. (a -> b) -> a -> b
$ Piecewise (Poly Rational) -> Rational -> Maybe Rational
forall a. (a ~ Rational) => Piecewise (Poly a) -> a -> Maybe a
quantileFromMonotone (Measure Rational -> Piecewise (Poly Rational)
forall a. (Ord a, Num a) => Measure a -> Piecewise (Poly a)
Measure.distribution Measure Rational
m) Rational
Probability DQ
p

    earliest :: DQ -> Eventually (Duration DQ)
earliest (DQ Measure Rational
m) = Maybe (Duration DQ) -> Eventually (Duration DQ)
forall a. Maybe a -> Eventually a
eventuallyFromMaybe (Maybe (Duration DQ) -> Eventually (Duration DQ))
-> Maybe (Duration DQ) -> Eventually (Duration DQ)
forall a b. (a -> b) -> a -> b
$ ((Rational, Rational) -> Duration DQ)
-> Maybe (Rational, Rational) -> Maybe (Duration DQ)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Rational, Rational) -> Rational
(Rational, Rational) -> Duration DQ
forall a b. (a, b) -> a
fst (Maybe (Rational, Rational) -> Maybe (Duration DQ))
-> Maybe (Rational, Rational) -> Maybe (Duration DQ)
forall a b. (a -> b) -> a -> b
$ Measure Rational -> Maybe (Rational, Rational)
forall a. (Ord a, Num a) => Measure a -> Maybe (a, a)
Measure.support Measure Rational
m

    deadline :: DQ -> Eventually (Duration DQ)
deadline (DQ Measure Rational
m)= Maybe (Duration DQ) -> Eventually (Duration DQ)
forall a. Maybe a -> Eventually a
eventuallyFromMaybe (Maybe (Duration DQ) -> Eventually (Duration DQ))
-> Maybe (Duration DQ) -> Eventually (Duration DQ)
forall a b. (a -> b) -> a -> b
$ ((Rational, Rational) -> Duration DQ)
-> Maybe (Rational, Rational) -> Maybe (Duration DQ)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Rational, Rational) -> Rational
(Rational, Rational) -> Duration DQ
forall a b. (a, b) -> b
snd (Maybe (Rational, Rational) -> Maybe (Duration DQ))
-> Maybe (Rational, Rational) -> Maybe (Duration DQ)
forall a b. (a -> b) -> a -> b
$ Measure Rational -> Maybe (Rational, Rational)
forall a. (Ord a, Num a) => Measure a -> Maybe (a, a)
Measure.support Measure Rational
m

-- | Partial order of cumulative distribution functions.
--
-- @'leq' x y@ holds if and only if for all completion times @t@,
-- the probability to succeed within the time @t@
-- is always larger (or equal) for @x@ compared to @y@.
-- In other words, @x@ has a higher probability of completing faster.
--
-- > x `leq` y  <=>  ∀ t. successWithin x t >= successWithin y t
instance PartialOrd DQ where
    DQ
m1 leq :: DQ -> DQ -> Bool
`leq` DQ
m2 =
        (Segment Rational Rational -> Bool)
-> [Segment Rational Rational] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Segment Rational Rational -> Bool
forall a. (a ~ Rational) => Segment a a -> Bool
isNonNegativeOnSegment
        ([Segment Rational Rational] -> Bool)
-> [Segment Rational Rational] -> Bool
forall a b. (a -> b) -> a -> b
$ Piecewise (Poly Rational) -> [Segment Rational Rational]
forall a. (a ~ Rational) => Piecewise (Poly a) -> [Segment a a]
toSegments
        (Piecewise (Poly Rational) -> [Segment Rational Rational])
-> Piecewise (Poly Rational) -> [Segment Rational Rational]
forall a b. (a -> b) -> a -> b
$ DQ -> Piecewise (Poly Rational)
distribution DQ
m1 Piecewise (Poly Rational)
-> Piecewise (Poly Rational) -> Piecewise (Poly Rational)
forall a. Num a => a -> a -> a
- DQ -> Piecewise (Poly Rational)
distribution DQ
m2

{-----------------------------------------------------------------------------
    Operations
    Helper functions
------------------------------------------------------------------------------}
-- | Helper type for segements of a piecewise functions.
data Segment a b
    = Jump a (b,b)
    | Polynomial (a,a) (b,b) (Poly a)
    | End a b
    deriving (Segment a b -> Segment a b -> Bool
(Segment a b -> Segment a b -> Bool)
-> (Segment a b -> Segment a b -> Bool) -> Eq (Segment a b)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a b.
(Num a, Eq a, Eq b) =>
Segment a b -> Segment a b -> Bool
$c== :: forall a b.
(Num a, Eq a, Eq b) =>
Segment a b -> Segment a b -> Bool
== :: Segment a b -> Segment a b -> Bool
$c/= :: forall a b.
(Num a, Eq a, Eq b) =>
Segment a b -> Segment a b -> Bool
/= :: Segment a b -> Segment a b -> Bool
Eq, Int -> Segment a b -> ShowS
[Segment a b] -> ShowS
Segment a b -> String
(Int -> Segment a b -> ShowS)
-> (Segment a b -> String)
-> ([Segment a b] -> ShowS)
-> Show (Segment a b)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall a b. (Show a, Show b) => Int -> Segment a b -> ShowS
forall a b. (Show a, Show b) => [Segment a b] -> ShowS
forall a b. (Show a, Show b) => Segment a b -> String
$cshowsPrec :: forall a b. (Show a, Show b) => Int -> Segment a b -> ShowS
showsPrec :: Int -> Segment a b -> ShowS
$cshow :: forall a b. (Show a, Show b) => Segment a b -> String
show :: Segment a b -> String
$cshowList :: forall a b. (Show a, Show b) => [Segment a b] -> ShowS
showList :: [Segment a b] -> ShowS
Show)

-- | Helper function that elaborates a piecewise function
-- into a list of segments.
toSegments :: (a ~ Rational) => Piecewise (Poly a) -> [Segment a a]
toSegments :: forall a. (a ~ Rational) => Piecewise (Poly a) -> [Segment a a]
toSegments = Poly a -> [(a, Poly a)] -> [Segment a a]
forall {b}.
(Ord b, Num b) =>
Poly b -> [(b, Poly b)] -> [Segment b b]
goJump Poly a
0 ([(a, Poly a)] -> [Segment a a])
-> (Piecewise (Poly a) -> [(a, Poly a)])
-> Piecewise (Poly a)
-> [Segment a a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Piecewise (Poly a) -> [(a, Poly a)]
Piecewise (Poly a) -> [(Domain (Poly a), Poly a)]
forall o. Ord (Domain o) => Piecewise o -> [(Domain o, o)]
Piecewise.toAscPieces
  where
    goJump :: Poly b -> [(b, Poly b)] -> [Segment b b]
goJump Poly b
_ [] = []
    goJump Poly b
prev ((b
x1, Poly b
o) : [(b, Poly b)]
xos)
        | b
y1 b -> b -> b
forall a. Num a => a -> a -> a
- b
y0 b -> b -> Bool
forall a. Ord a => a -> a -> Bool
> b
0 = b -> (b, b) -> Segment b b
forall a b. a -> (b, b) -> Segment a b
Jump b
x1 (b
y0, b
y1) Segment b b -> [Segment b b] -> [Segment b b]
forall a. a -> [a] -> [a]
: [Segment b b]
nexts
        | Bool
otherwise = [Segment b b]
nexts
      where
        y1 :: b
y1 = Poly b -> b -> b
forall a. Num a => Poly a -> a -> a
Poly.eval Poly b
o b
x1
        y0 :: b
y0 = Poly b -> b -> b
forall a. Num a => Poly a -> a -> a
Poly.eval Poly b
prev b
x1
        nexts :: [Segment b b]
nexts = b -> b -> Poly b -> [(b, Poly b)] -> [Segment b b]
goPoly b
x1 b
y1 Poly b
o [(b, Poly b)]
xos

    goPoly :: b -> b -> Poly b -> [(b, Poly b)] -> [Segment b b]
goPoly b
x1 b
y1 Poly b
o [] =
        b -> b -> Segment b b
forall a b. a -> b -> Segment a b
End b
x1 b
y1 Segment b b -> [Segment b b] -> [Segment b b]
forall a. a -> [a] -> [a]
: Poly b -> [(b, Poly b)] -> [Segment b b]
goJump Poly b
o []
    goPoly b
x1 b
y1 Poly b
o xos :: [(b, Poly b)]
xos@((b
x2, Poly b
_) : [(b, Poly b)]
_) =
        (b, b) -> (b, b) -> Poly b -> Segment b b
forall a b. (a, a) -> (b, b) -> Poly a -> Segment a b
Polynomial (b
x1, b
x2) (b
y1, Poly b -> b -> b
forall a. Num a => Poly a -> a -> a
Poly.eval Poly b
o b
x2) Poly b
o Segment b b -> [Segment b b] -> [Segment b b]
forall a. a -> [a] -> [a]
: Poly b -> [(b, Poly b)] -> [Segment b b]
goJump Poly b
o [(b, Poly b)]
xos
        -- TODO: What about the case where y1 == y2, i.e. a constant Polynomial?

{-----------------------------------------------------------------------------
    Operations
    quantile
------------------------------------------------------------------------------}
-- | Compute a quantile from a monotonically increasing function.
quantileFromMonotone :: (a ~ Rational) => Piecewise (Poly a) -> a -> Maybe a
quantileFromMonotone :: forall a. (a ~ Rational) => Piecewise (Poly a) -> a -> Maybe a
quantileFromMonotone Piecewise (Poly a)
pieces = [Segment Rational Rational] -> Rational -> Maybe Rational
findInSegments [Segment a a]
[Segment Rational Rational]
segments
  where
    segments :: [Segment a a]
segments = Piecewise (Poly a) -> [Segment a a]
forall a. (a ~ Rational) => Piecewise (Poly a) -> [Segment a a]
toSegments Piecewise (Poly a)
pieces

    findInSegments :: [Segment Rational Rational] -> Rational -> Maybe Rational
findInSegments [Segment Rational Rational]
_ Rational
0
        = Rational -> Maybe Rational
forall a. a -> Maybe a
Just Rational
0
    findInSegments [] Rational
_
        = Maybe Rational
forall a. Maybe a
Nothing
    findInSegments (Jump Rational
x1 (Rational
y1, Rational
y2) : [Segment Rational Rational]
xys) Rational
y
        | Rational
y1 Rational -> Rational -> Bool
forall a. Ord a => a -> a -> Bool
< Rational
y Bool -> Bool -> Bool
&& Rational
y Rational -> Rational -> Bool
forall a. Ord a => a -> a -> Bool
<= Rational
y2 = Rational -> Maybe Rational
forall a. a -> Maybe a
Just Rational
x1
        | Bool
otherwise = [Segment Rational Rational] -> Rational -> Maybe Rational
findInSegments [Segment Rational Rational]
xys Rational
y
    findInSegments (Polynomial (Rational
x1, Rational
x2) (Rational
y1, Rational
y2) Poly Rational
o : [Segment Rational Rational]
xys) Rational
y
        | Rational
y1 Rational -> Rational -> Bool
forall a. Ord a => a -> a -> Bool
< Rational
y Bool -> Bool -> Bool
&& Rational
y Rational -> Rational -> Bool
forall a. Ord a => a -> a -> Bool
<= Rational
y2 = Rational
-> Rational
-> (Rational, Rational)
-> Poly Rational
-> Maybe Rational
forall a.
(Ord a, Num a, Eq a, Fractional a) =>
a -> a -> (a, a) -> Poly a -> Maybe a
Poly.root Rational
precision Rational
y (Rational
x1, Rational
x2) Poly Rational
o
        | Bool
otherwise = [Segment Rational Rational] -> Rational -> Maybe Rational
findInSegments [Segment Rational Rational]
xys Rational
y
    findInSegments (End Rational
x1 Rational
y1 : [Segment Rational Rational]
_) Rational
y
        | Rational
y1 Rational -> Rational -> Bool
forall a. Eq a => a -> a -> Bool
== Rational
y = Rational -> Maybe Rational
forall a. a -> Maybe a
Just Rational
x1
        | Bool
otherwise = Maybe Rational
forall a. Maybe a
Nothing

precision :: Rational
precision :: Rational
precision = Rational
1 Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/ Rational
10Rational -> Integer -> Rational
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
10 :: Integer)

{-----------------------------------------------------------------------------
    Operations
    meetsQTA
------------------------------------------------------------------------------}
-- | Test whether the given probability distribution of completion times
-- is equal to or better than a given
-- __quantitative timeliness agreement__ (QTA).
--
-- Synonym for `leq` of the partial order,
--
-- > p `meetsQTA` qta  =  p `leq` qta
meetsQTA :: DQ -> DQ -> Bool
meetsQTA :: DQ -> DQ -> Bool
meetsQTA = DQ -> DQ -> Bool
forall a. PartialOrd a => a -> a -> Bool
leq

isNonNegativeOnSegment :: (a ~ Rational) => Segment a a -> Bool
isNonNegativeOnSegment :: forall a. (a ~ Rational) => Segment a a -> Bool
isNonNegativeOnSegment (Jump a
_ (a
y1, a
y2)) =
    a
y1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
0 Bool -> Bool -> Bool
&& a
y2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
0
isNonNegativeOnSegment (Polynomial (a
x1, a
x2) (a, a)
_ Poly a
poly) =
    Maybe Ordering
compareToZero Maybe Ordering -> Maybe Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just Ordering
GT Bool -> Bool -> Bool
|| Maybe Ordering
compareToZero Maybe Ordering -> Maybe Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just Ordering
EQ
  where
    compareToZero :: Maybe Ordering
compareToZero = (a, a, Poly a) -> Maybe Ordering
forall a.
(Fractional a, Eq a, Ord a) =>
(a, a, Poly a) -> Maybe Ordering
Poly.compareToZero (a
x1, a
x2, Poly a
poly)
isNonNegativeOnSegment (End a
_ a
y) =
    a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
0

{-----------------------------------------------------------------------------
    Operations
    Moments
------------------------------------------------------------------------------}
-- | Compute the success probability of a 'DQ',
-- and the first commonly used 'Moments' of the
-- probability distribution conditioned on success.
moments :: DQ -> (Rational, Moments Rational)
moments :: DQ -> (Rational, Moments Rational)
moments (DQ Measure Rational
m)
    | Rational
success Rational -> Rational -> Bool
forall a. Eq a => a -> a -> Bool
== Rational
0 =
        (Rational
0, Moments{mean :: Rational
mean = Rational
0, variance :: Rational
variance = Rational
0, skewness :: Rational
skewness = Rational
0, kurtosis :: Rational
kurtosis = Rational
1})
    | Bool
otherwise =
        (Rational
success, Prob Rational -> Moments Rational
forall a. (Ord a, Num a, Fractional a) => Prob a -> Moments a
Prob.moments Prob Rational
conditional)
  where
    success :: Rational
success = Measure Rational -> Rational
forall a. (Ord a, Num a) => Measure a -> a
Measure.total Measure Rational
m
    conditional :: Prob Rational
conditional = Measure Rational -> Prob Rational
forall a. Measure a -> Prob a
Prob.unsafeFromMeasure (Measure Rational -> Prob Rational)
-> Measure Rational -> Prob Rational
forall a b. (a -> b) -> a -> b
$ Rational -> Measure Rational -> Measure Rational
forall a. (Ord a, Num a) => a -> Measure a -> Measure a
Measure.scale (Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
success) Measure Rational
m