Improving Random
Carter Schonwald
carter.schonwald at gmail.com
Wed May 27 02:13:11 UTC 2020
Zemyla!
Yeah, absolutely agree that their pr has the wrong shape for monad random,
which is why I’m confused by dominics pronouncement :), though its a great
contrib.
It should be (ignoring m being applicative vs monad)
(For context, their design is roughly ... MonadRandom m s g | m,g -> s ?
I’m typing on a phone so i might be restating it wrong ... :) )
The *better* choice is
Class PRNG g => MonadRandom m g | m-> g where ...
And then their example instance should be something like
Newtype MWCT m a = ... newtype wrapper around StateT m a threading an MWC
indexed by the state token of the underlying PrimMonad
(Or newtype MWCT s m a = .... stateT thing)
Instance (PrimMonad m) => MonadRandom (MWCT m) (MCWGen (PrimState m))
where ...
Or something along those lines. It absolutely shouldn’t be in the style of
being on any PrimMonad, but part of a stack that provides that instance.
This is ignoring the freeze/thaw stuff which really is just “record and
restore RNG state”, and i think is an artifact of ther design choice in
their PR. Which has a lot of great stuff I’m reviewing and poking at.
Nothing is set in stone about deprecation and migration story, cause
improving everything and making sure everyone has a zero pain/ or at least
tolerable upgrade path is step zero. (And making sure good stable
interfaces persists is key! )
I hope everyone is having a safe and healthy start to their summers,
and I’m sorry for any confusions Dominics email about his collab Pr
announcement has created. But cest lie vie! Though sharing excitement
about a great Pr is great!
Stay well!
-Carter
On Tue, May 26, 2020 at 6:48 PM Zemyla <zemyla at gmail.com> wrote:
> And can you explain how to take an existing RNG and write it in this new
> format?
>
> On Tue, May 26, 2020, 15:54 David Feuer <david.feuer at gmail.com> wrote:
>
>> Could you explain the reasoning behind the deprecations?
>>
>> On Tue, May 26, 2020, 6:00 AM <dominic at steinitz.org> wrote:
>>
>>> Hello Libraries,
>>>
>>> You may recall that following the blog post
>>> <https://alexey.kuleshevi.ch/blog/2019/12/21/random-benchmarks/> by
>>> @lehins, a group of us (@curiousleo, @lehins and me) invited participation
>>> in February
>>> <https://mail.haskell.org/pipermail/libraries/2020-February/030261.html>
>>> to take this work and apply it to improving the current random library.
>>>
>>> Our proximate goals were to fix #25
>>> <https://github.com/haskell/random/issues/25> (filed in 2015) and #51
>>> <https://github.com/haskell/random/issues/51> (filed in 2018). After a
>>> lot of discussion and experimentation, we have a proposal that addresses
>>> both these issues and also: #26
>>> <https://github.com/haskell/random/issues/26>, #44
>>> <https://github.com/haskell/random/issues/44>, #53
>>> <https://github.com/haskell/random/issues/53>, #55
>>> <https://github.com/haskell/random/issues/55>, #58
>>> <https://github.com/haskell/random/issues/58> and #59
>>> <https://github.com/haskell/random/issues/59>.
>>>
>>> For backwards compatibility, the proposal retains the old style classes
>>> and enhances them. Thus in 1.1 we have
>>>
>>> class RandomGen g where
>>> next :: g -> (Int, g)
>>> genRange :: g -> (Int, Int)
>>> split :: g -> (g, g)
>>> {-# MINIMAL next, split #-}
>>>
>>> and in 1.2 we have
>>>
>>> class RandomGen g where
>>> next :: g -> (Int, g)
>>> genWord8 :: g -> (Word8, g)
>>> genWord16 :: g -> (Word16, g)
>>> genWord32 :: g -> (Word32, g)
>>> genWord64 :: g -> (Word64, g)
>>> genWord32R :: Word32 -> g -> (Word32, g)
>>> genWord64R :: Word64 -> g -> (Word64, g)
>>> genShortByteString :: Int
>>> -> g -> (Data.ByteString.Short.Internal.ShortByteString, g)
>>> genRange :: g -> (Int, Int)
>>> split :: g -> (g, g)
>>> {-# MINIMAL split, (genWord32 | genWord64 | next, genRange) #-}
>>>
>>> and next and genRange are deprecated. This interface is what allows the
>>> significantly faster performance as no longer is everything forced to go
>>> via Integer.
>>>
>>> Several new interfaces are introduced and it is recommended that new
>>> applications use these and, where feasible, existing applications migrate
>>> to using them.
>>>
>>> The major API addition in this PR is the definition of a new class
>>> MonadRandom:
>>>
>>> -- | 'MonadRandom' is an interface to monadic pseudo-random number generators.
>>> class Monad m => MonadRandom g s m | g m -> s where
>>> {-# MINIMAL freezeGen,thawGen,(uniformWord32|uniformWord64) #-}
>>>
>>> type Frozen g = (f :: Type) | f -> g
>>> freezeGen :: g s -> m (Frozen g)
>>> thawGen :: Frozen g -> m (g s)
>>>
>>> uniformWord32 :: g s -> m Word32 -- default implementation in terms of uniformWord64
>>> uniformWord64 :: g s -> m Word64 -- default implementation in terms of uniformWord32
>>> -- plus methods for other word sizes and for byte strings
>>> -- all have default implementations so the MINIMAL pragma holds
>>>
>>> Conceptually, in MonadRandom g s m, g s is the type of the generator, s
>>> is the state type, and m the underlying monad. Via the functional
>>> dependency g m -> s, the state type is determined by the generator and
>>> monad.
>>>
>>> Frozen is the type of the generator's state "at rest". It is defined as
>>> an injective type family via f -> g, so there is no ambiguity as to
>>> which g any Frozen g belongs to.
>>>
>>> This definition is generic enough to accommodate, for example, the Gen
>>> type from mwc-random, which itself abstracts over the underlying
>>> primitive monad and state token. This is the full instance declaration
>>> (provided here as an example - this instance is not part of random as
>>> random does not depend on mwc-random):
>>>
>>> instance (s ~ PrimState m, PrimMonad m) => MonadRandom MWC.Gen s m where
>>> type Frozen MWC.Gen = MWC.Seed
>>> freezeGen = MWC.save
>>> thawGen = MWC.restore
>>>
>>> uniformWord8 = MWC.uniform
>>> uniformWord16 = MWC.uniform
>>> uniformWord32 = MWC.uniform
>>> uniformWord64 = MWC.uniform
>>> uniformShortByteString n g = unsafeSTToPrim (genShortByteStringST n (MWC.uniform g))
>>>
>>> Pure random number generators can also be made instances of this class
>>> providing a uniform interface to both pure and stateful random number
>>> generators. An instance for the standard number generator StdGen is
>>> provided.
>>>
>>> The Random typeclass has conceptually been split into Uniform and
>>> UniformRange. The Random typeclass is still included for backwards
>>> compatibility. Uniform is for types where it is possible to sample from
>>> the type's entire domain; UniformRange is for types where one can
>>> sample from a specified range:
>>>
>>> class Uniform a where
>>> uniformM :: MonadRandom g s m => g s -> m a
>>>
>>> class UniformRange a where
>>> uniformRM :: MonadRandom g s m => (a, a) -> g s -> m a
>>>
>>> The proposal is a breaking change but the changes are not very intrusive
>>> and we have PRs ready for the affected downstream libraries:
>>>
>>> - requires base >= 4.10 (GHC-8.2)
>>> - StdGen is no longer an instance of Read
>>> - randomIO and randomRIO were extracted from the Random class into
>>> separate functions
>>>
>>> In addition, there may be import clashes with new functions, e.g.
>>> uniform and uniformR.
>>>
>>> Further explanatory details may be found here
>>> <https://github.com/idontgetoutmuch/random/blob/v1.2-release-notes/RELEASE-NOTES-v1.2.md#api-changes>
>>> and the PR for the proposed new version is here
>>> <https://github.com/haskell/random/pull/61>.
>>>
>>> Here are some benchmarks run on a 3.1 GHz Intel Core i7. The full
>>> benchmarks can be run using e.g. stack bench. The benchmarks are
>>> measured in milliseconds per 100,000 generations. In some cases, the
>>> performance is over x1000(!) times better; the minimum performance increase
>>> for the types listed below is more than x35.
>>>
>>> | Name | Mean (1.1) | Mean (1.2) | Improvement|
>>> | ----------------------- | ---------- | ---------- | ---------- |
>>> | pure/random/Float | 30 | 0.03 | 1038|
>>> | pure/random/Double | 52 | 0.03 | 1672|
>>> | pure/random/Integer | 43 | 0.33 | 131|
>>> | pure/uniform/Word8 | 14 | 0.03 | 422|
>>> | pure/uniform/Word16 | 13 | 0.03 | 375|
>>> | pure/uniform/Word32 | 21 | 0.03 | 594|
>>> | pure/uniform/Word64 | 42 | 0.03 | 1283|
>>> | pure/uniform/Word | 44 | 0.03 | 1491|
>>> | pure/uniform/Int8 | 15 | 0.03 | 511|
>>> | pure/uniform/Int16 | 15 | 0.03 | 507|
>>> | pure/uniform/Int32 | 22 | 0.03 | 749|
>>> | pure/uniform/Int64 | 44 | 0.03 | 1405|
>>> | pure/uniform/Int | 43 | 0.03 | 1512|
>>> | pure/uniform/Char | 17 | 0.49 | 35|
>>> | pure/uniform/Bool | 18 | 0.03 | 618|
>>> | pure/uniform/CChar | 14 | 0.03 | 485|
>>> | pure/uniform/CSChar | 14 | 0.03 | 455|
>>> | pure/uniform/CUChar | 13 | 0.03 | 448|
>>> | pure/uniform/CShort | 14 | 0.03 | 473|
>>> | pure/uniform/CUShort | 13 | 0.03 | 457|
>>> | pure/uniform/CInt | 21 | 0.03 | 737|
>>> | pure/uniform/CUInt | 21 | 0.03 | 742|
>>> | pure/uniform/CLong | 43 | 0.03 | 1544|
>>> | pure/uniform/CULong | 42 | 0.03 | 1460|
>>> | pure/uniform/CPtrdiff | 43 | 0.03 | 1494|
>>> | pure/uniform/CSize | 43 | 0.03 | 1475|
>>> | pure/uniform/CWchar | 22 | 0.03 | 785|
>>> | pure/uniform/CSigAtomic | 21 | 0.03 | 749|
>>> | pure/uniform/CLLong | 43 | 0.03 | 1554|
>>> | pure/uniform/CULLong | 42 | 0.03 | 1505|
>>> | pure/uniform/CIntPtr | 43 | 0.03 | 1476|
>>> | pure/uniform/CUIntPtr | 42 | 0.03 | 1463|
>>> | pure/uniform/CIntMax | 43 | 0.03 | 1535|
>>> | pure/uniform/CUIntMax | 42 | 0.03 | 1493|
>>>
>>>
>>>
>>> Dominic Steinitz
>>> dominic at steinitz.org
>>> http://idontgetoutmuch.org
>>> Twitter: @idontgetoutmuch
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20200526/86a09ca5/attachment-0001.html>
More information about the Libraries
mailing list