Proposal: "with" as a LINQ query expression clause (for Zip())

[orthoxerox]

Pasted from dotnet/roslyn#8221

I propose to add a with clause to the query expression syntax. This will allow us to zip sequences together using either LINQ syntax.

A query expression with a with clause followed by a select clause

from x1 in e1
with x2 in e2 
select v

is translated into

( e1 ) . Zip( e2, ( x1 , x2 ) => v )

A query expression with a with clause followed by something other than a select clause

from x1 in e1
with x2 in e2 
…

is translated into

from * in ( e1 ) . Zip(
        e2 , ( x1 , x2 ) => new { x1 , x2 })
…

This transformation would happen in section 7.16.2.4 of the spec:

from x1 in e1
from x2 in e2
with x3 in e3
…

is first translated into

from * in ( e1 ) . SelectMany( x1 => e2 , ( x1 , x2 ) => new { x1 , x2 } )
with x3 in e3
…

and then translated into (if I understand how transparent identifiers work)

from ** in ( ( e1 ) . SelectMany( x1 => e2 , ( x1 , x2 ) => new { x1 , x2 } ) ) . Zip(
        e2 , ( * , x3 ) => new { * , x3 })
…

And

from x1 in e1
with x2 in e2
from x3 in e3
…

is first translated into

from * in ( e1 ) . Zip( e2 , ( x1 , x2 ) => new { x1 , x2 })
from x3 in e3
…

and then translated into

from ** in ( ( e1 ) . Zip( e2 , ( x1 , x2 ) => new { x1 , x2 }) ).SelectMany( 
        * => e3 , ( * , x3 ) => new { * , x3 } )
…

---

2017 update: I won't mind if this is called zip join or anything similar, but with makes sense for more LINQables than IEnumerable<T>.

[phi1010]

I'm using zip() more often than I'd like too, but mostly user-defined variants, since the standard zip() implementation often doesn't work the way I want when dealing with differently-sized IEnumerables.

Thus, I'd rather like a keyword which allows me to define my own zip method, without requiring me to begin using the myIenumerable.callsomeextensionmethodhere method call syntax, maybe something that accepts a delegate:

using static System.Linq.Enumerable; // import the Zip() method into scope
IEnumerable<T1> e1;
IEnumerable<T2> e2;
IEnumerable<T3> e3;

from x1 in e1
from x2 in e2
from x3 in e3 with Zip
// variables in scope here: x1,x2,x3

instead of

from x1 in e1
from x2 in e2
with x3 in e3

The delegate in the with-clause might accept any two IEnumerables: The first one defined by the from clauses above, containing all variables defined until then, maybe represented as objects with the type of the new tuple construct), and the second one defined by the from clause just in front of it.

If non-existant, this "with" statement would default to "return the cross product of those two IEnumerables", as multiple from statements already do; if it is specified, we use this one instead, and can create a Zip, a union or something else with it, as long as the returned values have the right type. The type of the method passed as delegate would (only in the example above!) have to fit this delegate, which can be determined at compile-time:

IEnumerable<Tuple<(... some return variables ...),(... some return variables ...)>> WithDelegate(IEnumerable<(T1 x1, T2 x2)> first, IEnumerable<(T3 x3)> second)
// implemented by Zip using these generic parameters:
IEnumerable<Tuple<(T1 x1, T2 x2),(T3 x3)>> Zip(IEnumerable<(T1 x1, T2 x2)> first, IEnumerable<(T3 x3)> second)

Zip() would make use of the first option, not touching the names of the variables, because the property names of the tuple are already unique in the existing scope.

---

Later, with another possible delegate type, one might also extend the with syntax to allow Unions, Intersects or similar method calls:

IEnumerable<(... some variables for the scope after the for-with-statement ...)> WithDelegate(IEnumerable<(T1 x1, T2 x2)> first, IEnumerable<(T4)> second)
// implemented by Union using these generic parameters:
IEnumerable<(T45 y45)> Union(IEnumerable<(T45 y45)> first, IEnumerable<(T45 y45)> second)

Allowing the compiler to allow this usage:

IEnumerable<T45> e4,e5;
...
from y45 in e4
from y45 in e5 with Union
// variables in scope here: y45

[orthoxerox]

Prototype ready in https://github.com/orthoxerox/roslyn/tree/features/linq-with

[atifaziz]

Today, you can abuse join to get the same effect:

from x in Enumerable.Range(1, 2)
join y in Enumerable.Range(1, 2) on 1 equals 1
join z in Enumerable.Range(1, 3) on 1 equals 1
select new { x, y, z }

The ugly part is on 1 equals 1. A natural subtraction then would be that if on is absent:

from x in Enumerable.Range(1, 2)
join y in Enumerable.Range(1, 2)
join z in Enumerable.Range(1, 3)
select new { x, y, z }

then it simply translates to calling Zip that exists today. We wouldn't need new keywords like zip or with because it is a cross-join after all.

[orthoxerox]

Zip ain't a cross join. A cross join is expressed as multiple sequential from clauses.

[atifaziz]

A cross join is expressed as multiple sequential from clauses.

That may seem to be the effect but multiple from clauses actually form a sequential chain of dependents (bind) whereas joins do not. Same goes for zip where the two inputs are independent and simply merged.

For example:

from x in Enumerable.Range(1, 2)
from y in Enumerable.Range(1, x)     // you can use & depend on x here
from z in Enumerable.Range(1, x + y) // you can use & depend on x and y here
select new { x, y, z }

But here, you can't:

from x in Enumerable.Range(1, 2)
join y in Enumerable.Range(1, 2) // can't use x
join z in Enumerable.Range(1, 3) // can't use neither x nor y
select new { x, y, z }

In current LINQ's join, you can only use the range or bound variable for key selection, after on.

[svick]

@atifaziz But cross-join is still very different from a zip. For example, with your "join abuse":

from x in Enumerable.Range(1, 2)
join y in Enumerable.Range(1, 2) on 1 equals 1
select new { x, y }

the output is:

x	y
1	1
1	2
2	1
2	2

But for zip:

Enumerable.Range(1, 2).Zip(Enumerable.Range(1, 2), (x, y) => new { x, y })

the output is:

x	y
1	1
2	2

[chrisoverzero]

[…] multiple from clauses actually form a sequential chain of dependents (bind) […]

Right. And @orthoxerox, in asking for Zip, is effectively asking for applicative support in LINQ. (Or, like, in its keyword-style syntax.) Which, for whatever it’s worth, I would love.

[atifaziz]

@svick @chrisoverzero @orthoxerox When I wrote my comments earlier, I was being quick and brief as I was having quite a packed Friday. Reflecting back, I see that I might have done more harm than good so now that I am having a quiet Sunday, let me take the time to explain the position a bit better.

Before I proceed, I want to add the disclaimer that I am neither an academic nor do I have any experience in language design. I am coming at this purely from the angle of mechanical/logical deduction and floating an alternative that requires the least change.

I don't want to imply that a cross-join is the same thing as a zip and perhaps borrowing cross-join from set theory may have been misleading. Nevertheless, l think we all agree that the following gives you a cross-join for lists:

from x in Enumerable.Range(1, 2)
join y in Enumerable.Range(1, 2) on 1 equals 1
join z in Enumerable.Range(1, 3) on 1 equals 1
select new { x, y, z }

What I am suggesting is that the on part can be made optional and in doing so, it would mean that instead of looking for Join with the following signature (doesn't have to be an extension method as you'll see later but makes the discussion easier by being able to express full & self-contained signatures):

public static IEnumerable<TResult>
    Join<TOuter,TInner,TKey,TResult>(
        this IEnumerable<TOuter> outer,
        IEnumerable<TInner> inner
        Func<TOuter,TKey> outerKeySelector,
        Func<TInner,TKey> innerKeySelector,
        Func<TOuter,TInner,TResult> resultSelector);

it would instead look for:

public static IEnumerable<TResult>
    Join<TOuter,TInner,TResult>(
        this IEnumerable<TOuter> outer,
        IEnumerable<TInner> inner
        Func<TOuter,TInner,TResult> resultSelector);

When you drop the key projection functions and look at that signature, it's identical to Zip today:

public static IEnumerable<TResult>
    Zip<TFirst,TSecond,TResult>(
        this IEnumerable<TFirst> first,
        IEnumerable<TSecond> second,
        Func<TFirst,TSecond,TResult> resultSelector);

The parallel stands out even more if you name the type and method parameters identically across the two:

IEnumerable<V> Join<T, U, V>(this IEnumerable<T> xs, IEnumerable<U> ys, Func<T, U, V> f);
IEnumerable<V> Zip <T, U, V>(this IEnumerable<T> xs, IEnumerable<U> ys, Func<T, U, V> f);

This is what I meant by “it's just Zip” but that might have been misleading in hindsight.

For most computational contexts that I've worked with that aren't about sets or sequences, and this is important, the two will have an identical implementation! That is, Join can be implemented as Zip. For example, for some optional type implementation, the following naturally reads as a cross product of options:

from x in Some(1)
join y in Some(2)
join z in Some(3)
select new { x, y, z }

You can do this today with multiple from clauses (SelectMany chain):

from x in Some(1)
from y in Some(2)
from z in Some(3)
select new { x, y, z }

but it's unnecessary and even restricting when a join is more appropriate. Sometimes, it's even more correct where you want to enforce independence. In other words, I want to support cross-join and implement Join but not SelectMany.

Returning to sequences, if we have cross-join then we can support Zip with an extra wrapper that gives Join the semantics of Zip and here's how you can do that today.

Suppose the following wrapper:

sealed class ZipList<T> : IEnumerable<T>
{
    readonly IEnumerable<T> source;
    
    public ZipList(IEnumerable<T> source) =>
        this.source = source;

    public IEnumerator<T> GetEnumerator() => source.GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public ZipList<V>
        Join<U, K, V>(IEnumerable<U> second,
                      Func<T, K> k1, // unused!
                      Func<U, K> k2, // unused!
                      Func<T, U, V> resultSelector) =>
        source.Zip(second, resultSelector).ToZipList();
}

Suppose further an extension method that converts a sequence into a zip-list:

static partial class ZipList
{
    public static ZipList<T> ToZipList<T>(this IEnumerable<T> source) =>
        new ZipList<T>(source);
}

Now you can write:

from x in Enumerable.Range(1, 2).ToZipList()
join y in Enumerable.Range(1, 3) on 1 equals 1
join z in Enumerable.Range(1, 4) on 1 equals 1
select new { x, y, z }

It evaluates to:

{ x = 1, y = 1, z = 1 }
{ x = 2, y = 2, z = 2 }

which is to be expected because Zip stops at the shortest sequence.

Of course, the annoying part of on 1 equals 1 remains and that's what I was arguing for in my initial comment; that if we remove the requirement then Zip is just a few keystrokes away.

If you want to start with a zip-list in the from clause when you don't have a sequence to convert then you just need to introduce Return:

partial class ZipList
{
    public static ZipList<T> Return<T>(this T item)
    {
        return _(item).ToZipList();
        IEnumerable<T> _(T item) { for (;;) yield return item; }
    }
}

If you want, you can even hack a bogus from and just join (or zip) all the way:

from _ in ZipList.Return(0)
join x in Enumerable.Range(1, 2) on 1 equals 1
join y in Enumerable.Range(1, 3) on 1 equals 1
join z in Enumerable.Range(1, 4) on 1 equals 1
select new { x, y, z }

I am not advocating this; it's just for sake of illustration. Anyway, the cool thing with these joins is that you can zip to any product without overloading on arity.

Hope this makes better sense.

[svick]

@atifaziz That does clarify what you meant. Though I think adding syntax for zip still makes more sense than supporting cross-joins:

1. For sequences, the approach using ZipList is a clever hack, but I think it's also terrible design. zip is very different from join, so zip shouldn't use the join keyword.
2. For sequences, I don't see much value in supporting cross-join, when you can use from/SelectMany.
3. For other computations, it seems you don't care whether you have cross-join or zip, so zip would be sufficient.

[atifaziz]

Though I think adding syntax for zip still makes more sense than supporting cross-joins:

I find that to be odd reasoning for something that exists in the language today and where one half of it can be made optional (subtracting versus adding). It's like saying that cross-joins don't make sense when we already have join. Just to be clear, I am not saying cross-join should be the only way to go about doing zip but that there's a perfectly viable solution right under our noses. That's separate from arguing for a syntax for zip. Perhaps I am hijacking this issue and ought to open a new one?

1. For sequences, the approach using ZipList is a clever hack, but I think it's also terrible design. zip is very different from join, so zip shouldn't use the join keyword.

I am not a Haskell expert (not even a beginner) but I believe that's the approach taken there and I hope that gives it some merit. There is exactly a wrapper type for lists called ZipList that gives <*> (applicative, via liftA2) a reasonably alternative implementation (with the default being a cross-application):

-- | Lists, but with an 'Applicative' functor based on zipping.
newtype ZipList a = ZipList { getZipList :: [a] }

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    liftA2 f (ZipList xs) (ZipList ys) = ZipList (zipWith f xs ys)

The difference is that newtype is understood by Haskell to avoid an allocation for the wrapper (assuming it's more for compile-time & static resolution) when compared to emulating the same in C# (as I did above). However, when you go with LINQ, you make a trade-off: accept modest allocations for large gains in expressivity so a wrapper allocation would be playing fair.

2. For sequences, I don't see much value in supporting cross-join, when you can use from/SelectMany.

Except to see the LINQ query syntax only through the eyes of sequences would be short-sighted. It gives you a common vocabulary across computational expressions. The dependence created with from…from…from… and independence you gain with from…join…join… can change your execution model (think PLINQ) that otherwise only provides an artificial limitation and lost opportunities for optimisations.

3. For other computations, it seems you don't care whether you have cross-join or zip, so zip would be sufficient.

It's not that I don't care. It's that you'll find it's one and the same for other computations that produce one result. The exception here is rather sequences.

[orthoxerox]

@atifaziz I asked for zip support because I actually want zip support for sequences. Your suggestion changes the semantic for sequences from pairwise combination to Cartesian product.

[CharlesSchimmel]

I'm sad to see this still hasn't gotten any traction, I'd love to see a liftA2 or zip-shaped operator in LINQ. Enabling what is essentially ApplicativeDo syntax to C# would be tremendous in supporting the growing number of devs that use functional techniques in C#.

[CyrusNajmabadi]

I'm sad to see this still hasn't gotten any traction

There seems to be almost no community interest in this.

in supporting the growing number of devs that use functional techniques in C#.

It's possible this group is much smaller than some think it is. I definitely want to support small groups interested in fascinating parts of computing. But ultimately we want to invest our efforts such that they will benefit the majority as much as possible.