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

c#, cartesian-product, generics, linq

Solution

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.

Problem

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?

Original source