[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

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.