[Haskell-cafe] Re: Implementing Las Vegas algorithms in Haskell

[Heinrich Apfelmus]

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