Random.hs

-- | 
-- Copyright: (c) VegOwOtenks
-- License: AGPL3
--
-- A random monad based on the Infinitree, allows for efficient cancellation of chained effects.
-- See the discussion here: https://discourse.haskell.org/t/uploading-first-package-to-hackage-endorsements-for-infinitree/13082/8
--
-- This is an adaptation of the 'Prob' monad used in LazyPPL: https://hackage.haskell.org/package/lazyppl-1.0/docs/LazyPPL.html#t:Tree
--
-- The trade-offs are as follows:
--
-- * Discarding random values
--
--     * LazyPPL will not discard any value if it is needed later
--     * Infinitree has to discard generated values to split computations
--
-- * Generator State
--
--     * Infinitree calculates a logarithmic amount of generators
--     * LazyPPL has to calculate most of the generators in the path to your computation. Depending on association order the amount may be linear or better
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE InstanceSigs #-}
module Data.Infinitree.Random (build, Random(..), sample, run, runTree) where
import Data.Infinitree (Infinitree (Branch))
import qualified System.Random (Random)
import qualified System.Random as Random hiding (Random)
import qualified Data.Infinitree as Infinitree

-- | Newtype Wrapper over functions. The tree in the argument provides infinite random values of a singular type.
--
-- Due to the ability to split generators, calculations in this monad could be parallelized.
--
-- TODO: Explicit Parallel computation support

newtype Random random result = Random (Infinitree random -> result)
  deriving stock (Functor)

instance Applicative (Random random) where
  pure :: a -> Random random a
  pure a = Random $ const a
  (<*>) :: Random random (a -> b) -> Random random a -> Random random b
  (<*>) (Random makeF) (Random makeA) = Random $ \ (Branch left _ right) -> let
    f = makeF left
    a = makeA right
    in f a

instance Monad (Random random) where
  (>>=) :: Random random a -> (a -> Random random b) -> Random random b
  (>>=) (Random makeA) f = Random $ \ (Branch left _ right) -> let
    a = makeA left
    (Random makeB) = f a
    in makeB right

-- | Extract a single random value

sample :: Random result result
sample = Random $ \ (Branch _ x _) -> x

-- | Build an infinitree of random values, this hides the used generator
--
-- Name conflicts force to write this out

build :: (System.Random.Random a, Random.SplitGen g) => g -> Infinitree a
build generator = let
  (leaf, generator') = Random.random generator
  (generatorLeft, generatorRight) = Random.splitGen generator'
  in Infinitree.Branch (build generatorLeft) leaf (build generatorRight)

-- | Given an initial generator, run the entire computation with it as the seed.

run :: (System.Random.Random random, Random.SplitGen g) => Random random a -> g -> a
run (Random makeA) = makeA . build

-- | Evaluate a computation, using a pre-build tree as the source of randomness.

runTree :: Random random result -> Infinitree random -> result
runTree (Random makeA) = makeA