<div class="gmail_quote">2009/7/6 Matthias Görgens <span dir="ltr">&lt;<a href="mailto:matthias.goergens@googlemail.com">matthias.goergens@googlemail.com</a>&gt;</span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
A Las Vegas algorithm, like randomized quicksort, uses a source of<br>
randomness to make certain decisions.  However its output is<br>
unaffected by the randomness.  So a function<br>
<br>
&gt; f :: RandomGen g =&gt; g -&gt; a -&gt; b<br>
<br>
implementing a Las-Vegas-Algorithm &#39;looks&#39; like a pure function,<br>
ignoring its first argument and depending solely on its second<br>
argument.  What is an idiomatic way to implement such a function?  I<br>
believe, Monads are too linear and strict.</blockquote><div><br></div><div>Interesting question!</div><div><br></div><div>Well, you could make your own random generator for the lifetime of the function, with a fixed seed.  I&#39;d say this is the most &quot;honest&quot; way to do it; however, might a malicious user discover your seed, he could design an input that would make your algorithm perform poorly. </div>
<div><br></div><div>I&#39;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). </div>
<div><br></div><div>Keep us (me) posted on developments on this idea.</div><div><br></div><div>Luke</div></div>