Two approaches to Cartesian product of a collection of lists using LINQ

Question

I need to create the Cartesian product of a collection of lists. For example I have:

{ {4,3,7}, {1,2,9}, {5,8} }

And I need: {4,1,5}, {4,1,8}, {3,1,5}, {3,1,8}, ... , {7,9,8}

So far I have learned that you can do so using something like this:

var lists = new List<List<int>>
{ 
    new List<int> { 4, 3, 7},
    new List<int> { 1, 2, 9},
    new List<int> { 5, 8},
};

IEnumerable<IEnumerable<int>> empty = new[] { Enumerable.Empty<int>() };
var agg = lists.Aggregate(
    empty,
    (acc, next) 
=>  
    (from ac in acc
    from n in next
    select ac.Concat(new[] {n})));

However initially when I was implementing this, I implemented it like so:

var lists = new List<List<int>>
{ 
    new List<int> { 4, 3, 7},
    new List<int> { 1, 2, 9},
    new List<int> { 5, 8},
};

var agg = lists.Aggregate(
    new List<List<int>>() {new List<int> {}},
    (acc, next) 
=>  
    (from ac in acc
    from n in next
    select ac.Add(n)).ToList());

This specific implementation fails to compile with this error:

An expression of type 'System.Collections.Generic.List' is not allowed in a subsequent from clause in a query expression with source type 'System.Collections.Generic.List>'. Type inference failed in the call to 'SelectMany'.

I'm a little confused by this error message. I can't see why a List is not allowed in that location?

Answer 1

The first part of the error message is somewhat misleading. The following will compile and work just fine:

var agg = lists.Aggregate(
    new List<List<int>>(),
    (acc, next) 
=>  
    (from ac in acc
    from n in next
    // select ac.Add(n)).ToList());
    select ac.Concat(new[] {n}).ToList()).ToList());

The real problem is with select ac.Add(n). A select clause must return a value (in this case a List<int>), but your call to List<T>.Add modifies the original list and returns void instead.

Under the hood, LINQ tries to transform this LINQ expression into (among other things) a call to Enumerable.SelectMany. One of the arguments the compiler passes is a generated lambda expression that returns ac.Add(n) (i.e. void). The compiler tries to infer the type of the generated lambda based on the available overloads of SelectMany, but there is no compatible overload and so the type of the lambda can't be determined. Hence the error message "Type inference failed in the call to 'SelectMany'.".

Like Add, most List<T> methods aren't generally suitable for functional programming with LINQ, which is why the preferred solution relies only on IEnumerable<T> and its LINQ-related extension methods.