    {-# LANGUAGE CPP #-}
    {-# LANGUAGE FlexibleInstances #-}
    {-# LANGUAGE FunctionalDependencies #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE Safe #-}
    {-# LANGUAGE UndecidableInstances #-}

    -- |
    -- Module       :  Control.Monad.Random.Class
    -- Copyright    :  (c) Brent Yorgey 2016
    -- License      :  BSD3 (see LICENSE)
    -- Maintainer   :  byorgey@gmail.com
    --
    -- The 'MonadRandom', 'MonadSplit', and 'MonadInterleave' classes.
    --
    -- * 'MonadRandom' abstracts over monads with the capability of
    --   generating random values.
    --
    -- * 'MonadSplit' abstracts over random monads with the ability to get a
    --   split generator state.  It is not very useful but kept here for
    --   backwards compatibility.
    --
    -- * 'MonadInterleave' abstracts over random monads supporting an
    --   'interleave' operation, which allows sequencing computations which do
    --   not depend on each other's random generator state, by splitting the
    --   generator between them.
    --
    -- This module also defines convenience functions for sampling from a
    -- given collection of values, either uniformly or according to given
    -- weights.
    module Control.Monad.Random.Class (
      -- * MonadRandom
      MonadRandom (..),

      -- * MonadSplit
      MonadSplit (..),

      -- * MonadInterleave
      MonadInterleave (..),

      -- * Sampling functions
      fromList,
      fromListMay,
      uniform,
      uniformMay,
      weighted,
      weightedMay,
    ) where

    import Control.Monad
    import Control.Monad.Trans.Class
    import Control.Monad.Trans.Cont
    import Control.Monad.Trans.Except
    import Control.Monad.Trans.Identity
    import Control.Monad.Trans.Maybe
    import qualified Control.Monad.Trans.RWS.Lazy as LazyRWS
    import qualified Control.Monad.Trans.RWS.Strict as StrictRWS
    import Control.Monad.Trans.Reader
    import qualified Control.Monad.Trans.State.Lazy as LazyState
    import qualified Control.Monad.Trans.State.Strict as StrictState
    import qualified Control.Monad.Trans.Writer.Lazy as LazyWriter
    import qualified Control.Monad.Trans.Writer.Strict as StrictWriter
    import qualified Data.Foldable as F
    import Data.Word (Word64)
    import qualified System.Random as Random

    #if MIN_VERSION_base(4,8,0)
    #else
    import           Data.Monoid                       (Monoid)
    #endif

    ------------------------------------------------------------
    -- MonadRandom
    ------------------------------------------------------------

    -- | With a source of random number supply in hand, the 'MonadRandom' class
    -- allows the programmer to extract random values of a variety of types.
    class Monad m => MonadRandom m where
      -- | Takes a range /(lo,hi)/ and a random number generator
      -- /g/, and returns a computation that returns a random value uniformly
      -- distributed in the closed interval /[lo,hi]/, together with a new
      -- generator. It is unspecified what happens if /lo>hi/. For continuous
      -- types there is no requirement that the values /lo/ and /hi/ are ever
      -- produced, but they may be, depending on the implementation and the
      -- interval.
      --
      -- See 'System.Random.randomR' for details.
      getRandomR :: Random.Random a => (a, a) -> m a

      -- | The same as 'getRandomR', but using a default range determined by the type:
      --
      -- * For bounded types (instances of 'Bounded', such as 'Char'),
      --   the range is normally the whole type.
      --
      -- * For fractional types, the range is normally the semi-closed interval
      -- @[0,1)@.
      --
      -- * For 'Integer', the range is (arbitrarily) the range of 'Int'.
      --
      -- See 'System.Random.random' for details.
      getRandom :: Random.Random a => m a

      -- | Plural variant of 'getRandomR', producing an infinite list of
      -- random values instead of returning a new generator.
      --
      -- See 'System.Random.randomRs' for details.
      getRandomRs :: Random.Random a => (a, a) -> m [a]

      -- | Plural variant of 'getRandom', producing an infinite list of
      -- random values instead of returning a new generator.
      --
      -- See 'System.Random.randoms' for details.
      getRandoms :: Random.Random a => m [a]

    instance MonadRandom IO where
      getRandomR :: forall a. Random a => (a, a) -> IO a
    getRandomR = (a, a) -> IO a
    forall a (m :: * -> *). (Random a, MonadIO m) => (a, a) -> m a
    Random.randomRIO
      getRandom :: forall a. Random a => IO a
    getRandom = IO a
    forall a (m :: * -> *). (Random a, MonadIO m) => m a
    Random.randomIO
      getRandomRs :: forall a. Random a => (a, a) -> IO [a]
    getRandomRs (a, a)
    lohi = (StdGen -> [a]) -> IO StdGen -> IO [a]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM ((a, a) -> StdGen -> [a]
    forall g. RandomGen g => (a, a) -> g -> [a]
    forall a g. (Random a, RandomGen g) => (a, a) -> g -> [a]
    Random.randomRs (a, a)
    lohi) IO StdGen
    forall (m :: * -> *). MonadIO m => m StdGen
    Random.newStdGen
      getRandoms :: forall a. Random a => IO [a]
    getRandoms = (StdGen -> [a]) -> IO StdGen -> IO [a]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM StdGen -> [a]
    forall g. RandomGen g => g -> [a]
    forall a g. (Random a, RandomGen g) => g -> [a]
    Random.randoms IO StdGen
    forall (m :: * -> *). MonadIO m => m StdGen
    Random.newStdGen

    instance MonadRandom m => MonadRandom (ContT r m) where
      getRandomR :: forall a. Random a => (a, a) -> ContT r m a
    getRandomR = m a -> ContT r m a
    forall (m :: * -> *) a. Monad m => m a -> ContT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> ContT r m a) -> ((a, a) -> m a) -> (a, a) -> ContT r m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => ContT r m a
    getRandom = m a -> ContT r m a
    forall (m :: * -> *) a. Monad m => m a -> ContT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> ContT r m [a]
    getRandomRs = m [a] -> ContT r m [a]
    forall (m :: * -> *) a. Monad m => m a -> ContT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> ContT r m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> ContT r m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => ContT r m [a]
    getRandoms = m [a] -> ContT r m [a]
    forall (m :: * -> *) a. Monad m => m a -> ContT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance MonadRandom m => MonadRandom (ExceptT e m) where
      getRandomR :: forall a. Random a => (a, a) -> ExceptT e m a
    getRandomR = m a -> ExceptT e m a
    forall (m :: * -> *) a. Monad m => m a -> ExceptT e m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> ExceptT e m a)
    -> ((a, a) -> m a) -> (a, a) -> ExceptT e m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => ExceptT e m a
    getRandom = m a -> ExceptT e m a
    forall (m :: * -> *) a. Monad m => m a -> ExceptT e m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> ExceptT e m [a]
    getRandomRs = m [a] -> ExceptT e m [a]
    forall (m :: * -> *) a. Monad m => m a -> ExceptT e m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> ExceptT e m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> ExceptT e m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => ExceptT e m [a]
    getRandoms = m [a] -> ExceptT e m [a]
    forall (m :: * -> *) a. Monad m => m a -> ExceptT e m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance MonadRandom m => MonadRandom (IdentityT m) where
      getRandomR :: forall a. Random a => (a, a) -> IdentityT m a
    getRandomR = m a -> IdentityT m a
    forall (m :: * -> *) a. Monad m => m a -> IdentityT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> IdentityT m a)
    -> ((a, a) -> m a) -> (a, a) -> IdentityT m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => IdentityT m a
    getRandom = m a -> IdentityT m a
    forall (m :: * -> *) a. Monad m => m a -> IdentityT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> IdentityT m [a]
    getRandomRs = m [a] -> IdentityT m [a]
    forall (m :: * -> *) a. Monad m => m a -> IdentityT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> IdentityT m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> IdentityT m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => IdentityT m [a]
    getRandoms = m [a] -> IdentityT m [a]
    forall (m :: * -> *) a. Monad m => m a -> IdentityT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance MonadRandom m => MonadRandom (MaybeT m) where
      getRandomR :: forall a. Random a => (a, a) -> MaybeT m a
    getRandomR = m a -> MaybeT m a
    forall (m :: * -> *) a. Monad m => m a -> MaybeT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> MaybeT m a) -> ((a, a) -> m a) -> (a, a) -> MaybeT m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => MaybeT m a
    getRandom = m a -> MaybeT m a
    forall (m :: * -> *) a. Monad m => m a -> MaybeT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> MaybeT m [a]
    getRandomRs = m [a] -> MaybeT m [a]
    forall (m :: * -> *) a. Monad m => m a -> MaybeT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> MaybeT m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> MaybeT m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => MaybeT m [a]
    getRandoms = m [a] -> MaybeT m [a]
    forall (m :: * -> *) a. Monad m => m a -> MaybeT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance (Monoid w, MonadRandom m) => MonadRandom (LazyRWS.RWST r w s m) where
      getRandomR :: forall a. Random a => (a, a) -> RWST r w s m a
    getRandomR = m a -> RWST r w s m a
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> RWST r w s m a)
    -> ((a, a) -> m a) -> (a, a) -> RWST r w s m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => RWST r w s m a
    getRandom = m a -> RWST r w s m a
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> RWST r w s m [a]
    getRandomRs = m [a] -> RWST r w s m [a]
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> RWST r w s m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> RWST r w s m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => RWST r w s m [a]
    getRandoms = m [a] -> RWST r w s m [a]
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance (Monoid w, MonadRandom m) => MonadRandom (StrictRWS.RWST r w s m) where
      getRandomR :: forall a. Random a => (a, a) -> RWST r w s m a
    getRandomR = m a -> RWST r w s m a
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> RWST r w s m a)
    -> ((a, a) -> m a) -> (a, a) -> RWST r w s m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => RWST r w s m a
    getRandom = m a -> RWST r w s m a
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> RWST r w s m [a]
    getRandomRs = m [a] -> RWST r w s m [a]
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> RWST r w s m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> RWST r w s m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => RWST r w s m [a]
    getRandoms = m [a] -> RWST r w s m [a]
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance MonadRandom m => MonadRandom (ReaderT r m) where
      getRandomR :: forall a. Random a => (a, a) -> ReaderT r m a
    getRandomR = m a -> ReaderT r m a
    forall (m :: * -> *) a. Monad m => m a -> ReaderT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> ReaderT r m a)
    -> ((a, a) -> m a) -> (a, a) -> ReaderT r m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => ReaderT r m a
    getRandom = m a -> ReaderT r m a
    forall (m :: * -> *) a. Monad m => m a -> ReaderT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> ReaderT r m [a]
    getRandomRs = m [a] -> ReaderT r m [a]
    forall (m :: * -> *) a. Monad m => m a -> ReaderT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> ReaderT r m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> ReaderT r m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => ReaderT r m [a]
    getRandoms = m [a] -> ReaderT r m [a]
    forall (m :: * -> *) a. Monad m => m a -> ReaderT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance MonadRandom m => MonadRandom (LazyState.StateT s m) where
      getRandomR :: forall a. Random a => (a, a) -> StateT s m a
    getRandomR = m a -> StateT s m a
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> StateT s m a) -> ((a, a) -> m a) -> (a, a) -> StateT s m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => StateT s m a
    getRandom = m a -> StateT s m a
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> StateT s m [a]
    getRandomRs = m [a] -> StateT s m [a]
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> StateT s m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> StateT s m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => StateT s m [a]
    getRandoms = m [a] -> StateT s m [a]
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance MonadRandom m => MonadRandom (StrictState.StateT s m) where
      getRandomR :: forall a. Random a => (a, a) -> StateT s m a
    getRandomR = m a -> StateT s m a
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> StateT s m a) -> ((a, a) -> m a) -> (a, a) -> StateT s m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => StateT s m a
    getRandom = m a -> StateT s m a
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> StateT s m [a]
    getRandomRs = m [a] -> StateT s m [a]
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> StateT s m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> StateT s m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => StateT s m [a]
    getRandoms = m [a] -> StateT s m [a]
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance (MonadRandom m, Monoid w) => MonadRandom (LazyWriter.WriterT w m) where
      getRandomR :: forall a. Random a => (a, a) -> WriterT w m a
    getRandomR = m a -> WriterT w m a
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> WriterT w m a)
    -> ((a, a) -> m a) -> (a, a) -> WriterT w m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => WriterT w m a
    getRandom = m a -> WriterT w m a
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> WriterT w m [a]
    getRandomRs = m [a] -> WriterT w m [a]
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> WriterT w m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> WriterT w m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => WriterT w m [a]
    getRandoms = m [a] -> WriterT w m [a]
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    instance (MonadRandom m, Monoid w) => MonadRandom (StrictWriter.WriterT w m) where
      getRandomR :: forall a. Random a => (a, a) -> WriterT w m a
    getRandomR = m a -> WriterT w m a
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m a -> WriterT w m a)
    -> ((a, a) -> m a) -> (a, a) -> WriterT w m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m a
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR
      getRandom :: forall a. Random a => WriterT w m a
    getRandom = m a -> WriterT w m a
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m a
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
      getRandomRs :: forall a. Random a => (a, a) -> WriterT w m [a]
    getRandomRs = m [a] -> WriterT w m [a]
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (m [a] -> WriterT w m [a])
    -> ((a, a) -> m [a]) -> (a, a) -> WriterT w m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, a) -> m [a]
    forall a. Random a => (a, a) -> m [a]
    forall (m :: * -> *) a.
    (MonadRandom m, Random a) =>
    (a, a) -> m [a]
    getRandomRs
      getRandoms :: forall a. Random a => WriterT w m [a]
    getRandoms = m [a] -> WriterT w m [a]
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m [a]
    forall a. Random a => m [a]
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m [a]
    getRandoms

    ------------------------------------------------------------
    -- MonadSplit
    ------------------------------------------------------------

    -- | The class 'MonadSplit' proivides a way to specify a random number
    --   generator that can be split into two new generators.
    --
    --   This class is not very useful in practice: typically, one cannot
    --   actually do anything with a generator.  It remains here to avoid
    --   breaking existing code unnecessarily.  For a more practically
    --   useful interface, see 'MonadInterleave'.
    class Monad m => MonadSplit g m | m -> g where
      -- | The 'getSplit' operation allows one to obtain two distinct random number
      -- generators.
      --
      -- See 'System.Random.split' for details.
      getSplit :: m g

    instance MonadSplit Random.StdGen IO where
      getSplit :: IO StdGen
    getSplit = IO StdGen
    forall (m :: * -> *). MonadIO m => m StdGen
    Random.newStdGen

    instance MonadSplit g m => MonadSplit g (ContT r m) where
      getSplit :: ContT r m g
    getSplit = m g -> ContT r m g
    forall (m :: * -> *) a. Monad m => m a -> ContT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance MonadSplit g m => MonadSplit g (ExceptT e m) where
      getSplit :: ExceptT e m g
    getSplit = m g -> ExceptT e m g
    forall (m :: * -> *) a. Monad m => m a -> ExceptT e m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance MonadSplit g m => MonadSplit g (IdentityT m) where
      getSplit :: IdentityT m g
    getSplit = m g -> IdentityT m g
    forall (m :: * -> *) a. Monad m => m a -> IdentityT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance MonadSplit g m => MonadSplit g (MaybeT m) where
      getSplit :: MaybeT m g
    getSplit = m g -> MaybeT m g
    forall (m :: * -> *) a. Monad m => m a -> MaybeT m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance (Monoid w, MonadSplit g m) => MonadSplit g (LazyRWS.RWST r w s m) where
      getSplit :: RWST r w s m g
    getSplit = m g -> RWST r w s m g
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance (Monoid w, MonadSplit g m) => MonadSplit g (StrictRWS.RWST r w s m) where
      getSplit :: RWST r w s m g
    getSplit = m g -> RWST r w s m g
    forall (m :: * -> *) a. Monad m => m a -> RWST r w s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance MonadSplit g m => MonadSplit g (ReaderT r m) where
      getSplit :: ReaderT r m g
    getSplit = m g -> ReaderT r m g
    forall (m :: * -> *) a. Monad m => m a -> ReaderT r m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance MonadSplit g m => MonadSplit g (LazyState.StateT s m) where
      getSplit :: StateT s m g
    getSplit = m g -> StateT s m g
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance MonadSplit g m => MonadSplit g (StrictState.StateT s m) where
      getSplit :: StateT s m g
    getSplit = m g -> StateT s m g
    forall (m :: * -> *) a. Monad m => m a -> StateT s m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance (Monoid w, MonadSplit g m) => MonadSplit g (LazyWriter.WriterT w m) where
      getSplit :: WriterT w m g
    getSplit = m g -> WriterT w m g
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    instance (Monoid w, MonadSplit g m) => MonadSplit g (StrictWriter.WriterT w m) where
      getSplit :: WriterT w m g
    getSplit = m g -> WriterT w m g
    forall (m :: * -> *) a. Monad m => m a -> WriterT w m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift m g
    forall g (m :: * -> *). MonadSplit g m => m g
    getSplit

    ------------------------------------------------------------
    -- MonadInterleave
    ------------------------------------------------------------

    -- | The class 'MonadInterleave' proivides a convenient interface atop
    --   a 'split' operation on a random generator.
    class MonadRandom m => MonadInterleave m where
      -- | If @x :: m a@ is a computation in some random monad, then
      --   @interleave x@ works by splitting the generator, running @x@
      --   using one half, and using the other half as the final generator
      --   state of @interleave x@ (replacing whatever the final generator
      --   state otherwise would have been).  This means that computation
      --   needing random values which comes after @interleave x@ does not
      --   necessarily depend on the computation of @x@.  For example:
      --
      --   > >>> evalRandIO $ snd <$> ((,) <$> undefined <*> getRandom)
      --   > *** Exception: Prelude.undefined
      --   > >>> evalRandIO $ snd <$> ((,) <$> interleave undefined <*> getRandom)
      --   > 6192322188769041625
      --
      --   This can be used, for example, to allow random computations to
      --   run in parallel, or to create lazy infinite structures of
      --   random values.  In the example below, the infinite tree
      --   @randTree@ cannot be evaluated lazily: even though it is cut
      --   off at two levels deep by @hew 2@, the random value in the
      --   right subtree still depends on generation of all the random
      --   values in the (infinite) left subtree, even though they are
      --   ultimately unneeded.  Inserting a call to @interleave@, as in
      --   @randTreeI@, solves the problem: the generator splits at each
      --   @Node@, so random values in the left and right subtrees are
      --   generated independently.
      --
      --   > data Tree = Leaf | Node Int Tree Tree deriving Show
      --   >
      --   > hew :: Int -> Tree -> Tree
      --   > hew 0 _    = Leaf
      --   > hew _ Leaf = Leaf
      --   > hew n (Node x l r) = Node x (hew (n-1) l) (hew (n-1) r)
      --   >
      --   > randTree :: Rand StdGen Tree
      --   > randTree = Node <$> getRandom <*> randTree <*> randTree
      --   >
      --   > randTreeI :: Rand StdGen Tree
      --   > randTreeI = interleave $ Node <$> getRandom <*> randTreeI <*> randTreeI
      --
      --   > >>> hew 2 <$> evalRandIO randTree
      --   > Node 2168685089479838995 (Node (-1040559818952481847) Leaf Leaf) (Node ^CInterrupted.
      --   > >>> hew 2 <$> evalRandIO randTreeI
      --   > Node 8243316398511136358 (Node 4139784028141790719 Leaf Leaf) (Node 4473998613878251948 Leaf Leaf)
      interleave :: m a -> m a

    instance MonadInterleave m => MonadInterleave (ContT r m) where
      interleave :: forall a. ContT r m a -> ContT r m a
    interleave = (m r -> m r) -> ContT r m a -> ContT r m a
    forall {k} (m :: k -> *) (r :: k) a.
    (m r -> m r) -> ContT r m a -> ContT r m a
    mapContT m r -> m r
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance MonadInterleave m => MonadInterleave (ExceptT e m) where
      interleave :: forall a. ExceptT e m a -> ExceptT e m a
    interleave = (m (Either e a) -> m (Either e a))
    -> ExceptT e m a -> ExceptT e m a
    forall (m :: * -> *) e a (n :: * -> *) e' b.
    (m (Either e a) -> n (Either e' b))
    -> ExceptT e m a -> ExceptT e' n b
    mapExceptT m (Either e a) -> m (Either e a)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance MonadInterleave m => MonadInterleave (IdentityT m) where
      interleave :: forall a. IdentityT m a -> IdentityT m a
    interleave = (m a -> m a) -> IdentityT m a -> IdentityT m a
    forall {k1} {k2} (m :: k1 -> *) (a :: k1) (n :: k2 -> *) (b :: k2).
    (m a -> n b) -> IdentityT m a -> IdentityT n b
    mapIdentityT m a -> m a
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance MonadInterleave m => MonadInterleave (MaybeT m) where
      interleave :: forall a. MaybeT m a -> MaybeT m a
    interleave = (m (Maybe a) -> m (Maybe a)) -> MaybeT m a -> MaybeT m a
    forall (m :: * -> *) a (n :: * -> *) b.
    (m (Maybe a) -> n (Maybe b)) -> MaybeT m a -> MaybeT n b
    mapMaybeT m (Maybe a) -> m (Maybe a)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance (Monoid w, MonadInterleave m) => MonadInterleave (LazyRWS.RWST r w s m) where
      interleave :: forall a. RWST r w s m a -> RWST r w s m a
    interleave = (m (a, s, w) -> m (a, s, w)) -> RWST r w s m a -> RWST r w s m a
    forall (m :: * -> *) a s w (n :: * -> *) b w' r.
    (m (a, s, w) -> n (b, s, w')) -> RWST r w s m a -> RWST r w' s n b
    LazyRWS.mapRWST m (a, s, w) -> m (a, s, w)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance (Monoid w, MonadInterleave m) => MonadInterleave (StrictRWS.RWST r w s m) where
      interleave :: forall a. RWST r w s m a -> RWST r w s m a
    interleave = (m (a, s, w) -> m (a, s, w)) -> RWST r w s m a -> RWST r w s m a
    forall (m :: * -> *) a s w (n :: * -> *) b w' r.
    (m (a, s, w) -> n (b, s, w')) -> RWST r w s m a -> RWST r w' s n b
    StrictRWS.mapRWST m (a, s, w) -> m (a, s, w)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance MonadInterleave m => MonadInterleave (ReaderT r m) where
      interleave :: forall a. ReaderT r m a -> ReaderT r m a
    interleave = (m a -> m a) -> ReaderT r m a -> ReaderT r m a
    forall (m :: * -> *) a (n :: * -> *) b r.
    (m a -> n b) -> ReaderT r m a -> ReaderT r n b
    mapReaderT m a -> m a
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance MonadInterleave m => MonadInterleave (LazyState.StateT s m) where
      interleave :: forall a. StateT s m a -> StateT s m a
    interleave = (m (a, s) -> m (a, s)) -> StateT s m a -> StateT s m a
    forall (m :: * -> *) a s (n :: * -> *) b.
    (m (a, s) -> n (b, s)) -> StateT s m a -> StateT s n b
    LazyState.mapStateT m (a, s) -> m (a, s)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance MonadInterleave m => MonadInterleave (StrictState.StateT s m) where
      interleave :: forall a. StateT s m a -> StateT s m a
    interleave = (m (a, s) -> m (a, s)) -> StateT s m a -> StateT s m a
    forall (m :: * -> *) a s (n :: * -> *) b.
    (m (a, s) -> n (b, s)) -> StateT s m a -> StateT s n b
    StrictState.mapStateT m (a, s) -> m (a, s)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance (Monoid w, MonadInterleave m) => MonadInterleave (LazyWriter.WriterT w m) where
      interleave :: forall a. WriterT w m a -> WriterT w m a
    interleave = (m (a, w) -> m (a, w)) -> WriterT w m a -> WriterT w m a
    forall (m :: * -> *) a w (n :: * -> *) b w'.
    (m (a, w) -> n (b, w')) -> WriterT w m a -> WriterT w' n b
    LazyWriter.mapWriterT m (a, w) -> m (a, w)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    instance (Monoid w, MonadInterleave m) => MonadInterleave (StrictWriter.WriterT w m) where
      interleave :: forall a. WriterT w m a -> WriterT w m a
    interleave = (m (a, w) -> m (a, w)) -> WriterT w m a -> WriterT w m a
    forall (m :: * -> *) a w (n :: * -> *) b w'.
    (m (a, w) -> n (b, w')) -> WriterT w m a -> WriterT w' n b
    StrictWriter.mapWriterT m (a, w) -> m (a, w)
    forall a. m a -> m a
    forall (m :: * -> *) a. MonadInterleave m => m a -> m a
    interleave

    ------------------------------------------------------------
    -- Convenience samplers
    ------------------------------------------------------------

    -- | Sample a random value from a weighted nonempty collection of
    --   elements.  Crashes with a call to @error@ if the collection is
    --   empty or the total weight is zero.
    weighted :: (F.Foldable t, MonadRandom m) => t (a, Rational) -> m a
    weighted :: forall (t :: * -> *) (m :: * -> *) a.
    (Foldable t, MonadRandom m) =>
    t (a, Rational) -> m a
    weighted t (a, Rational)
    t = do
      ma <- t (a, Rational) -> m (Maybe a)
    forall (t :: * -> *) (m :: * -> *) a.
    (Foldable t, MonadRandom m) =>
    t (a, Rational) -> m (Maybe a)
    weightedMay t (a, Rational)
    t
      case ma of
        Maybe a
    Nothing -> [Char] -> m a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Control.Monad.Random.Class.weighted: empty collection, or total weight <= 0"
        Just a
    a -> a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    a

    -- | Sample a random value from a weighted collection of elements.
    --   Returns @Nothing@ if the collection is empty or the total weight is
    --   zero.
    weightedMay :: (F.Foldable t, MonadRandom m) => t (a, Rational) -> m (Maybe a)
    weightedMay :: forall (t :: * -> *) (m :: * -> *) a.
    (Foldable t, MonadRandom m) =>
    t (a, Rational) -> m (Maybe a)
    weightedMay = [(a, Rational)] -> m (Maybe a)
    forall (m :: * -> *) a.
    MonadRandom m =>
    [(a, Rational)] -> m (Maybe a)
    fromListMay ([(a, Rational)] -> m (Maybe a))
    -> (t (a, Rational) -> [(a, Rational)])
    -> t (a, Rational)
    -> m (Maybe a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . t (a, Rational) -> [(a, Rational)]
    forall a. t a -> [a]
    forall (t :: * -> *) a. Foldable t => t a -> [a]
    F.toList

    -- | Sample a random value from a weighted list.  The list must be
    --   non-empty and the total weight must be non-zero.
    fromList :: MonadRandom m => [(a, Rational)] -> m a
    fromList :: forall (m :: * -> *) a. MonadRandom m => [(a, Rational)] -> m a
    fromList [(a, Rational)]
    ws = do
      ma <- [(a, Rational)] -> m (Maybe a)
    forall (m :: * -> *) a.
    MonadRandom m =>
    [(a, Rational)] -> m (Maybe a)
    fromListMay [(a, Rational)]
    ws
      case ma of
        Maybe a
    Nothing -> [Char] -> m a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Control.Monad.Random.Class.fromList: empty list, or total weight = 0"
        Just a
    a -> a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    a

    -- | Sample a random value from a weighted list.  Return @Nothing@ if
    --   the list is empty or the total weight is nonpositive.
    fromListMay :: MonadRandom m => [(a, Rational)] -> m (Maybe a)
    fromListMay :: forall (m :: * -> *) a.
    MonadRandom m =>
    [(a, Rational)] -> m (Maybe a)
    fromListMay [(a, Rational)]
    xs = do
      let s :: Rational
    s = [Rational] -> Rational
    forall a. Num a => [a] -> a
    forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
    sum (((a, Rational) -> Rational) -> [(a, Rational)] -> [Rational]
    forall a b. (a -> b) -> [a] -> [b]
    map (a, Rational) -> Rational
    forall a b. (a, b) -> b
    snd [(a, Rational)]
    xs)
          cums :: [(a, Rational)]
    cums = ((a, Rational) -> (a, Rational) -> (a, Rational))
    -> [(a, Rational)] -> [(a, Rational)]
    forall a. (a -> a -> a) -> [a] -> [a]
    scanl1 (\ ~(a
    _, Rational
    q) ~(a
    y, Rational
    s') -> (a
    y, Rational
    s' Rational -> Rational -> Rational
    forall a. Num a => a -> a -> a
    + Rational
    q)) [(a, Rational)]
    xs
      if Rational
    s Rational -> Rational -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Rational
    0
        then Maybe a -> m (Maybe a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
        else do
          -- Pick a Word64 value uniformly
          w <- m Word64
    forall a. Random a => m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => m a
    getRandom
          -- w / maxBound gives a uniform Rational in the range [0,1].
          -- Subtract from 1 to match the way uniform Double values are
          -- generated, and hence match the old behavior of this function.
          let p = Rational
    s Rational -> Rational -> Rational
    forall a. Num a => a -> a -> a
    * (Rational
    1 Rational -> Rational -> Rational
    forall a. Num a => a -> a -> a
    - Word64 -> Rational
    forall a. Real a => a -> Rational
    toRational (Word64
    w :: Word64) Rational -> Rational -> Rational
    forall a. Fractional a => a -> a -> a
    / Word64 -> Rational
    forall a. Real a => a -> Rational
    toRational (Word64
    forall a. Bounded a => a
    maxBound :: Word64))
          return . fmap fst . F.find ((>= p) . snd) $ cums

    -- | Sample a value uniformly from a nonempty collection of elements.
    uniform :: (F.Foldable t, MonadRandom m) => t a -> m a
    uniform :: forall (t :: * -> *) (m :: * -> *) a.
    (Foldable t, MonadRandom m) =>
    t a -> m a
    uniform t a
    t = do
      ma <- t a -> m (Maybe a)
    forall (t :: * -> *) (m :: * -> *) a.
    (Foldable t, MonadRandom m) =>
    t a -> m (Maybe a)
    uniformMay t a
    t
      case ma of
        Maybe a
    Nothing -> [Char] -> m a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Control.Monad.Random.Class.uniform: empty collection"
        Just a
    a -> a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    a

    -- | Sample a value uniformly from a collection of elements.  Return
    --   @Nothing@ if the collection is empty.
    uniformMay :: (F.Foldable t, MonadRandom m) => t a -> m (Maybe a)
    uniformMay :: forall (t :: * -> *) (m :: * -> *) a.
    (Foldable t, MonadRandom m) =>
    t a -> m (Maybe a)
    uniformMay = [(a, Rational)] -> m (Maybe a)
    forall (m :: * -> *) a.
    MonadRandom m =>
    [(a, Rational)] -> m (Maybe a)
    fromListMay ([(a, Rational)] -> m (Maybe a))
    -> (t a -> [(a, Rational)]) -> t a -> m (Maybe a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> (a, Rational)) -> [a] -> [(a, Rational)]
    forall a b. (a -> b) -> [a] -> [b]
    map ((a -> Rational -> (a, Rational)) -> Rational -> a -> (a, Rational)
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (,) Rational
    1) ([a] -> [(a, Rational)]) -> (t a -> [a]) -> t a -> [(a, Rational)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . t a -> [a]
    forall a. t a -> [a]
    forall (t :: * -> *) a. Foldable t => t a -> [a]
    F.toList

    ------------------------------------------------------------

    -- The old implementation of `fromListMay`, for comparison.  See
    -- https://github.com/byorgey/MonadRandom/issues/53 and
    -- https://byorgey.github.io/blog/posts/2024/10/14/MonadRandom-version-bump.html
    _fromListMayOld :: MonadRandom m => [(a, Rational)] -> m (Maybe a)
    _fromListMayOld :: forall (m :: * -> *) a.
    MonadRandom m =>
    [(a, Rational)] -> m (Maybe a)
    _fromListMayOld [(a, Rational)]
    xs = do
      let s :: Double
    s = Rational -> Double
    forall a. Fractional a => Rational -> a
    fromRational ([Rational] -> Rational
    forall a. Num a => [a] -> a
    forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
    sum (((a, Rational) -> Rational) -> [(a, Rational)] -> [Rational]
    forall a b. (a -> b) -> [a] -> [b]
    map (a, Rational) -> Rational
    forall a b. (a, b) -> b
    snd [(a, Rational)]
    xs)) :: Double
          cums :: [(a, Rational)]
    cums = ((a, Rational) -> (a, Rational) -> (a, Rational))
    -> [(a, Rational)] -> [(a, Rational)]
    forall a. (a -> a -> a) -> [a] -> [a]
    scanl1 (\ ~(a
    _, Rational
    q) ~(a
    y, Rational
    s') -> (a
    y, Rational
    s' Rational -> Rational -> Rational
    forall a. Num a => a -> a -> a
    + Rational
    q)) [(a, Rational)]
    xs
      if Double
    s Double -> Double -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Double
    0
        then Maybe a -> m (Maybe a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
        else do
          p <- (Double -> Rational) -> m Double -> m Rational
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM Double -> Rational
    forall a. Real a => a -> Rational
    toRational (m Double -> m Rational) -> m Double -> m Rational
    forall a b. (a -> b) -> a -> b
    $ (Double, Double) -> m Double
    forall a. Random a => (a, a) -> m a
    forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
    getRandomR (Double
    0, Double
    s)
          return . fmap fst . F.find ((>= p) . snd) $ cums