• April 15, 2013
• in geek, scala
• 7 min read

List comprehension over non-enumerables in C

As I was trying to finish up my C# implementation of Try[A] for Scando, I ran into some LINQ issues. Or at least I thought I did. Using the LINQ syntax kept failing to call my extension methods and instead fell back to the IEnumerable<T> ones. I thought to myself how unfortunate it was that the LINQ syntax was hard wired to IEnumerable<T>, otherwise it would be perfect to emulate Scala's for comprehensions.

Fortunately I had just watched Runar Bjarnason's excellent "Lambda: The Ultimate Dependency Injection Framework" and recalled usage of a container type similar to how Option<T> and Try<T> are used. I also recalled that projecting such a type with a function that also returned a new instance of that container type via map (roughly equivalent to Select) created nested containers, yet I had a test for Option<T> that looked like this:

[Test]
public void Can_chain_somes() {
 var r = Api.DoSomething()
    .Select(Api.Passthrough)
    .Select(Api.Passthrough)
    .GetOrElse("bar");
 Assert.AreEqual("foo", r);
}

This should have returned an Option<Option<Option<string>>> but instead just returned Option<string>. Obviously my implementation of Select was wrong, which would explain why LINQ syntax didn't use it. And that probably meant that my assumptions about IEnumerable were wrong as well. Runar solved the nested container problem by implementing flatMap which also enabled for comprehensions in Scala. For me that meant that I was also missing SelectMany to make LINQ work properly.

Scala For Comprehension

Before I get into LINQ, I should cover why wrapping a value in a single or no value collection is a useful thing in the first place. Let's look at an example of functions returning Option[A]:

for {
  user <- UserRepository.findById(1) if user.isActive
  profile <- ProfileRepository.getProfileByUser(user)
  url <- profile.url
} yield url

This will get a single Option[User], check that the user is active, fetch the user's profile and then return the profile url. What makes this code special is that we don't have to check that the previous call returned a value. If UserRepository returned None, then the if guard never gets executed (since it gets executed for all values in the "Collection") and likewise ProfileRepository is never called since no user was selected.

With for comprehensions and the Option container we can chain calls and have it handle the short circuiting along the way so we will always receive an Option of the yielded type without checking return values along the way.

LINQ and IEnumerable

Ok, but that's subverting a list processing construct for its behavior on empty collections and Scala's excellent type inference deals with types changing throughout the comprehensions. Can LINQ pull that off?

Turns out, yep, it can. The LINQ syntactic sugar doesn't have any ties to operating on IEnumerable or any type at all. To mimic the Scala for comprehension above, we just need to implement 3 methods.

Select: Transforming C to C

For illustration purposes, I've create a container Type C<T> with an accessor Value. It does not implement IEnumerable<T> as Option<T> originally did (which I've since removed since the only reason had been that I thought I needed it for LINQ).

Let's start with the simplest comprehension style LINQ query:

from x in new C<int>(1) select x

At this point the compiler complains with Could not find an implementation of the query pattern for source type 'Sandbox.C'. 'Select' not found. Simple enough, let's add Select to C<T>:

public C<TResult> Select<TResult>(Func<T, TResult> selector) {
  return new C<TResult>(selector(_value));
}

Note: LINQ does not care whether its methods are provided as methods on the object or extensions. For this example I'm just attaching it straight on C<T> instead of using an Extension Method, so I don't need the this C<T> source argument.

Now that query works and we are getting back a C<T>, not an IEnumerable<T>. That means that we can call .Value directly on the result of the query.

SelectMany: Flatting C>

Next up is passing the result from the first as input to the next call:

from x in new C<int>(1)
from y in new C<int>(x)
select y

Again, it won't compile. Now it complains about SelectMany. Since there are multiple overloads of SelectMany, let's start with the simplest, i.e. a selector to transform T into C<TResult>:

public C<TResult> SelectMany<TResult>(Func<T, C<TResult>> selector ) {
   return selector(Value);
}

Except that just leads to a new compiler error: No overload for method 'SelectMany' takes 2 arguments. To get a closer look at what the compiler wants to do, we can just rewrite the query using int[] instead of C<T>:

from x in new[] {1}
from y in new[] {x}
select x;

Then, using IlSpy and turning Query decompilation off, we can see what .NET actually translates that LINQ to:

new int[] {1}.SelectMany(x => new int[] {x}, (x, y) => y);

That's interesting. Instead of

SelectMany<TSource, TResult>(
  this IEnumerable<TSource> source,
  Func<TSource,IEnumerable<TResult>> selector
)

It's using

SelectMany<TSource, TCollection, TResult>(
  this IEnumerable<TSource> source,
  Func<TSource,IEnumerable<TCollection>> collectionSelector,
  Func<TSource,TCollection,TResult> resultSelector
)

but passes in a resultCollector that merely ignores the first argument and always returns the second, making it functionally equivalent of the first signature. Here's what that looks like as a Method on C<T>:

public C<TResult> SelectMany<TCollection, TResult>(
    Func<T, C<TCollection>> collectionSelector, 
    Func<T, TCollection, TResult> resultCollector
) {
  var c = collectionSelector(Value);
  return new C<TResult>(resultCollector(Value, c.Value));
}

And now the LINQ query with multiple from clauses works.

Where: What does a short circuit of C look like?

Finally, we want to add the guard clause, which in LINQ is simply Where:

from x in new C<T>(1) where x == 1
select x

with Where having the following signature

C<T> Where(Func<T, bool> predicate) { ... }

Implementing the guard poses a problem, though. Where will always return a C<T>, but what does a C<T> that failed the predicate check look like? Which also raises the question, what value does the from retrieve when encountering such a C<T>? If the point was that comprehension lets us short circuit the execution chain, then we need a way to indicate that C<T> doesn't have a value.

For this implementation, I've simply added an IsEmpty flag and use the no argument constructor to construct an empty version. While that takes care of implementing Where, it does point to an oversight in Select and SelectMany. Both need to be aware of IsEmpty and return an empty C<T> rather than executing the selectors in order to provide short-circuiting behavior. The full implementation of C<T> now looks like this:

public class C<T> {

  public C() { IsEmpty = true; }
  public C(T value) { Value = value; }

  public T Value { get; private set; }
  public bool IsEmpty { get; private set; }

  public C<T> Where(Func<T, bool> predicate) {
    if(IsEmpty) {
      return this;
    }
    return predicate(Value) ? this : new C<T>();
  }

  public C<TResult> Select<TResult>(Func<T, TResult> selector) {
    return IsEmpty ? new C<TResult>() : new C<TResult>(selector(Value));
  }

  public C<TResult> SelectMany<TCollection, TResult>(
    Func<T, C<TCollection>> collectionSelector,
    Func<T, TCollection, TResult> resultCollector
  ) {
    if(IsEmpty) {
      return new C<TResult>();
    }
    var c = collectionSelector(Value);
    return c.IsEmpty ? new C<TResult>() : new C<TResult>(resultCollector(Value, c.Value));
  }
}

That still does not answer how from x in a works since that clearly pulls a value from the container. You would expect an enumerator to be required. The key to understanding how this construct works is that the transformation of the call becomes a Select or SelectMany, which has no concept of enumeration. Both have a selector that takes T and converts it into the containerized T, C<T>. Since traditionally the container is IEnumerable, the natural association for x in a is an enumeration, but it really is just an instance of the container with no assumption about what it contains.

Applying LINQ comprehensions

Now that we know how to create a container type, we can create return values for our methods that follow those principles and rewrite the Scala example in C#:

from user in UserRepository.FindById(1) where user.isActive
from profile in ProfileRepository.GetProfileByUser(user)
from url in profile.url
select url

Essentially, C<T> is just a naive re-implementation of Option<T>. The reason I created it instead of just walking through the existing type was to illustrate this container type pattern. It's the pattern Option<T> uses, as does Try<T> and it is used it to implement the Reader Monad for functional dependency injection. The essence of this pattern is that by wrapping T in a container we can attach an environment to it to carry along additional data. In the case of Option, it was the ability to determine the presence or lack of a value for T. In case of Try it is presence of an error occurring while trying to produce T. and for functional Dependency Injection it was the ability to carry along dependencies that a call at the end of a long chain needed without the intermediate calls having to be aware of them. By using the container, functions that care about the environment can take it as input or return it, while functions that don't can be lifted to fit the required shape and take part in the composition without ever needing to be aware of the environment being passed along.

Having used for comprehensions in Scala and seeing how it can remove a lot of imperative boiler plate that does nothing to aid in the comprehension of the workflow, it is nice to see that it requires just three methods to allow LINQ to be used for a similarly expressive syntax for composing method chains.