Grouping and windowing

These operations cut one sequence into several smaller ones. They differ in whether the pieces overlap (SlidingWindow, Pairwise), have a fixed size (Chunk) or are delimited by the data itself (AdjacentGroupBy, Split).

Chunk

Cuts a sequence into consecutive pieces of a fixed size. The last piece is smaller if the length is not a multiple of the size.

IEnumerable<IReadOnlyList<TSource>> Chunk<TSource>(this IEnumerable<TSource> source, int size)
IEnumerable<TResult> Chunk<TSource, TResult>(this IEnumerable<TSource> source, int size, Func<IReadOnlyList<TSource>, TResult> resultSelector)

A size of zero or less throws an ArgumentOutOfRangeException immediately, not on enumeration. The chunks are produced lazily, but each chunk is materialized when it is yielded, so you can hold on to a chunk after moving to the next one.

.NET 6 added Enumerable.Chunk to the BCL, returning arrays. On those targets Funcky's own Chunk(size) steps aside and the BCL method is picked; the overload with a result selector remains Funcky's, and is the shorter way to write Chunk(size).Select(selector).

Example

var numbers = Sequence.Return(1, 2, 3, 4, 5, 6, 7);

numbers.Chunk(3);
// [[1, 2, 3], [4, 5, 6], [7]]

var magicSquare = Sequence.Return(4, 9, 2, 3, 5, 7, 8, 1, 6);
magicSquare.Chunk(3, row => row.Sum());
// [15, 15, 15]

SlidingWindow

Produces every window of a fixed width, moving one element at a time. Consecutive windows overlap in all but one element.

IEnumerable<IReadOnlyList<TSource>> SlidingWindow<TSource>(this IEnumerable<TSource> source, int width)

Only full windows are produced. A sequence shorter than the width yields nothing, and a sequence of exactly the width yields one window. A width of zero or less throws an ArgumentOutOfRangeException. The windows are produced lazily and each one is an immutable snapshot.

SlidingWindow(2) is Pairwise with lists instead of tuples; use Pairwise when the width is two.

Example

A moving average over the last three readings:

var readings = Sequence.Return(2, 4, 6, 8, 10);

readings.SlidingWindow(3);
// [[2, 4, 6], [4, 6, 8], [6, 8, 10]]

readings.SlidingWindow(3).Select(window => window.Average());
// [4, 6, 8]

Pairwise

Pairs each element with the one that follows it.

IEnumerable<(TSource Front, TSource Back)> Pairwise<TSource>(this IEnumerable<TSource> source)
IEnumerable<TResult> Pairwise<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TSource, TResult> resultSelector)

A sequence of n elements produces n - 1 pairs; an empty sequence or a single element produces nothing. Every element except the first and the last appears twice, once as Back and once as Front. The operation is lazy and holds on to only one element at a time.

Compare WithPrevious, which keeps every element and makes the predecessor an Option, so the first element is not dropped.

Example

Differences between consecutive measurements:

var temperatures = Sequence.Return(20, 22, 21, 25);

temperatures.Pairwise();
// [(20, 22), (22, 21), (21, 25)]

temperatures.Pairwise((before, after) => after - before);
// [2, -1, 4]

AdjacentGroupBy

Groups runs of consecutive elements that share a key. Where GroupBy collects all elements with the same key from the whole sequence, AdjacentGroupBy starts a new group every time the key changes.

IEnumerable<IGrouping<TKey, TSource>> AdjacentGroupBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
IEnumerable<IGrouping<TKey, TSource>> AdjacentGroupBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)

Like GroupBy, there are further overloads with an element selector, a result selector taking the key and the elements, or both, each with and without a comparer.

The same key can therefore appear in several groups, as a does in the diagram. On a sequence that is sorted by the key, the result is identical to GroupBy, and that is the typical use: the data is already ordered, and AdjacentGroupBy can stream it, yielding each group as soon as the next key is seen, instead of reading everything into a lookup first. Each group is materialized when it is yielded.

This is the same operation as Haskell's groupBy and Python's itertools.groupby.

Example

Collapsing a log into runs of the same severity:

var entries = Sequence.Return(
    new LogEntry(Level.Info, "started"),
    new LogEntry(Level.Info, "listening"),
    new LogEntry(Level.Error, "timeout"),
    new LogEntry(Level.Info, "recovered"));

entries.AdjacentGroupBy(entry => entry.Level, (level, run) => $"{run.Count()} × {level}");
// ["2 × Info", "1 × Error", "1 × Info"]

Splitting a date-ordered sequence into days:

var byDay = events.AdjacentGroupBy(e => DateOnly.FromDateTime(e.Timestamp));

Split

Cuts a sequence at every occurrence of a separator element, like string.Split on a string.

IEnumerable<IReadOnlyList<TSource>> Split<TSource>(this IEnumerable<TSource> source, TSource separator)
IEnumerable<IReadOnlyList<TSource>> Split<TSource>(this IEnumerable<TSource> source, TSource separator, IEqualityComparer<TSource> comparer)
IEnumerable<TResult> Split<TSource, TResult>(this IEnumerable<TSource> source, TSource separator, IEqualityComparer<TSource> comparer, Func<IReadOnlyList<TSource>, TResult> resultSelector)

The separators themselves are not part of the result. The result has exactly one part more than there are separators, exactly like string.Split: two adjacent separators produce an empty part between them, a separator at the very start produces an empty first part, a separator at the very end produces an empty last part, and an empty source produces a single empty part. Joining the parts with the separator therefore always restores the source. The parts are produced lazily and each part is materialized when it is yielded.

Example

Splitting a token stream into statements:

var tokens = Sequence.Return("let", "x", ";", "print", "x", ";", ";", "exit");

tokens.Split(";");
// [["let", "x"], ["print", "x"], [], ["exit"]]

tokens.Split(";", StringComparer.Ordinal, statement => string.Join(' ', statement));
// ["let x", "print x", "", "exit"]

TakeEvery

Keeps the first element and then every n-th element after it.

IEnumerable<TSource> TakeEvery<TSource>(this IEnumerable<TSource> source, int interval)

The elements at indices 0, n, 2n, … are kept. To start at a different offset, Skip first. An interval of zero or less throws an ArgumentOutOfRangeException immediately; TakeEvery(1) is the identity.

Example

Enumerable.Range(1, 10).TakeEvery(3);
// [1, 4, 7, 10]

Enumerable.Range(1, 10).Skip(1).TakeEvery(3);
// [2, 5, 8]

Transpose

Swaps rows and columns of a sequence of sequences, so that the first result row holds the first element of every input row, and so on.

IEnumerable<IReadOnlyList<TSource>> Transpose<TSource>(this IEnumerable<IEnumerable<TSource>> source)

All input rows must have the same length; the behaviour for jagged input is unspecified. The outer sequence is enumerated more than once, so pass a materialized collection rather than a one-shot iterator. An empty outer sequence transposes to an empty sequence.

Example

var matrix = Sequence.Return(
    Sequence.Return(1, 2, 3),
    Sequence.Return(4, 5, 6));

matrix.Transpose();
// [[1, 4], [2, 5], [3, 6]]

Turning a list of records into columns, for example to compute a per-column statistic:

var columns = rows.Select(row => row.Values).Transpose();
var columnMaxima = columns.Select(column => column.MaxOrNone());

PowerSet

Produces every subset of the input, including the empty set and the input itself.

IEnumerable<IEnumerable<TSource>> PowerSet<TSource>(this IEnumerable<TSource> source)

A sequence of n elements has 2ⁿ subsets, so this is only practical for small inputs. The subsets are produced in a fixed order: first all subsets without the last input element, then the same subsets with it added. The whole input is read before the first subset is yielded. Elements are treated by position, not by value, so duplicates in the input produce duplicate subsets.

Example

Sequence.Return("a", "b", "c").PowerSet();
// [[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]

All ways to choose toppings whose total price fits a budget:

var affordable = toppings
    .PowerSet()
    .Where(choice => choice.Sum(t => t.Price) <= budget);