CODEWITHSUNDEEP
c#linqfunctional-programmingmonads
Ben
Ben

Reputation: 282

How to mix monadic constructs in a single Linq expression?

I have a toy implementation of a Maybe monad in C# and have implemented the relevant SelectMany extension methods to work with Linq. I stumbled upon a problem when I tried to mix IEnumerable and IMaybe in a single Linq statement.

The Maybe monad looks like

public interface IMaybe<T>
{
    bool HasValue { get; }
    T Value { get; }
}

public static class Maybe
{
    class SomeImpl<T>: IMaybe<T> // obvious implementation snipped for brevity
    class NoneImpl<T>: IMaybe<T> // obvious implementation snipped for brevity

    // methods to construct the Maybe monad
    public static Wrap<T> Some<T>(T value);
    public static Wrap<T> Some<T>(T? value) where T: struct;
    public static IMaybe<T> None<T>();

    public static IMaybe<B> SelectMany<A, B>(this IMaybe<A> a, Func<A, IMaybe<B>> mapFn)
    {
        if (a.HasValue)
            return mapFn(a.Value);
        else
            return None<B>();
    }

    public static IMaybe<C> SelectMany<A, B, C>(
        this IMaybe<A> a, Func<A, IMaybe<B>> mapFn, Func<A, B, C> selector)
    {
        if (a.HasValue)
        {
            var b = mapFn(a.Value);
            if (b.HasValue)
                return Some(selector(a.Value, b.Value));
            else
                return None<C>();
        }
        else
            return None<C>();
    }
}

My program tries to read a file, parse the content into a number of URI entries, and for each of the entries download the content from the URI. Exactly how these operations are implemented is irrelevant. The trouble I have lies in the chaining these operations in a Linq statement. I.e.

    static IMaybe<string> ReadFile(string path);
    static IMaybe<KeyValuePair<string, Uri>[]> ParseEntries(string input);
    static IMaybe<string> Download(Uri location);

    static void Main(string[] args)
    {
        var result = // IEnumerable<IMaybe<anonymous type of {Key, Content}>>
            from fileContent in ReadFile(args[0])
            from entries     in ParseEntries(fileContent)
            from entry       in entries                   // this line won't compile
            from download    in Download(entry.Value)
            select new { Key = entry.Key, Content = download };

        // rest of program snipped off for brevity
    }

The error in question complains about mixing the IMaybe and IEnumerable monads. In its exact wording:

Error 1 An expression of type 'System.Collections.Generic.KeyValuePair[]' is not allowed in a subsequent from clause in a query expression with source type 'MonadicSharp.IMaybe'. Type inference failed in the call to 'SelectMany'. C:\Dev\Local\MonadicSharp\MonadicSharp\Program.cs 142 31 MonadicSharp

How do I get around this?

Upvotes: 2

Views: 228

Answers (3)

Ben
Ben

Reputation: 282

After some research I've concluded that it is just impossible to mix monads in a single LINQ statement so I decided to break it into two statements. This is how it works:

First off, I need to make a slight change to the IMaybe interface declaration to use covariance:

public interface IMaybe<out T>{ ... }

Next, I need some helper method to transform the IMaybe monad to the IEnumerable monad:

public static IEnumerable<IMaybe<T>> UnfoldAll<T>(
    this IMaybe<IEnumerable<T>> source)
{
    if (source.HasValue)
        return Enumerable.Range(0, 1).Select(i => Maybe.None<T>());
    else
        return source.Value.Select(value => Maybe.Some(value));
}

And finally, I will break the original LINQ statement into two statements (nesting LINQ expressions works too)

static void Main(string[] args)
{
    var path = args[0];
    var theEntries =
        from fileContent in ReadFile(path)
        from entries in ParseEntries(fileContent)
        select entries;

    var theContents = 
        from entry in theEntries.UnfoldAll() 
        where entry.HasValue 
        select Download(entry.Value.Value);

    foreach (var content in theContents)
    {
        //...
    }
}

As you can see, the first LINQ statement works on IMaybe monad and the second one on the IEnumerable.

Upvotes: 0

Enigmativity
Enigmativity

Reputation: 117029

It seems to me that the issue lies in the signature for ParseEntries.

It currently is:

static IMaybe<KeyValuePair<string, Uri>[]> ParseEntries(string input);

Perhaps it should be?

static IMaybe<KeyValuePair<string, Uri>>[] ParseEntries(string input);

So instead of a maybe of array it should be an array of maybe.

Upvotes: 1

Matt Ko
Matt Ko

Reputation: 979

I think the issue is because entries is of type IMaybe<T> and not of type IEnumerable<T>.
Have you tried something like this:

from entry       in entries.Value

Of course this is not what the purpose of a Monad is, but this should be the first step.

Upvotes: 0

Related Questions