Treating `IDistribution<T>` as a monad or functor

[djcarter85]

The IDistribution<T> interface forms a monad. Is there scope for adding implementations of unit, map and bind to RandN? Or perhaps to add Select and SelectMany extension methods so that it could be used with query syntax.

[djcarter85]

I should add - if this was viewed as an acceptable addition to the library, I'd be interested in contributing, both in terms of API design and implementation.

[ociaw]

Could you provide examples of what the API might look like? I'm not sure if these would fit in best as part of IDistribution<T>, or as extension methods. And if extension methods, as part of RandN or a companion package.

[djcarter85]

Sure! I’ll put together some ideas and post them here soon.

As a general point I’d suggest not having them as part of IDistribution<T>, because otherwise every implementation will need to support these methods. I think an extension method might work best. A companion package could work really well.

[djcarter85]

OK, here goes ...

The API for the unit function would be pretty simple.

public static class Distribution
{
    public static IDistribution<T> Unit<T>(T item)
    { 
        // Implementation
    }
}

IDistribution<string> unitDistribution = Distribution.Unit("unit");

In fact, you could say that the singleton distribution (the distribution that always returns the same value) deserves its own place in the API (like the existing Bernoulli and Uniform distributions). Something like:

public static class Singleton
{
    public static IDistribution<T> New<T>(T item)
    { 
        // Implementation
    }
}

IDistribution<string> singletonDistribution = Singleton.New("singleton");

One way of implementing the map and bind functions would be to make them static methods in a static class:

public static class Distribution
{
    public static IDistribution<TResult> Map<TSource, TResult>(
        IDistribution<TSource> distribution,
        Func<TSource, TResult> selector)
    {
        // Implementation
    }

    public static IDistribution<TResult> Bind<TSource, TResult>(
        IDistribution<TSource> distribution,
        Func<TSource, IDistribution<TResult>> selector)
    {
        // Implementation
    }
}

IDistribution<int> evenNumbersDistribution = Distribution.Map(
    Uniform.NewInclusive(0, 5),
    i => i * 2);

// Don't ask what sort of distribution this one gives - it's just an example!
IDistribution<PointF> distribution = Distribution.Bind(
    Uniform.NewInclusive(0, 5),
    x => Uniform.NewInclusive(0, x));

Perhaps they could be implemented as extension methods, which would allow you to do this:

IDistribution<int> evenNumbersDistribution = 
    Uniform.NewInclusive(0, 5).Map(i => i * 2);

IDistribution<int> distribution =
    Uniform.NewInclusive(0, 5).Bind(x => Uniform.NewInclusive(0, x));

The alternative would be to follow the LINQ pattern, and rename Map to Select and Bind to SelectMany:

IDistribution<int> evenNumbersDistribution = 
    Uniform.NewInclusive(0, 5).Select(i => i * 2);

IDistribution<PointF> distribution =
    Uniform.NewInclusive(0, 5).SelectMany(x => Uniform.NewInclusive(0, x));

And then, with the addition of another overload of SelectMany, you can use LINQ query syntax:

IDistribution<int> evenNumbersDistribution =
    from i in Uniform.NewInclusive(0, 5)
    select i * 2;

public static class DistributionExtensions
{
    public static IDistribution<C> SelectMany<A, B, C>(
        this IDistribution<A> distribution,
        Func<A, IDistribution<B>> function,
        Func<A, B, C> projection)
    {
        // Implementation
    }
}

IDistribution<PointF> pointDistribution =
    from x in Uniform.NewInclusive(0.0, 1.0)
    from y in Uniform.NewInclusive(0.0, 1.0)
    select new System.Drawing.PointF(x, y);

I can't tell whether this re-use of LINQ query syntax is good or not. It might not be obvious at first glance that it's operating on distributions rather than enumerables, but I do think it's quite a neat way of building new distributions out of old ones. This might be a good candidate for a separate package, as then it would make it opt-in for those that wanted it.

Reading back over these options, I don't think they are mutually exclusive. You could provide multiple ways to do the same thing, to give the consumer more options in how they write their code. However the cost of that is that it could be confusing, as it wouldn't be obvious from the outside that two similar functions are actually identical. I don't know which way I lean on that!

I've deliberately left out the implementation here so we can focus on the interface. However it would be important that the implementation satisfied the functor and monad laws. I can provide sample implementations if you like - I think they're reasonably straightforward to get functionally correct but I have no idea of the performance requirements for a library like this.

[ociaw]

Yep, I think extension methods are the way to go with this. Default interface members could be used as well to avoid re-implementing them, but I can't think of any reason to use them instead of extensions.

Naming is a big question - I definitely don't want two methods with different names that do the same thing. Map/Bind are probably not as familiar to C# users as Select would be. I think Select/SelectMany would make sense. (Now that I think about it, I wonder if providing an IEnumerable implementation around IDistribution would be useful...)

Regarding return types - I'm partial to the idea of returning concrete types instead of interfaces where possible. For example:

public static class Singleton
{
    public static SingletonDistribution<T> New<T>(T item)
    { 
        // Implementation
    }
}

Which would let the runtime avoid dynamic dispatch in some situations. On the other hand it does take away some flexibility - the tradeoff might not be worth it.

I don't think implementation performance will be too much of an issue, though obviously it should be as fast as reasonable. It's generally understood (citation needed) that LINQ isn't the fastest way to accomplish something, and if someone needs as much performance as possible, they can drop down to using IDistribution.TrySample directly.

Another question that needs to be answered is how will SelectMany/Bind/anything aggregating 2+ distributions work with failure to sample. Is it important that the distributions remain "synchronized"? Ex, DistC is composed of DistA and DistB, and we call TrySample on DistC - if DistA.TrySample fails, should we be lazy and fail immediately, or instead call DistB.TrySample anyway and discard the result? And when calling Sample on DistC, should we be lazy and call DistA.Sample and then DistB.Sample, or instead call TrySample on both simultaneously until they both succeed?

I don't see an issue with not forcing them to be synchronized, but it's something to keep in mind, and whatever is chosen needs to remain consistent and documented for the sake of reproducibility.

[djcarter85]

Yep, I think extension methods are the way to go with this. Default interface members could be used as well to avoid re-implementing them, but I can't think of any reason to use them instead of extensions.

Agree, that sounds sensible.

Naming is a big question - I definitely don't want two methods with different names that do the same thing. Map/Bind are probably not as familiar to C# users as Select would be. I think Select/SelectMany would make sense. (Now that I think about it, I wonder if providing an IEnumerable implementation around IDistribution would be useful...)

I agree; I've been using C# for 7 years and only came across the idea of map and bind in the last couple (and even then it was only because I started to look into F#).

Regarding return types - I'm partial to the idea of returning concrete types instead of interfaces where possible. ... Which would let the runtime avoid dynamic dispatch in some situations. On the other hand it does take away some flexibility - the tradeoff might not be worth it.

From an API design point of view, I think either would be fine. I don't know much about how the runtime actually works so I don't know the considerations there.

I don't think implementation performance will be too much of an issue, though obviously it should be as fast as reasonable. It's generally understood (citation needed) that LINQ isn't the fastest way to accomplish something, and if someone needs as much performance as possible, they can drop down to using IDistribution.TrySample directly.

Sounds good. I've not really worked with benchmarking before but I guess we'd add something the Benchmarks.csproj and run some tests?

Another question that needs to be answered is how will SelectMany/Bind/anything aggregating 2+ distributions work with failure to sample. Is it important that the distributions remain "synchronized"? Ex, DistC is composed of DistA and DistB, and we call TrySample on DistC - if DistA.TrySample fails, should we be lazy and fail immediately, or instead call DistB.TrySample anyway and discard the result?

My gut feel would be the former (fail fast) but I don't really have any evidence on it. Perhaps it would be worth coming up with some scenarios where people might use these and see what would be the best thing to do in each one?

And when calling Sample on DistC, should we be lazy and call DistA.Sample and then DistB.Sample, or instead call TrySample on both simultaneously until they both succeed?

Good question, and one I was unsure about. Before coming across RandN I had a play with distributions myself but the interface I came up with only had the Sample method (not the TrySample) method so I haven't had to answer that question!

whatever is chosen needs to remain consistent and documented for the sake of reproducibility.

Strongly agree!

[ociaw]

@djcarter85 Thank you for the PRs! I think the only thing that's left for this ticket is to add documentation - I think these deserve their own page. If you're still interested I'd welcome your input, otherwise I'll finish it up.

[djcarter85]

@ociaw I'm quite busy at the moment so I don't think I have time to write the docs. But I could offer a review if that would be helpful?