Safe Haskell	Safe
Language	GHC2021

LambdaUC.Syntax.PrAlgo

Contents

Syntax
Distributions
Interpretations
- Pure
- Impure

Synopsis

newtype PrAlgo a = PrAlgo {
- runAlgo :: Free AlgoActions a
}
class Monad m => MonadRand (m :: Type -> Type) where
- rand :: m Bool
data AlgoActions (a :: Type) where
- RandAction :: (Bool -> a) -> AlgoActions a
class UniformDist s where
- uniformDist :: forall m. MonadRand m => m s
rangeDist :: MonadRand m => Integer -> Integer -> m Integer
pr :: PrAlgo Bool -> Rational
withRandomBits :: [Bool] -> PrAlgo a -> Either (Bool -> PrAlgo a) a
collectRandomBits :: PrAlgo a -> PrAlgo (a, [Bool])
toMonadRand :: MonadRand m => PrAlgo a -> m a
runIO :: PrAlgo a -> IO a

Syntax

This section defines the syntax of PrAlgo monad for probabilistic algorithms.

newtype PrAlgo a #

Probabilistic algorithm. Allows only one action rand to sample a random bit.

Use with ExceptT, MaybeT or WriterT if you want extra side-effects such exceptions or writing debug messages.

Constructors

PrAlgo
Fields runAlgo :: Free AlgoActions a

Instances

Instances details

Applicative PrAlgo #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods pure :: a -> PrAlgo a # (<>) :: PrAlgo (a -> b) -> PrAlgo a -> PrAlgo b # liftA2 :: (a -> b -> c) -> PrAlgo a -> PrAlgo b -> PrAlgo c # (>) :: PrAlgo a -> PrAlgo b -> PrAlgo b # (<*) :: PrAlgo a -> PrAlgo b -> PrAlgo a #
Functor PrAlgo #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods fmap :: (a -> b) -> PrAlgo a -> PrAlgo b # (<$) :: a -> PrAlgo b -> PrAlgo a #
Monad PrAlgo #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods (>>=) :: PrAlgo a -> (a -> PrAlgo b) -> PrAlgo b # (>>) :: PrAlgo a -> PrAlgo b -> PrAlgo b # return :: a -> PrAlgo a #
MonadRand PrAlgo #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods rand :: PrAlgo Bool #

class Monad m => MonadRand (m :: Type -> Type) where #

Class of monads that allow sampling a random bit.

Methods

rand :: m Bool #

Sample a random value.

Instances

Instances details

MonadRand IO #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods rand :: IO Bool #
MonadRand PrAlgo #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods rand :: PrAlgo Bool #
(MonadTrans t, MonadRand m) => MonadRand (t m) #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods rand :: t m Bool #
(XMonadTrans t, MonadRand m, bef ~ aft) => MonadRand (t m bef aft) #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods rand :: t m bef aft Bool #
MonadRand (AsyncExT ex ports i i) #
Instance details Defined in LambdaUC.Syntax.Async Methods rand :: AsyncExT ex ports i i Bool #

data AlgoActions (a :: Type) where #

Constructors

RandAction :: (Bool -> a) -> AlgoActions a

Instances

Instances details

Functor AlgoActions #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods fmap :: (a -> b) -> AlgoActions a -> AlgoActions b # (<$) :: a -> AlgoActions b -> AlgoActions a #

Distributions

Common probability distributions.

class UniformDist s where #

Methods

uniformDist :: forall m. MonadRand m => m s #

Sample a uniformly random value from s

Instances

Instances details

UniformDist Bool #
Instance details Defined in LambdaUC.Syntax.PrAlgo Methods uniformDist :: MonadRand m => m Bool #

rangeDist :: MonadRand m => Integer -> Integer -> m Integer #

Sample a random value from the given range of Integer

Interpretations

Pure

These are the pure interpretations of PrAlgo, i.e. those that do not require IO.

pr :: PrAlgo Bool -> Rational #

Calculate the probability of a random event.

You can see this as a pure interpretation (not using IO) of PrAlgo.

withRandomBits :: [Bool] -> PrAlgo a -> Either (Bool -> PrAlgo a) a #

Run a probabilistic algorithm supplying the given stream of bits.

If the number of supplied bits was sufficient for all the rand requests that algorithm made until it terminated, evaluates to Right of the result. If the bits were exhausted before the algorithm was ready to terminate, return Left of the continuation with remaining computations.

collectRandomBits :: PrAlgo a -> PrAlgo (a, [Bool]) #

Run a probabilistic algorithm, collecting the random bits it samples.

This is, in some sense, dual to withRandomBits: collected randomBits can be fed back to an algorithm to repeat its execution.

Impure

The following are interpretations of PrAlgo in IO.

toMonadRand :: MonadRand m => PrAlgo a -> m a #

Convert an PrAlgo to any monad that implements MonadRand.

runIO :: PrAlgo a -> IO a #

Run a probabilistic algorithm in IO.

The random bits are faithfully sampled using OS RNG.