[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

[Luke Palmer]

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.


Interesting question!

Well, you could make your own random generator for the lifetime of the
function, with a fixed seed.  I'd say this is the most "honest" way to do
it; however, might a malicious user discover your seed, he could design an
input that would make your algorithm perform poorly.

I'm wary of saying you could use unsafePerformIO . randomRIO to get a seed.
 But I think some sort of unsafe something has to be involved, since you are
representing a very advanced proof obligation (the algorithm is independent
of the randomness).

Keep us (me) posted on developments on this idea.

Luke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090706/c85c9f2f/attachment.html