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

[Ryan Ingram]

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:

> newtype Gen a = Gen (Int -> StdGen -> a)
> generate n g (Gen f) = f n g
>
> return x = Gen (\_ _ -> x)
> m >>= f = Gen mbindf where
>    mbindf n g = b where
>        (g1,g2) = split g
>        a = generate n g1 m
>        b = generate n g2 (f a)

Now, to see how this generates data for an infinite list, just consider
>  sequence [arbitrary, ...
which we can represent as
>  sequence (arbitrary:undefined)

Recall the definition of sequence:

> sequence [] = return []
> sequence (a:as) = do
>    x <- a
>    xs <- sequence as
>    return (x:xs)

If we are ever required to evaluate the rest of the list, we'll get
undefined and computation will fail.  The goal is to get something out
of the computation without needing to do so; if that works, then it
will work for (arbitrary:arbitrary:undefined) and so on up to an
infinite list of actions.  Let's try it!

generate 42 g $ sequence (aribtrary : undefined)

= generate 42 sg $ do
    x <- arbitrary
    xs <- sequence undefined
    return (x:xs)

= generate 42 sg (
     arbitrary >>= \x -> sequence undefined >>= \xs -> return (x:xs)
   )

= let
    m = arbitrary
    f = \x -> sequence undefined >>= \xs -> return (x:xs)
    mbindf n g = b where
        (g1,g2) = split g
        a = generate n g m
        b = generate n g (f a)
  in
     generate 42 sg (Gen mbindf)

= let ... in mbindf 42 sg

= let
    m = arbitrary
    f = \x -> sequence undefined >>= \xs -> return (x:xs)
    n = 42
    g = sg
    (g1,g2) = split g
    a = generate n g1 m
    b = generate n g2 (f a)
  in b

= let ... in generate n g2 (f a)
= let ... in generate n g2 (sequence undefined >>= \xs -> return (a:xs)

= let
    m = arbitrary
    n = 42
    g = sg
    (g1,g2) = split g
    a = generate n g1 m

    m1 = sequence undefined
    f = \xs -> return (a:xs)
    mbindf n1 g3 = b where
        (g4,g5) = split g3
        a1 = generate n1 g4 m1
        b = generate n1 g5 (f a1)
  in generate n g2 (Gen mbindf)
= let ... in mbindf n g2

= let
    m = arbitrary
    n = 42
    g = sg
    (g1,g2) = split g
    a = generate n g1 m

    m1 = sequence undefined
    f = \xs -> return (a:xs)
    (g4,g5) = split g2
    a1 = generate n g4 m1
    b = generate n g5 (f a1)
  in generate n g5 (f a1)

= let ... in generate n g5 (return (a:a1))
= let ... in generate n g5 (Gen (\_ _ -> (a:a1)))
= let ... in (\_ _ -> (a:a1)) n g5
= let ... in (a:a1)
= let ... in (generate n g1 m : a1)
= let ... in (generate n g1 arbitrary : a1)
= let ... in (<arbitrary> : a1)

We have now output a cons cell with an arbitrary value without even
evaluating the rest of the input to sequence (which is undefined;
could have been 'repeat aribtrary' or anything else)

Lazy evaluation is pretty neat :)

  -- ryan