[Haskell-cafe] Re: Implementing Las Vegas algorithms in Haskell
Heinrich Apfelmus
apfelmus at quantentunnel.de
Tue Jul 7 11:50:58 EDT 2009
Luke Palmer wrote:
>>>> What I wondered was, if one could hid the random plumbing in some data
>>>> structure, like the state monad, but less linear.
>>> This problem cries for a State monad solution - but you don't need to
>>> do it yourself, there's already a Random monad defined for you.
>>
>> Yes, but I only need the random values inside splitOnMedia. The rest
>> is just non-linear plumbing. We do not know beforehand how many
>> random values a branch quicksort will consume --- neither do we ware
>> about the state of the random generator at the end. Do you consider
>> the RandomMonad the best fit?
>
>
> Random monad is a very natural choice for "random cloud" computations.
> Don't think of it as a state monad -- that's an implementation detail. You
> can think of a value of type Random a as a "probability distribution of
> a's"; and there are natural definitions for the monad operators on this
> semantics.
>
> I blogged about this a while ago:
> http://lukepalmer.wordpress.com/2009/01/17/use-monadrandom/
I concur with Luke that interpreting
Random a
as a probability distribution of values of type a is the best mental
model. The fact that it's a monad is secondary, if crucial for doing
anything with these values.
For a concrete example,
http://apfelmus.nfshost.com/random-permutations.html
might help.
Regards,
apfelmus
--
http://apfelmus.nfshost.com
More information about the Haskell-Cafe
mailing list