[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

[Ketil Malde]

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
laziness headaches?

> 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
do it yourself, there's already a Random monad defined for you.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants