> the random number generator is stateful which conflicts with laziness

It's not difficult to create a stateful computation in a non-strict runtime environment. Laziness is compatible with (local) state. Haskell's random package is designed around explicitly threading the PRNG state through the computation:

    import System.Random (Random, RandomGen, random)
    import Data.List (unfoldr)

    randomList ∷ (Random a, RandomGen g) ⇒ g → [a]
    randomList = unfoldr (Just ∘ random)

Since the function passed to `unfoldr` always returns a `Just` value, the resulting lazy list never ends. If you're not familiar with `unfoldr`, it's essentially the opposite of `foldr`: instead of applying a reduction function to a list it produces a list by iteratively applying a generator function to a seed—in this case the PRNG state.

As it happens, this function already exists as `System.Random.randoms`. You use it like this:

    main = do
      (xs :: [Int]) ← randoms <$> newStdGen
      mapM_ print xs

There are related functions `randomR` and `randomRs` which take a lower and upper bound in addition to the state.

If you were trying to achieve this effect with `randomIO` or `randomRIO`—perhaps to avoid explicitly threading the state—then you will run into difficulties. Not because of laziness; rather the contrary. The problem is that IO actions are strict by default, so you can't easily combine them to create a lazy list. You would need to use something like `System.IO.Unsafe.unsafeInterleaveIO` to defer the generation of the random values until they were actually demanded, but then you're mutating the shared, global PRNG state each time an item is evaluated from the list and the result would not be deterministic or repeatable even if you started with a known seed.

There's no reason that you can't do this. Of course, you're not going to be able to just simply return a list of random numbers. But you can get a Rand [Int] or whatever and then evaluate it in an IO monad using evalRandIO.

What was the problem exactly? I don't see any issues with generating e.g. an infinite list of random numbers in Haskell.

On the one hand, of course you can. But I do understand how it might seem tricky if you're too focused on trying to glue together `Gen a`s (or even `MonadRandom m => m a`s), principally with Monad.

To the grandparent, assuming the trouble was as I understand it, the idea is to split your state and advance one new state down the lazy list while the rest of the computation uses the other new state.

Eliding constraints for brevity, if you have:

    split :: g -> (g, g)
    random :: g -> (a, g)

then you can say

    lazyRandomList :: g -> ([a], g)
    lazyRandomList oldState =
        let (listState, newState) = split oldState
         in (makeList listState, newState)
      where
        makeList inState =
            let (value, nextState) = random inState
             in value : makeList nextState

When you match on the outer tuple, the split gets forced, but `makeList listState` is still a thunk. You can go ahead and use `newState` all you want without forcing it.

Once you force it, you have a cons, with two thunks that can be forced independently. The tail evaluates to a similar cons produced from a different state. A lazy list.

It's true that it's infinite, but you can fix that (if you want to) by taking the head (perhaps a random number of elements); it's easier to control the distribution of length that way than with some fixed chance you produce nil at each step, although that approach works too.