New type: Iterator - a safe IEnumerator

[louthy]

Language-ext gained Iterable a few months back, which is a functional wrapper for IEnumerable. We now have Iterator, which is a more functional wrapper for IEnumerator.

IEnumerator is particularly problematic due to its mutable nature. It makes it impossible to share or leverage safely within other immutable types.

For any type where you could previously call GetEnumerator(), it is now possible to call GetIterator().

Iterator is pattern-matchable, so you can use the standard FP sequence processing technique:

public static A Sum<A>(this Iterator<A> self) where A : INumber<A> =>
    self switch
    {
        Iterator<A>.Nil                 => A.Zero,
        Iterator<A>.Cons(var x, var xs) => x + xs.Sum()
    };

Or, bog standard imperative processing:

for(var iter = Naturals.GetIterator(); !iter.IsEmpty; iter = iter.Tail)
{
    Console.WriteLine(iter.Head);
}

You need to be a little careful when processing large lists or infinite streams.. Iterator<A> uses Iterator<A>.Cons and Iterator<A>.Nil types to describe a linked-list of values. That linked-list requires an allocated object per item. That is not really a problem for most of us that want correctness over outright performance, it is a small overhead. But, the other side-effect of this is that if you hold a reference to the head item of a sequence and you're processing an infinite sequence, then those temporary objects won't be freed by the GC. Causing a space leak.

This will cause a space-leak:

var first = Naturals.GetIterator();
for(var iter = first; !iter.IsEmpty; iter = iter.Tail)
{
    Console.WriteLine(iter.Head);
}

first references the first Iterator<A>.Cons and every subsequent item via the Tail.

This (below) is OK because the iter reference keeps being overwritten, which means nothing is holding on the Head item in the sequence:

for(var iter = Naturals.GetIterator(); !iter.IsEmpty; iter = iter.Tail)
{
    Console.WriteLine(iter.Head);
}

This type is probably more useful for me when implementing the various core types of language-ext, but I can't be the only person who's struggled with IEnumerator and its horrendous design.

A good example of where I am personally already seeing the benefits is IO<A>.RetryUntil.

This is the original version:

public IO<A> RepeatUntil(
    Schedule schedule,
    Func<A, bool> predicate) =>
    LiftAsync(async env =>
              {
                  if (env.Token.IsCancellationRequested) throw new TaskCanceledException();
                  var token = env.Token;
                  var lenv  = env.LocalResources;
                  try
                  {
                      var result = await RunAsync(lenv);

                      // free any resources acquired during a repeat
                      await lenv.Resources.ReleaseAll().RunAsync(env);

                      if (predicate(result)) return result;

                      foreach (var delay in schedule.Run())
                      {
                          await Task.Delay((TimeSpan)delay, token);
                          result = await RunAsync(lenv);

                          // free any resources acquired during a repeat
                          await lenv.Resources.ReleaseAll().RunAsync(env);

                          if (predicate(result)) return result;
                      }

                      return result;
                  }
                  finally
                  {
                      // free any resources acquired during a repeat
                      await lenv.Resources.ReleaseAll().RunAsync(env);
                  }
              });      
    

Notice the foreach in there and the manual running of the item to retry with RunAsync. This has to go all imperative because there previously was no way to safely get the IEnumerator of Schedule.Run() and pass it around.

This is what RetryUntil looks like now:

public IO<A> RetryUntil(Schedule schedule, Func<Error, bool> predicate)
{
    return go(schedule.PrependZero.Run().GetIterator(), Errors.None);

    IO<A> go(Iterator<Duration> iter, Error error) =>
        iter switch
        {
            Iterator<Duration>.Nil =>
                IO.fail<A>(error),

            Iterator<Duration>.Cons(var head, var tail) =>
                IO.yieldFor(head)
                  .Bind(_ => BracketFail()
                               .Catch(e => predicate(e)
                                               ? IO.fail<A>(e)
                                               : go(tail, e)))
        };
}

Entirely functional, no imperative anything, and even (potentially) infinitely recursive depending on the Schedule. There's also no manual running of the IO monad with RunAsync, which means we benefit from all of the DSL work on optimising away the async/await machinery.

Future:

• Potentially use Iterator in StreamT
• Potentially use Iterator in Pipes
• Potentially create IteratorT (although this would likely just be StreamT, so maybe a renaming)

---

This discussion was created from the release New type: Iterator - a safe IEnumerator.