On Tue, Feb 2, 2010 at 1:48 PM, Ryan Ingram wrote:
> Gen slightly breaks the monad laws:
>
>> arbitrary >>= return
> is not the same as
>> return () >>= const arbitrary
> because each bind splits the generator, so you end up with a different
> seed passed to arbitrary in these two cases.

Ah yes, that was exactly the problem.

> If the observable value is "some random object" this is a safe fudge,
> but if you want repeatable, it doesn't quite work. You need your
> instances to be exactly identical, down to the associativity of binds,
> in order to get the same results.

We could avoid that problem by redefining Gen as a state transformer monad.

newtype Gen a = MkGen { unGen :: StdGen -> Int -> (a, StdGen) }

instance Monad Gen where
return a = MkGen $ \r _ -> (a,r)
MkGen m >>= k = MkGen $ \r n -> let (a,r') = m r n in unGen (k a) r' n

I'm pretty sure all the Gen primitives can be similarly redefined.