search

nick8325 / quickcheck

Automatic testing of Haskell programs.
Other
713 stars 119 forks source link

Law-abiding Monad using Free like representation of Gen #288

Closed safareli closed 4 years ago

safareli commented 4 years ago

Was there an attempt of implementing Gen using some Free like datatype which is "mart" and avoids split of the seed when encountering the case like return x >>= f?

Lysxia commented 4 years ago

That seems similar to using a state monad for randomness, State RandomSeed. It's a perfectly reasonable approach 99.99% of the time. The advantage of the current Gen is that it is a little more lazy. Consider generating a pair:

(,) <$> genA <*> genB :: Gen (A, B)

Now suppose only B gets used. With a State-based generator, you have to run genA to be able to run genB. With a splitting-based generator like Gen, genB can be run independently. This kind of laziness fundamentally requires splitting "overeagerly". It is not a problem in practice because (1) the laws hold when a Gen is viewed as a probability distribution, and (2) it's uncommon to bind generators that do nothing to the point that the redundant splitting becomes a problem for performance.

safareli commented 4 years ago

thanks