@Shimuuar I understand the fix, but I am still having trouble with the problem you are describing. Can you comment here a simple example that compiles and produces some result with your fix, while being impossible without it?

There is a good chance that I don't understand your concern correctly, but if I do, then my opinion is that there is no problem there because we don't have a generic way to construct the frozen state, therefore it is irrelevant that it depends on the state token.

In particular in your example frozen <- readGeneratorState there is no way to achieve it in general (for an arbitrary generator) regardless if Frozen is data or type family.

Here is a way anyone can use it with MWC.

λ> import System.Random.MWC
λ> import qualified System.Random as R
λ> import Control.Monad.ST
λ> g0 <- createSystemRandom
λ> s <- save g0
λ> runST $ R.thawGen (Frozen s) >>= \ g -> R.uniformWord8 g >>= \a -> R.freezeGen g >>= \(Frozen s') -> pure (s', a)

When compared to this PR there would be no wrapper/unwrapper for Frozen, but it would be necessary to specify the type of g, which, when combine with ST is a major pain (gotta pull out ScopedTypeVariables, extra bindings with signatures etc.)

because we don't have a generic way to construct the frozen state

Binary (Frozen g) and likes of it could get programmer surprisingly far :)

Here is simplest example that doesn't work. Just trying to pass frozen state to function causes. Idea is to load pure PRNG state from somewhere and then run some otherwise pure computation:

broken :: Frozen (MutGen s StdGen) -> [Word64]
broken frozen = runST $ do
  g <- thawGen frozen
  replicateM 4 $ uniformWord64 g

It fails with

 System/Random.hs:1255:8: error:
    • Couldn't match type ‘s1’ with ‘s’ arising from a use of ‘thawGen’
      ‘s1’ is a rigid type variable bound by
        a type expected by the context:
          forall s1. ST s1 [Word64]
        at System/Random.hs:(1254,22)-(1256,32)
      ‘s’ is a rigid type variable bound by
        the type signature for:
          go1 :: forall s. Frozen (MutGen s StdGen) -> [Word64]
        at System/Random.hs:1253:1-43

There's rather ugly workaround. Wrap that thing in a box. And one will have to carry such box around.

newtype Box = Box (forall s. Frozen (MutGen s StdGen))

boxed :: Box -> [Word64]
boxed (Box frozen) = runST $ do
  g <- thawGen frozen
  replicateM 4 $ uniformWord64 g

Variant with type family works. But it require type annotations

works :: StdGen -> [Word64]
works frozen = do
  runST $ do
    g :: MutGen s StdGen <- thawGen frozen
    replicateM 4 $ uniformWord64 g

Alternatives

But as soon as we drop that that annoying type variable everything becomes conveniently injective and won't require any annotations. Maybe we got things backwards. Instead of trying to derive frozen state from mutable state which require discarding state tyvar we should derive mutable generator from its frozen state. After all mutable generator could be reduced to pure one by fthawing and then freezing generator. Efficiency will be horrible of course.

This approach suffers from same problem as dispatching on type constructor. Where should we get type variable for state token? But this approach could work out.

That's the point that doesn't make sense to me. Why would you ever need that?

broken :: Frozen (MutGen s StdGen) -> [Word64]

This works without any type annotations:

notBroken :: StdGen -> [Word64]
notBroken seed = runST $ do
  g <- thawGen (MutGen seed)
  replicateM 4 $ uniformWord64 g

Binary (Frozen b) is nonsense, you need to know the actual generator in order to create an instance like that. If you want to create Binary (Frozen (MutGen s StdGen)) you can do so and s is not preventing from doing that.

I am yet to see a compelling reason for this PR.

Hell, even this would work just fine, if you really wanted the original type signature Frozen (MutGen s StdGen) -> [Word64]

notBroken2 :: Frozen (MutGen s StdGen) -> [Word64]
notBroken2 (MutGen seed) = runST $ do
  g <- thawGen (MutGen seed)
  replicateM 4 $ uniformWord64 g

So, my question is, is there a really impossible case that requires type family vs data family? Cause if not then all this fix is gonna do is confuse the compiler and many novice users, because without specifying the type thawGen will never work:

g :: MutGen s StdGen <- thawGen frozen

Newtype wrapper break down the moment you want to be polymorphic in generator type. But you managed to convince me that both variants are bad.

What we really want from Frozen is to be able to write: something along the lines: (g s -> ST s a) -> (Frozen g -> (Frozen g, a)

something along the lines: (g s -> ST s a) -> (Frozen g -> (Frozen g, a)

I think you are trying to say what we want is something like that, right?

runGenST :: Frozen g -> (forall s . g s -> ST s a) -> (a, Frozen g)

Frozen is irrelevant here and something else prevents us form doing that, namely the MonadRandom. With broken type signature the problem is apparent, s is trying to escape

runGenST :: MonadRandom (g s) (ST s) => Frozen g -> (forall s . g s -> ST s a) -> (a, Frozen g)

So, MonadRandom needs the Gen s, which relates s in Gen and in PrimState m. I can't really see a solution there, I've played around with it, but I don't think there is even a possibility of some work around there, even by making MonadRandom (g :: * -> *) s m, as you mention here: #56 (comment)

@Shimuuar I think I might have a pretty nasty, but really cool solution to this. I am gonna mess with it a bit and will ping you when I have something working :)

@Shimuuar Nevermind, spoke too soon :) I don't think it is possible to solve this with ST in general.

Just in case you are curious, here is what I had in mind. By the way, this approach does get rid of s in Frozen and reduces the number of type variables in the class, but complicates instance creation a bit and overall is not even a little bit simpler to what we have now:

class RandomGenM (g :: (* -> *) -> *) where
  type GenMonad g :: (* -> *) -> Constraint
  data Frozen g :: *
  {-# MINIMAL freezeGen,thawGen,(uniformWord32R|uniformWord32),(uniformWord64R|uniformWord64) #-}

  thawGen :: (GenMonad g m, Monad m) => Frozen g -> m (g m)
  freezeGen :: (GenMonad g m, Monad m) => g m -> m (Frozen g)
  uniformWord32R :: (GenMonad g m, Monad m) => Word32 -> g m -> m Word32
  uniformWord64R :: (GenMonad g m, Monad m) => Word64 -> g m -> m Word64
  uniformWord8 :: (GenMonad g m, Monad m) => g m -> m Word8
  uniformWord8 = fmap fromIntegral . uniformWord32R (fromIntegral (maxBound :: Word8))
  uniformWord16 :: (GenMonad g m, Monad m) => g m -> m Word16
  uniformWord16 = fmap fromIntegral . uniformWord32R (fromIntegral (maxBound :: Word16))
  uniformWord32 :: (GenMonad g m, Monad m) => g m -> m Word32
  uniformWord32 = uniformWord32R maxBound
  uniformWord64 :: (GenMonad g m, Monad m) => g m -> m Word64
  uniformWord64 = uniformWord64R maxBound
  uniformByteArray :: (GenMonad g m, Monad m) => Int -> g m -> m ByteArray
  default uniformByteArray :: (GenMonad g m, PrimMonad m) => Int -> g m -> m ByteArray
  uniformByteArray = uniformByteArrayPrim

withGenM :: (Monad m, RandomGenM g, GenMonad g m) => Frozen g -> (g m -> m a) -> m (a, Frozen g)
withGenM fg action = do
  g <- thawGen fg
  res <- action g
  fg' <- freezeGen g
  pure (res, fg')

PureGen becomes funky looking:

data PureGen g (m :: * -> *) = PureGenI

instance (RandomGen g) => RandomGenM (PureGen g) where
  type GenMonad (PureGen g) = MonadState g
  newtype Frozen (PureGen g) = PureGen g
  thawGen (PureGen g) = PureGenI <$ put g
  freezeGen _ = fmap PureGen get
  uniformWord32R r _ = state (genWord32R r)
  uniformWord64R r _ = state (genWord64R r)
  uniformWord8 _ = state genWord8
  uniformWord16 _ = state genWord16
  uniformWord32 _ = state genWord32
  uniformWord64 _ = state genWord64
  uniformByteArray n _ = state (genByteArray n)

MutGen now depends on m rather than s

newtype MutGen g m = MutGenI (MutVar (PrimState m) g)

instance RandomGen g => RandomGenM (MutGen g) where
  type GenMonad (MutGen g) = PrimMonad
  newtype Frozen (MutGen g) = MutGen g
  thawGen (MutGen g) = fmap MutGenI (newMutVar g)
  freezeGen (MutGenI gVar) = fmap MutGen (readMutVar gVar)
  uniformWord32R r = atomicMutGen (genWord32R r)
  uniformWord64R r = atomicMutGen (genWord64R r)
  uniformWord8 = atomicMutGen genWord8
  uniformWord16 = atomicMutGen genWord16
  uniformWord32 = atomicMutGen genWord32
  uniformWord64 = atomicMutGen genWord64
  uniformByteArray n = atomicMutGen (genByteArray n)

atomicMutGen :: PrimMonad m => (g -> (a, g)) -> MutGen g m -> m a
atomicMutGen op (MutGenI gVar) =
  atomicModifyMutVar' gVar $ \g ->
    case op g of
      (a, g') -> (g', a)

@Shimuuar I am closing this PR due to your comment:

But you managed to convince me that both variants are bad.

If I misunderstood you and if you still think type vs data is still a good idea, please reopen it and we can pickup this discussions again.

Nevermind, spoke too soon :) I don't think it is possible to solve this with ST in general.

I know that feeling. I have small graveyard of ideas that didn't quite work.

But I finally got a design with which I fought last few week. Here is rough draft: https://gist.github.com/Shimuuar/353a5b3367cf410677843028ba9fb57a

Its main selling point is ability to use mutability and hide this fact so it becomes possible to write things like: genBytestring :: PRNG g => Int -> PRNG g Word8 -> PRNG g ByteString which use in place mutation but doesn't expose this fact in signature (internalMutability example in the draft)

It is certainly a fun experiment, but it is way more complex than what we have right now. It also has real problems, in particular:

• You can't interact with the real world, because PRNG will not work with IO. That's just not acceptable.
• Unnecessary complexity:
  • There is a definition of 4 monads ( RandST, RandPure, Rand and MRand)
  • A custom Monad1, just to deal with s?

@Shimuuar Let me ask you, what does this approach solve, that we cannot do right now? Also if it makes something easier, or clearer (which pretty subjective, but arguable) it would be nice to have a side by side example to what we have already implemented.

I don't think hiding mutability should be the desired goal of a random library that is what ST is for. As long as we can operate in PrimMonad we should be fine. For example there is already:

genByteString :: RandomGen g => Int -> g -> (ByteString, g)
genByteString n g = runPureGenST g (uniformByteStringPrim n)

which produces a ByteString while hiding the mutation.

If passing around generator is a problem I think #70 is a much better solution. This #70 (comment) also shows usage of internalMutability

You can't interact with the real world, because PRNG will not work with IO. That's just not acceptable.

True. But it's not a complete proposal. What I have in mind is something in same spirit as #70 which lifts to Rand to MonadRandom.

Unnecessary complexity:

Necessary. RandPure & RandST are mostly internal data types which are mostly of interest for PRNG implementors. And Monad1 is seemingly only way to encode ∀s. Monad (m s)

Let me ask you, what does this approach solve, that we cannot do right now?

1. Single approach for working with any PRNG. Libraries that builds on of random need abstraction for PRNG to do things like generate normally distributed numbers, shuffle array, etc given generator. Right now we have two type classes: MonadRandom and RandomGen which are similar but not quite the same.

2. Ability to hide local mutation. I still think that it's important since realistically we're speaking about things like: genBS :: (MonadRandom g m, PrimMonad m) => Int -> (g -> m Word8) -> g -> m ByteString and then it suddenly becomes impossible to remove PrimMonad constraint. In fact m in negative position could lead to problems for lifting Rand as well. I need to think about it.

3. Ability to run computation using any generator whether it uses mutability underneath or no Rand g a -> g -> (g,a)

In any case this is proof of concept. I think it will fit well into random but it's not yet tested