Combining sequences

These operations take two or more sequences and produce one. They differ in how they pick the next element: Merge by comparing, Interleave by taking turns, ZipLongest by position, Flatten by exhausting one sequence before starting the next. Intersperse is the odd one out: it combines a sequence with a single element.

All of them are lazy and enumerate each input at most once.

Merge

Merges two or more sorted sequences into one sorted sequence, like the merge step of a merge sort.

IEnumerable<TSource> Merge<TSource>(this IEnumerable<TSource> source1, IEnumerable<TSource> source2, Option<IComparer<TSource>> comparer = default)
IEnumerable<TSource> Merge<TSource>(this IEnumerable<TSource> source1, IEnumerable<TSource> source2, IEnumerable<TSource> source3, Option<IComparer<TSource>> comparer = default)
IEnumerable<TSource> Merge<TSource>(this IEnumerable<TSource> source1, IEnumerable<TSource> source2, IEnumerable<TSource> source3, IEnumerable<TSource> source4, Option<IComparer<TSource>> comparer = default)
IEnumerable<TSource> Merge<TSource>(this IEnumerable<IEnumerable<TSource>> sources, Option<IComparer<TSource>> comparer = default)

A marble diagram showing the Merge operation

The inputs must already be sorted by the same comparer, which defaults to Comparer<T>.Default. Merge does not check this; on unsorted input it still produces all elements, but not in order. At each step it looks at the current head of every input and yields the smallest. When two heads compare equal, the one from the earlier input wins, so the merge is stable.

Merge is lazy and streams: it holds one element per input, never materializes anything, and works on infinite inputs. This is what distinguishes it from Concat(...).OrderBy(...), which has to read everything first.

Example

var odds = Sequence.Return(1, 3, 5, 9);
var evens = Sequence.Return(2, 4, 6);

odds.Merge(evens);
// [1, 2, 3, 4, 5, 6, 9]

var byNewest = Comparer<LogEntry>.Create((a, b) => b.Timestamp.CompareTo(a.Timestamp));
var combinedLog = Sequence.Return(webLog, dbLog, workerLog).Merge(byNewest);

Interleave

Takes one element from each sequence in turn, round-robin, until all sequences are exhausted.

IEnumerable<TSource> Interleave<TSource>(this IEnumerable<TSource> source, params IEnumerable<TSource>[] otherSources)
IEnumerable<TSource> Interleave<TSource>(this IEnumerable<IEnumerable<TSource>> source)

A marble diagram showing the Interleave operation

Sequences of different lengths are fine: a sequence that runs out simply drops out of the rotation and the remaining ones continue. The result therefore contains every element of every input. Interleave is lazy and advances each input only when it is that input's turn.

For two sequences of the same length, Interleave is Zip followed by flattening the pairs.

Example

var numbers = Sequence.Return(1, 2, 3, 4);
var letters = Sequence.Return("a", "b");

numbers.Select(n => n.ToString()).Interleave(letters);
// ["1", "a", "2", "b", "3", "4"]

Alternating rows from several sources in a fair way, for example to mix results of different providers:

var mixed = Sequence.Return(newsFeed, blogFeed, podcastFeed).Interleave().Take(30);

Intersperse

Inserts a separator element between every two elements of a sequence.

IEnumerable<TSource> Intersperse<TSource>(this IEnumerable<TSource> source, TSource element)

A marble diagram showing the Intersperse operation

The separator goes only between elements: an empty sequence stays empty, and a single element is returned without a separator. A sequence of n elements becomes one of 2n - 1. The operation is lazy.

This is the sequence counterpart of string.Join: JoinToString(", ") is Intersperse(", ") followed by concatenation. Use Intersperse when the result should stay a sequence, for example to put spacer items into a list of UI elements.

Example

Sequence.Return(9, 7, 3).Intersperse(0);
// [9, 0, 7, 0, 3]

Sequence.Return("a").Intersperse("-");
// ["a"]

var layout = widgets.Intersperse(new Spacer());

ZipLongest

Pairs up two sequences element by element, like Zip, but keeps going until the longer one is exhausted.

IEnumerable<EitherOrBoth<TLeft, TRight>> ZipLongest<TLeft, TRight>(this IEnumerable<TLeft> left, IEnumerable<TRight> right)
IEnumerable<TResult> ZipLongest<TLeft, TRight, TResult>(this IEnumerable<TLeft> left, IEnumerable<TRight> right, Func<EitherOrBoth<TLeft, TRight>, TResult> resultSelector)

A marble diagram showing the ZipLongest operation

Zip stops at the end of the shorter sequence and silently drops the rest of the longer one. ZipLongest instead produces an EitherOrBoth<L, R> for every position: Both(left, right) while both sequences have elements, then Left(left) or Right(right) for the remaining elements of whichever is longer. There is no default value to invent, so nothing is invented.

EitherOrBoth is handled with Match or Switch, which take three functions. The result selector overload is the shorter way to write ZipLongest(right).Select(selector).

Example

var expected = Sequence.Return("a", "b", "c");
var actual = Sequence.Return("a", "x");

expected.ZipLongest(actual, pair => pair.Match(
    both: (e, a) => e == a ? $"{e} ok" : $"{e} != {a}",
    left: e => $"{e} missing",
    right: a => $"{a} unexpected"));
// ["a ok", "b != x", "c missing"]

Flatten

Concatenates a sequence of sequences into one sequence.

IEnumerable<T> Flatten<T>(this IEnumerable<IEnumerable<T>> enumerable)

A marble diagram showing the Flatten operation

Flatten is SelectMany(Identity): the inner sequences are enumerated one after the other, in order, lazily. It is the inverse of Chunk, and exists because SelectMany(x => x) says much less than its name.

The same operation on a known number of sequences is Sequence.Concat(first, second, third), which is the variadic form of LINQ's Concat.

Example

var pages = Sequence.Return(
    Sequence.Return(1, 2, 3),
    Sequence.Return(4, 5),
    Enumerable.Empty<int>(),
    Sequence.Return(6));

pages.Flatten();
// [1, 2, 3, 4, 5, 6]

numbers.Chunk(3).Flatten().SequenceEqual(numbers);
// true

CartesianProduct

The Cartesian product of two sequences is the sequence of all pairs with the first element from the first sequence and the second from the second. Funcky does not ship a method for it, because LINQ already has one under a different name, and this section exists so that you find it.

Recipe

SelectMany with a selector that ignores its argument is the Cartesian product:

// As tuples
var pairs = first.SelectMany(_ => second, ValueTuple.Create);

// With a selector
var combined = first.SelectMany(_ => second, (a, b) => ...);

// In query syntax, which reads most naturally
var combined =
    from a in first
    from b in second
    select ...;

The second sequence is enumerated once per element of the first, so if it is expensive to produce, materialize it before.

Example

Every playing card is a suit combined with a rank:

var suits = Sequence.Return("♠", "♣", "♥", "♦");
var ranks = Sequence.Return("2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K", "A");

var deck =
    from suit in suits
    from rank in ranks
    select $"{rank}{suit}";
// ["2♠", "3♠", …, "A♦"], 52 cards

Funcky User Guide