[Haskell-cafe] Implementing Las Vegas algorithms in Haskell
Ketil Malde
ketil at malde.org
Tue Jul 7 05:47:58 EDT 2009
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
More information about the Haskell-Cafe
mailing list