Ketil Malde ketil at malde.org
Tue Jul 7 04:04:25 EDT 2009

```Matthias Görgens <matthias.goergens at googlemail.com> writes:

> Yes, I thought of a similar scheme.  Say we want to implemented
> randomized quicksort.  Passing a list of random numbers would destroy
> laziness and linearise the algorithm --- because the right recursion
> branch would need to know at least how many random numbers where
> consumed by the left branch.

Well, you could implement a function 'split' as

split (x:xs) = (evens (x:xs), evens xs)
where evens (y:_:ys) = y:evens ys

This would divide your supply of random numbers in two - this is lazy,
but forcing any of the sublists would force the spine of the original
list, so not optimal.

So the obvious followup is why not pass a randomGen around instead,
which has a split operation already defined, and which causes no

> What I wondered was, if one could hid the random plumbing in some data
> structure, like the state monad, but less linear.

This problem cries for a State monad solution - but you don't need to