[Haskell-cafe] Re: Generating repeatable arbitrary values with QuickCheck 2

[David Menendez]

On Fri, Feb 5, 2010 at 3:39 PM, Ryan Ingram <ryani.spam at gmail.com> wrote:
> On Fri, Feb 5, 2010 at 5:19 AM, Martijn van Steenbergen
> <martijn at van.steenbergen.nl> wrote:
>> Ryan Ingram wrote:
>>>
>>> Unfortunately, this makes things like
>>>>
>>>>  infinite_xs <- sequence (repeat arbitrary)
>>>
>>> no longer work, since the state never comes out the other side.
>>
>> You're asking to execute an infinite number of monadic actions. How can this
>> ever terminate at all?
>
> Stefan already gave an example, but to explain slightly further --
>
> There's nothing "magical" about monadic actions.  It's just another
> function call.
>
> In the case of QuickCheck, Gen is a reader monad with a "broken" >>=
> that changes the state of the generator passed to each side:

Incidentally, the alternative Gen I suggested also works for infinite
lists. (It's equivalent to StateT StdGen (Reader Int), using the
StateT from Control.Monad.State.Lazy.)

The problem, as Ryan pointed out, is that you can't access the state
after the infinite computation, so you can't create two infinite
streams or an infinite tree, which the current definition of Gen
allows.

More concretely, this works fine:

stream = do
    x <- arbitrary
    xs <- stream
    return (x:xs)

but you can't call arbitrary after you call stream

broken = do
    xs <- stream
    y <- arbitrary  -- can't evaluate until stream is fully evaluated
(i.e., never)

The present definition of Gen avoids this by splitting the StdGen at
every >>=, but that creates the situation where two expressions which
should be equivalent produce different results in some contexts.

It isn't clear to me which implementation is best. I lean towards the
StateT-like implementation, on the theory that it's limitations are
easier to explain, but I guess it comes down to whether we want to
make life easier for (a) people creating infinite structures or (b)
people who need reproducible results.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>