A sequence is an ordered abstraction whose elements can be processed in a defined order. Sequences can serve as both inputs and outputs: a Cartesian product combines items from input sequences, while mapping transforms each item into a new sequence. section 6.1 section 11.2
When a Cartesian product takes an arbitrary number of sequences:
- Its result is a sequence of sequences, with one output element drawn from each input sequence. section 6.1.2
- Zero input sequences yield one empty sequence; one input sequence yields one-element output sequences. section 6.1.2
- A sequence can also be transformed element by element; the example divides every integer by two to produce a sequence of doubles. section 11.2
Listing 6.5 A LINQ-based implementation of the arbitrary Cartesian product
public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
this IEnumerable<IEnumerable<T>> sequences)
{
IEnumerable<IDeque<T>> result = [Deque<T>.Empty];
foreach (var sequence in sequences)
result = from deque in result
from item in sequence
select deque.PushRight(item);
return result;
}
This implementation builds the product incrementally, extending each partial result with an item from the next sequence. section 6.1.2
