If
x :: m a is a computation in some random monad, then
interleave x works by splitting the generator, running
x using one half, and using the other half as the final
generator state of
interleave x (replacing whatever the final
generator state otherwise would have been). This means that
computation needing random values which comes after
interleave
x does not necessarily depend on the computation of
x.
For example:
>>> evalRandIO $ snd <$> ((,) <$> undefined <*> getRandom)
*** Exception: Prelude.undefined
>>> evalRandIO $ snd <$> ((,) <$> interleave undefined <*> getRandom)
6192322188769041625
This can be used, for example, to allow random computations to run in
parallel, or to create lazy infinite structures of random values. In
the example below, the infinite tree
randTree cannot be
evaluated lazily: even though it is cut off at two levels deep by
hew 2, the random value in the right subtree still depends on
generation of all the random values in the (infinite) left subtree,
even though they are ultimately unneeded. Inserting a call to
interleave, as in
randTreeI, solves the problem: the
generator splits at each
Node, so random values in the left
and right subtrees are generated independently.
data Tree = Leaf | Node Int Tree Tree deriving Show
hew :: Int -> Tree -> Tree
hew 0 _ = Leaf
hew _ Leaf = Leaf
hew n (Node x l r) = Node x (hew (n-1) l) (hew (n-1) r)
randTree :: Rand StdGen Tree
randTree = Node <$> getRandom <*> randTree <*> randTree
randTreeI :: Rand StdGen Tree
randTreeI = interleave $ Node <$> getRandom <*> randTreeI <*> randTreeI
>>> hew 2 <$> evalRandIO randTree
Node 2168685089479838995 (Node (-1040559818952481847) Leaf Leaf) (Node ^CInterrupted.
>>> hew 2 <$> evalRandIO randTreeI
Node 8243316398511136358 (Node 4139784028141790719 Leaf Leaf) (Node 4473998613878251948 Leaf Leaf)