Probability Distribution Monad

In the previous lesson, we discovered the interesting fact that conditional probabilities can be represented as likelihood functions and that applying a conditional probability to a prior probability looks suspiciously like SelectMany, which is usually the bind operation on the sequence monad.

---

Monads in C#

We created a new implementation of SelectMany that creates an object which samples from the prior, calls the likelihood, and then samples from the resulting distribution. Is that the bind operation on the probability distribution monad?

If you’re completely confused by the preceding paragraph, you might want to read an introduction to monads for OO programmers.

We need the following things to have a monad in C#:

1. We need an “embarrassingly generic” type: some Foo<T> where it can sensibly take on any T whatsoever. IDiscreteDistribution<T> meets that condition.
2. The type represents an “amplification of power” of the underlying type. Indeed it does; it allows us to represent a probability distribution of particular values of that type, which is certainly a new power that we did not have before.
3. We need a way of taking any specific value of any T and creating an instance of the monadic type that represents that specific value. Singleton.Distribution(t) meets that condition.
4. There is frequently(but not necessarily) an operation that extracts a value of the underlying type from an instance of the monad. Sample() is that operation. Note that sampling a singleton always gives you back the original value.
5. There is a way to “bind” a new function onto an existing instance of the monad. That operation has the signature M<R> SelectMany<A, R>(M<A> m, Func<A, M<R>> f). We traditionally call it SelectMany in C# because that’s the bind operation on IEnumerable<T>, and it produces a projection on all the elements from a sequence of sequences. As we saw last time, we have this function for probability distributions.
6. Binding the “create a new instance” function to an existing monad must produce an equivalent monad. I think it is pretty clear that if we have an IDiscreteDistribution in hand, call it $d$, that SelectMany(d, t => Singleton.Distribution(t)) produces an object that has the same distribution that $d$ does.

If that’s not clear, play around with the code until it becomes clear to you.

6. Going “the other direction” must also work. That is, if we have a Func<A, IDiscreteDistribution<B>> called $f$, and a value of $A$, then SelectMany(Singleton<A>.Distribution(a), f) and f(a) must produce logically the same IDiscreteDistribution<B>.

Again, if that’s not clear in your mind, step through the code mentally or write some sample code and convince yourself that it is true.

7. Two bind operations “on top of each other” must produce the same logical result as a single bind that is the composition of the two bound functions.

All our conditions are met; IDiscreteDistribution<T> is a monad. So we should be able to use it in a query comprehension, right?

from c in cold
from s in SneezedGivenCold(c)
select s

Unfortunately, this gives an error saying that SelectMany cannot be found; what’s up with that?

The query comprehension syntax requires a slight variation on the traditional “bind” operation; it requires that we also allow a projection on end and that moreover, the projection take both the original value and the transformed value. That is, C# requires us to implement it like this:

public sealed class Combined<A, B, C> : IDiscreteDistribution<C>
{
  private readonly List<C> support;
  private readonly IDiscreteDistribution<A> prior;

  private readonly Func<A, IDiscreteDistribution<B>> likelihood;
  private readonly Func<A, B, C> projection;
  public static IDiscreteDistribution<C> Distribution(IDiscreteDistribution<A> prior, Func<A, IDiscreteDistribution<B>> likelihood, 
      Func<A, B, C> projection) => new Combined<A, B, C>(prior, likelihood, projection);

  private Combined(IDiscreteDistribution<A> prior, Func<A, IDiscreteDistribution<B>> likelihood, Func<A, B, C> projection)
  {
    this.prior = prior;
    this.likelihood = likelihood;
    this.projection = projection;
    var s = from a in prior.Support()
            from b in this.likelihood(a).Support()
            select projection(a, b);
            this.support = s.Distinct().ToList();
  }

  public IEnumerable<C> Support() => this.support.Select(x => x);

  public int Weight(C c) => // NOT YET!

  public C Sample()
  {
    A a = this.prior.Sample();
    B b = this.likelihood(a).Sample();
    return this.projection(a, b);
  }
}

And now we can implement SelectMany as

public static IDiscreteDistribution<C> SelectMany<A, B, C>(this IDiscreteDistribution<A> prior, Func<A, IDiscreteDistribution<B>> likelihood,
    Func<A, B, C> projection) => Combined<A, B, C>.Distribution(prior, likelihood, projection);

and of course, if we want a SelectMany with the traditional monad bind signature, that’s just

public static IDiscreteDistribution<B> SelectMany<A, B>(this

...