[Haskell-cafe] Implementing Las Vegas algorithms in Haskell

[Ketil Malde]

Luke Palmer <lrpalmer at gmail.com> writes:

> 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 wonder if pure values and values in the Random monad as belonging to
different complexity classes?  It's been to long since theory of
computation, but I think the relationship between BPP and the other
classes is a bit unclear.  (Of course, Random isn't limited to
polynomial.) 

> I blogged about this a while ago:
> http://lukepalmer.wordpress.com/2009/01/17/use-monadrandom/

Nice.

I've been busy writing a simulator, and thus needed to model some of
the statistical distributions.  The way I did this, was to say

  data Distribution = Uniform low high | Normal mu sigma | StudentT  ... 

and

  sample :: Distribution -> Random Double
  sample (Normal mu sigma) = ...

one reason to go beyond simply:

  normal :: Double -> Double -> Random Double
  -- normal mu sigma = sample (Normal mu sigma)

is that you might want to do other things with a probability
distribution than sampling it, like querying p-values for a given
sample.

I haven't gotten around to it yet, but I think I can get away by
defining functions for the cumulative distribution and its inverse,
and just write a generic function for 'sample' (which would need to
pull a random probability (0<=p<=1).  (But it might turn out it is
useful to specialize it for simple distributions anyway?) 

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants