I have a simple Either
type:
public class Left<L, R> : Either<L, R>
{
public override string ToString()
{
return Left.ToString();
}
public Left(L left)
{
Left = left;
IsLeft = true;
}
}
public class Right<L, R> : Either<L, R>
{
public override string ToString()
{
return Right.ToString();
}
public Right(R right)
{
Right = right;
IsRight = true;
}
}
public class Either<L, R>
{
public bool IsLeft {get; protected set;}
public bool IsRight {get; protected set;}
public L Left {get; protected set;}
public R Right {get; protected set;}
public Either(L left)
{
Left = left;
IsLeft = true;
}
public Either(R right)
{
Right = right;
IsRight = true;
}
public Either()
{
}
}
I'd like to use this type with LINQ query syntax. I can implement Select
, but I can't quite figure out the SelectMany
method signature required. More accurately, this works:
var l = new Either<string, int>("no, this is a left");
var r = new Either<string, int>(2);
var ret5 =
from x in l
from y in r
select y;
// returns ret5 as a Left, with the expected message
if I use the following implentation:
public static Either<L, RR> SelectMany<L, R, RR>(
this Either<L, R> either, // the source "collection"
Func<R, Either<L, R>> g, // why R here? why not L, R. can only be 1 argument. Func<TSource, IEnumerable<TCollection>> collectionSelector,
Func<L, R, RR> f // a transform that takes the contained items and converts to the transformed right
)
{
if (either.IsLeft) return new Left<L, RR>(either.Left);
var inner = g(either.Right);
if (inner.IsLeft) return new Left<L, RR>(inner.Left);
return new Right<L, RR>(f(inner.Left, inner.Right));
}
but I can't mentally correlate it with the documented signature (here from Jon Skeet's Edulinq post)
public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult>(
this IEnumerable<TSource> source,
Func<TSource, IEnumerable<TCollection>> collectionSelector,
Func<TSource, TCollection, TResult> resultSelector)
Is there a general way of understanding what the signature of your SelectMany
method should be for classes with multiple generic parameters?
EDIT: The LaYumba library has a similar signature for a Transition
example class so .. are the complete set of SelectMany
overloads documented somewhere - including those for multi-parameter types?
EDIT: very delayed edit, but the reference source details the signatures for IEnumerable<>.SelectMany
, but doesn't tell you why they're needed. You can dig through the compiler code to get there but it's a painful journey.
The suggested SelectMany
overload only compiles because the only test case doesn't change the types. That is, in
var ret5 =
from x in l
from y in r
select y;
both l
and r
have the same type: Either<string, int>
. Thus, while being too constrained, the suggested SelectMany
overload is actually enough to make the code compile. It's not flexible enough, however, to map between different types of Eithers.
The correct type of SelectMany
is:
public static Either<L, RR> SelectMany<L, R, T, RR>(
this Either<L, R> source,
Func<R, Either<L, T>> k,
Func<R, T, RR> s)
It may help to forget this particular overload for a little while, since it's a C#-specific weirdness that has no equivalent in other languages that I'm aware of (F# and Haskell).
The standard SelectMany
method in C# corresponds to what is usually known as monadic bind. For the Either
type in the OP, it'd look like this:
public static Either<L, RR> SelectMany<L, R, RR>(
this Either<L, R> source,
Func<R, Either<L, RR>> selector)
{
if (source.IsLeft)
return new Left<L, RR>(source.Left);
return selector(source.Right);
}
This overload is much easier to deal with, since it doesn't require that weird extra-step function that the other overload takes.
To be clear, however, the other overload is required to make query syntax light up, so I'll get back to that later.
If you can implement a SelectMany
method like this one, the type forms a monad. Notice that it only maps the right-hand side, though. This may be easier to see if we also add a Select
method.
All monads are also functors. You can always implement Select
if you have a lawful SelectMany
(monadic bind), and the implementation is entirely automatable:
public static Either<L, RR> Select<L, R, RR>(
this Either<L, R> source,
Func<R, RR> selector)
{
return source.SelectMany(r => new Right<L, RR>(selector(r)));
}
Notice that Select
only maps R
to RR
while L
stays fixed. Either is actually not just a single functor, but a family of functors - one for each L
. For example, Either<string, R>
gives rise to a different functor than Either<int, R>
. Either is, however, a bifunctor.
There's only one type to map: R
.
These two method are enough if you only need method call syntax, but if you also need query syntax, you're going to need that other SelectMany
overload. As far as I can tell, if you already have Select
and SelectMany
, you can always(?) implement the other overload with the same nested lambda express:
public static Either<L, RR> SelectMany<L, R, T, RR>(
this Either<L, R> source,
Func<R, Either<L, T>> k,
Func<R, T, RR> s)
{
return source.SelectMany(x => k(x).Select(y => s(x, y)));
}
I actually copy-pasted that expression from a SelectMany
method for an entirely different monad (State).
Notice again that L
is fixed. It doesn't partake in any mappings, so it's as though it wasn't there. The 'intermediary' type is here called T
.
The reason that the method suggested in the OP compiled is that the C# compiler is actually quite forgiving. If you make the generic types less generic than you have to, it still compiles.
For example, much to my surprise, I last year discovered that you can also use a more constrained Select
method to implement monomorphic functors.
All this said, you should consider adding some encapsulation to the types in question. As the code stands, anyone can add a new class that inherits from Either<L, R>
and behaves completely erratically.
You may, for example, instead consider a Church-encoded Either.