2009/7/6 Matthias Görgens <[email protected]> > 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
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
