Project sequence to multiple sequences using LINQ (or extension methods)

Question

I'm creating a method that expands a sequence.

This is a sample of how it works:

Input: {1, 2, 3}
Output: {1}, {1, 2}, {1,2,3}

So far, I've been able to solve the algorithm using 2 different approaches:

Approach 1

public IEnumerable<IEnumerable<T>> Expand<T>(IEnumerable<T> sequence)
{
    return sequence.Select((x, i) => sequence.Take(i + 1));
}

Approach 2

Using Aggregate

public IEnumerable<IEnumerable<T>> Expand<T>(IEnumerable<T> sequence)
{
    return sequence.Aggregate(new List<List<T>>(), (a, i) =>
    {
        var prev = a.LastOrDefault() ?? Enumerable.Empty<T>();
        var newList = prev.Concat(new[] { i });
        var sources = newList.ToList();
        return a.Concat(new[] { sources }).ToList();
    });
}

This one is overly complicated. But it works.

Is there a more elegant way to do this using LINQ or its extension methods?

Answer 1

Approach 1 is going to iterate over the IEnumerable multiple times. That's against best practices.

Approach 2 is better but still complex. The biggest downside of Aggerate for this solution is we lose the deferred execution and lazy evaluation of the IEnumerable and have to consume the entire enumerable before emitting a result.

I think just a normal foreach and yield will read better and also not have multiple iterations.

public static IEnumerable<IEnumerable<T>> Expand<T>(this IEnumerable<T> source)
{
    var buffer = new List<T>();
    foreach (var item in source)
    {
        buffer.Add(item);
        var result = new T[buffer.Count];
        buffer.CopyTo(result);
        yield return result;
    }
}

Answer 2

Modified version of Approach #1

• As it was stated by CharlesNRice iterating through an IEnumerable multiple times is not ideal
• If the source does not contain too many items then the following alternative might be a better option

IEnumerable<IEnumerable<T>> Expand<T>(IEnumerable<T> sourceSequence)
{
    var materializedSequence = sourceSequence.ToArray();
    return materializedSequence.Select((x, i) => materializedSequence[0..(i+1)]);
}

• First we materialize the IEnumerable to an array
• Then we do more or less what you did except that we rely on the Range construct

Modified version of Approach #2

• Using the Aggregate function is a good direction
  • Your implementation's complexity (in my humble opinion) is coming from the usage of wide variety of operators (LastOrDefault, Concat, ToList, Empty)
• My alternative solution utilizies only just the Add method

IEnumerable<IEnumerable<T>> Expand<T>(IEnumerable<T> sourceSequence)
{
    List<IEnumerable<T>> results = new ();
    _ = sourceSequence.Aggregate(new List<T>(), (accumulator, item) =>
    {
        accumulator.Add(item);
        results.Add(new List<T>(accumulator));
        return accumulator;
    });
    return results;
}

• First we create a variable for the sequences (results)
• Then we call the Aggregate to
  • append the item to the accumulator which is a simple list
  • append the copy of the simple list (new List<T>(accumulator)) to the results
• We don't care about the result of the Aggregate that's why we can use the discard operator there