On Jun 4, 2010, at 1:19 AM, Alexander Solla wrote:

We don't necessarily have to compute the inverse of the distribution via sampling to do it.  It can be done algebraically, in terms of the convolution operator.  Since the types are enumerated, wouldn't something like... work?

-- A set and binary operation.  We have an algebra.  I like the J for 'join'.
-- With this algebra, we can use the real-complex analytical methods to
-- interpret the terms later, if we want to actually reify a Distribution
-- instance as a "Real" (Float, Double) function.

> data DistributionJ a = UniformDistribution Uniform a
> | ...
> | ExponentialDistribution Exponential a
> | DistributionJ a `Convolve` (DistributionJ a)


-- I hope I understand the semantics for the PromptT monad.
> newtype RVarT m a = RVarT { unRVarT :: PromptT (Prim, DistributionJ) m a }

I guess threading fst and snd in all the low level computations is inelegant, but it's a step closer.

An algebraic solution would work as long as the user only made use of a very small set of supported operations.  Unfortunately, even detecting whether they have done so in any implementation supporting Monad is not really feasible.  The Functor/Applicative/Monad classes allow inclusion of arbitrary functions in the construction of an RVar, which is a very big part of the usefulness of the system.  Even in a simple no-op defininion such as "fmap id x", fmap has no way of discovering whether the function is "id", "negate", "primes !!", or worse, so the only way (I believe) to effectively propagate the algebraic part would be to drop the Functor, Applicative and Monad instances and work with RVars solely via some combinator library.  At that point, why not just work with the symbolic form directly and choose at the end whether to sample or compute a pdf?  You could make DistributionJ an instance of Distribution to make it sampleable, and do precisely that.  In fact, that would probably be a pretty nifty thing to do.

-- James

PS - the usage of DistributionJ in the prompt wouldn't quite work, because a "DistributionJ a" would just be a standin for a computation of type "m a" where "m" is the monad in which the variable is eventually sampled.  There is no way to rediscover the particular constructor that was used for the prompt, for approximately the same reasons as above.