[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

Antoine Latter aslatter at gmail.com
Tue Jul 7 02:10:01 EDT 2009


2009/7/6 Matthias Görgens <matthias.goergens at googlemail.com>:
> 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.

If I were using the function in an executable I were writing, I would
probably do something like unsafePerformIO . randomIO. Or thread in
the random Gen from main if it were convenient.

If I were writing it as a library function, I would leave the function
as you described and let the caller make the choice. Calling into
randomIO in a library function is extremely dubious, as a second
library could be getting and setting the random seed used by randomIO
(see setStdGen).

So I'm okay taking on that risk in an application I write, but I'm not
okay shipping that risk in a re-usable library, with the risk hidden
behind a type signature.

Maybe I'm just paranoid.

Antoine


More information about the Haskell-Cafe mailing list