Getting head and tail from IEnumerable that can only be iterated once

Question

I have a sequence of elements. The sequence can only be iterated once and can be "infinite".

What is the best way get the head and the tail of such a sequence?

Update: A few clarifications that would have been nice to include in the original question :)

• Head is the first element of the sequence and tail is "the rest". That means the the tail is also "infinite".

• When I say infinite, I mean "very large" and "I wouldn't want to store it all in memory at once". It could also have been actually infinite, like sensor data for example (but it wasn't in my case).

• When I say that it can only be iterated once, I mean that generating the sequence is resource heavy, so I woundn't want to do it again. It could also have been volatile data, again like sensor data, that won't be the same on next read (but it wasn't in my case).

Answer 1

Decomposing IEnumerable<T> into head & tail isn't particularly good for recursive processing (unlike functional lists) because when you use the tail operation recursively, you'll create a number of indirections. However, you can write something like this:

I'm ignoring things like argument checking and exception handling, but it shows the idea...

Tuple<T, IEnumerable<T>> HeadAndTail<T>(IEnumerable<T> source) {
  // Get first element of the 'source' (assuming it is there)
  var en = source.GetEnumerator();
  en.MoveNext();
  // Return first element and Enumerable that iterates over the rest
  return Tuple.Create(en.Current, EnumerateTail(en));
}

// Turn remaining (unconsumed) elements of enumerator into enumerable
IEnumerable<T> EnumerateTail<T>(IEnumerator en) {
  while(en.MoveNext()) yield return en.Current; 
}

The HeadAndTail method gets the first element and returns it as the first element of a tuple. The second element of a tuple is IEnumerable<T> that's generated from the remaining elements (by iterating over the rest of the enumerator that we already created).

Answer 2

Obviously, each call to HeadAndTail should enumerate the sequence again (unless there is some sort of caching used). For example, consider the following:

var a = HeadAndTail(sequence);
Console.WriteLine(HeadAndTail(a.Tail).Tail);
//Element #2; enumerator is at least at #2 now.

var b = HeadAndTail(sequence);
Console.WriteLine(b.Tail);
//Element #1; there is no way to get #1 unless we enumerate the sequence again.

For the same reason, HeadAndTail could not be implemented as separate Head and Tail methods (unless you want even the first call to Tail to enumerate the sequence again even if it was already enumerated by a call to Head).

Additionally, HeadAndTail should not return an instance of IEnumerable (as it could be enumerated multiple times).

This leaves us with the only option: HeadAndTail should return IEnumerator, and, to make things more obvious, it should accept IEnumerator as well (we're just moving an invocation of GetEnumerator from inside the HeadAndTail to the outside, to emphasize it is of one-time use only).

Now that we have worked out the requirements, the implementation is pretty straightforward:

class HeadAndTail<T> {
    public readonly T Head;
    public readonly IEnumerator<T> Tail;

    public HeadAndTail(T head, IEnumerator<T> tail) {
        Head = head;
        Tail = tail;
    }
}

static class IEnumeratorExtensions {
    public static HeadAndTail<T> HeadAndTail<T>(this IEnumerator<T> enumerator) {
        if (!enumerator.MoveNext()) return null;
        return new HeadAndTail<T>(enumerator.Current, enumerator);
    }
}

And now it can be used like this:

Console.WriteLine(sequence.GetEnumerator().HeadAndTail().Tail.HeadAndTail().Head);
//Element #2

Or in recursive functions like this:

TResult FoldR<TSource, TResult>(
    IEnumerator<TSource> sequence,
    TResult seed,
    Func<TSource, TResult, TResult> f
) {
    var headAndTail = sequence.HeadAndTail();
    if (headAndTail == null) return seed;
    return f(headAndTail.Head, FoldR(headAndTail.Tail, seed, f));
}

int Sum(IEnumerator<int> sequence) {
    return FoldR(sequence, 0, (x, y) => x+y);
}

var array = Enumerable.Range(1, 5);
Console.WriteLine(Sum(array.GetEnumerator())); //1+(2+(3+(4+(5+0)))))

Answer 3

While other approaches here suggest using yield return for the tail enumerable, such an approach adds unnecessary nesting overhead. A better approach would be to convert the Enumerator<T> back into something that can be used with foreach:

public struct WrappedEnumerator<T>
{
    T myEnumerator;
    public T GetEnumerator() { return myEnumerator; }
    public WrappedEnumerator(T theEnumerator) { myEnumerator = theEnumerator; }
}
public static class AsForEachHelper
{
    static public WrappedEnumerator<IEnumerator<T>> AsForEach<T>(this IEnumerator<T> theEnumerator) {return new WrappedEnumerator<IEnumerator<T>>(theEnumerator);}

    static public WrappedEnumerator<System.Collections.IEnumerator> AsForEach(this System.Collections.IEnumerator theEnumerator) 
        { return new WrappedEnumerator<System.Collections.IEnumerator>(theEnumerator); }
}

If one used separate WrappedEnumerator structs for the generic IEnumerable<T> and non-generic IEnumerable, one could have them implement IEnumerable<T> and IEnumerable respectively; they wouldn't really obey the IEnumerable<T> contract, though, which specifies that it should be possible to possible to call GetEnumerator() multiple times, with each call returning an independent enumerator.

Another important caveat is that if one uses AsForEach on an IEnumerator<T>, the resulting WrappedEnumerator should be enumerated exactly once. If it is never enumerated, the underlying IEnumerator<T> will never have its Dispose method called.

Applying the above-supplied methods to the problem at hand, it would be easy to call GetEnumerator() on an IEnumerable<T>, read out the first few items, and then use AsForEach() to convert the remainder so it can be used with a ForEach loop (or perhaps, as noted above, to convert it into an implementation of IEnumerable<T>). It's important to note, however, that calling GetEnumerator() creates an obligation to Dispose the resulting IEnumerator<T>, and the class that performs the head/tail split would have no way to do that if nothing ever calls GetEnumerator() on the tail.