On Fri, Feb 5, 2010 at 5:19 AM, Martijn van Steenbergen
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