FlatMap maps each element to a sequence, then concatenates those sequences into one. In C#, the equivalent operation is SelectMany. section 11.4
public static IEnumerable<R> SelectMany<T, R>(
this IEnumerable<T> items,
Func<T, IEnumerable<R>> func)
{
foreach(T t in items)
foreach(R r in func(t))
yield return r;
}
public static IEnumerable<R> SelectMany<T, U, R>(
this IEnumerable<T> items,
Func<T, IEnumerable<U>> func,
Func<T, U, R> projection)
{
foreach(T t in items)
foreach(U u in func(t))
yield return projection(t, u);
}
The nested iteration makes the operation explicit: the outer loop visits source elements, while the inner loop emits every element from each resulting sequence. section 11.4
FlatMap supports several closely related ideas:
- It avoids producing a sequence of sequences by concatenating each mapped result immediately. section 11.4
- It corresponds to Bind for the sequence monad; Select corresponds to Map, and Join removes one nesting level. section 11.5
- It can represent filtering by mapping each item to either a one-element sequence or an empty sequence. section 11.4
Backtracking with SelectMany
A general backtracker recursively explores every possible value for an unresolved key. Each recursive call returns a sequence of solutions, and SelectMany concatenates those sequences into one solution stream. The same pattern solves Sudoku after a reducer eliminates impossible candidates. section 8.5.2
The technique is useful when one choice expands into many choices and the results must remain uniformly composable. It also supports readable sequence-based code for manipulating random quantities. section 12.0 section 11.5
