[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

[Matthias Görgens]

A Las Vegas algorithm, like randomized quicksort, uses a source of
randomness to make certain decisions.  However its output is
unaffected by the randomness.  So a function

> f :: RandomGen g => g -> a -> b

implementing a Las-Vegas-Algorithm 'looks' like a pure function,
ignoring its first argument and depending solely on its second
argument.  What is an idiomatic way to implement such a function?  I
believe, Monads are too linear and strict.