2
\$\begingroup\$

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?

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Are you interested solutions with Linq or smart solutions without Linq are also playing? \$\endgroup\$ Commented Oct 6, 2022 at 18:15
  • 1
    \$\begingroup\$ I've appreciate pure linq solutions better. Thanks for asking. \$\endgroup\$
    – SuperJMN
    Commented Oct 6, 2022 at 22:07

2 Answers 2

2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ If maintaining state outside a linq operator wouldn't Select be a better choice than Aggregate? With a select we could keep deferred execution while Aggregate would consume the entire enumerable and lose the lazy evaluation? \$\endgroup\$ Commented Oct 7, 2022 at 12:39
  • \$\begingroup\$ @CharlesNRice I think it depends on the length of the source sequence and how do you plant to use this method. Don't get me wrong I'm not against lazy evaluation, what I try to say it that there are situations where eager evaluation is also fine. \$\endgroup\$ Commented Oct 7, 2022 at 12:49
  • 1
    \$\begingroup\$ Yes programming is all about situations. For me if returning an IEnumerable by default I would assume it's deferred evaluation. I know even C# breaks that with GroupBy but most do. If eager I would suggest returning arrays or something that indicates the enumerable has been materialized. Just my 2 cents. \$\endgroup\$ Commented Oct 7, 2022 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.