[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

Matthias Görgens matthias.goergens at googlemail.com
Mon Jul 6 21:08:43 EDT 2009

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.

More information about the Haskell-Cafe mailing list