Implementing an immutable enumerator

Question

Consider the following possible interface for an immutable generic enumerator:

interface IImmutableEnumerator<T>
{
    (bool Succesful, IImmutableEnumerator<T> NewEnumerator) MoveNext();
    T Current { get; }
}

How would you implement this in a reasonably performant way in c#? I'm a little out of ideas, because the IEnumerator infrastructure in .NET is inherently mutable and I can't see a way around it.

A naive implementation would be to simply create a new enumerator on every MoveNext() handing down a new inner mutable enumerator with current.Skip(1).GetEnumerator() but that is horribly inefficient.

I'm implementing a parser that needs to be able to look ahead; using an immutable enumerator would make things cleaner and easier to follow so I'm curious if there is an easy way to do this that I might be missing.

The input is an IEnumerable<T> and I can't change that. I can always materialize the enumerable with ToList() of course (with an IList in hand, looking ahead is trivial), but the data can be pretty large and I'd like to avoid it, if possible.

Answer 1

This is it:

public class ImmutableEnumerator<T> : IImmutableEnumerator<T>, IDisposable
{
    public static (bool Succesful, IImmutableEnumerator<T> NewEnumerator) Create(IEnumerable<T> source)
    {
        var enumerator = source.GetEnumerator();
        var successful = enumerator.MoveNext();
        return (successful, new ImmutableEnumerator<T>(successful, enumerator));
    }
    private IEnumerator<T> _enumerator;
    private (bool Succesful, IImmutableEnumerator<T> NewEnumerator) _runOnce = (false, null);
    private ImmutableEnumerator(bool successful, IEnumerator<T> enumerator)
    {
        _enumerator = enumerator;
        this.Current = successful ? _enumerator.Current : default(T);
        if (!successful)
        {
            _enumerator.Dispose();
        }
    }
    public (bool Succesful, IImmutableEnumerator<T> NewEnumerator) MoveNext()
    {
        if (_runOnce.NewEnumerator == null)
        {
            var successful = _enumerator.MoveNext();
            _runOnce = (successful, new ImmutableEnumerator<T>(successful, _enumerator));
        }
        return _runOnce;
    }
    public T Current { get; private set; }
    public void Dispose()
    {
        _enumerator.Dispose();
    }
}

My test code succeeds nicely:

var xs = new[] { 1, 2, 3 };

var ie = ImmutableEnumerator<int>.Create(xs);
if (ie.Succesful)
{
    Console.WriteLine(ie.NewEnumerator.Current);
    var ie1 = ie.NewEnumerator.MoveNext();
    if (ie1.Succesful)
    {
        Console.WriteLine(ie1.NewEnumerator.Current);
        var ie2 = ie1.NewEnumerator.MoveNext();
        if (ie2.Succesful)
        {
            Console.WriteLine(ie2.NewEnumerator.Current);
            var ie3 = ie2.NewEnumerator.MoveNext();
            if (ie3.Succesful)
            {
                Console.WriteLine(ie3.NewEnumerator.Current);
                var ie4 = ie3.NewEnumerator.MoveNext();
            }
        }
    }
}

This outputs:

1
2
3

It's immutable and it's efficient.

---

Here's a version using Lazy<(bool, IImmutableEnumerator<T>)> as per a request in the comments:

public class ImmutableEnumerator<T> : IImmutableEnumerator<T>, IDisposable
{
    public static (bool Succesful, IImmutableEnumerator<T> NewEnumerator) Create(IEnumerable<T> source)
    {
        var enumerator = source.GetEnumerator();
        var successful = enumerator.MoveNext();
        return (successful, new ImmutableEnumerator<T>(successful, enumerator));
    }
    private IEnumerator<T> _enumerator;
    private Lazy<(bool, IImmutableEnumerator<T>)> _runOnce;
    private ImmutableEnumerator(bool successful, IEnumerator<T> enumerator)
    {
        _enumerator = enumerator;
        this.Current = successful ? _enumerator.Current : default(T);
        if (!successful)
        {
            _enumerator.Dispose();
        }
        _runOnce = new Lazy<(bool, IImmutableEnumerator<T>)>(() =>
        {
            var s = _enumerator.MoveNext();
            return (s, new ImmutableEnumerator<T>(s, _enumerator));
        });
    }
    public (bool Succesful, IImmutableEnumerator<T> NewEnumerator) MoveNext()
    {
        return _runOnce.Value;
    }
    public T Current { get; private set; }
    public void Dispose()
    {
        _enumerator.Dispose();
    }
}