Nested Iterators, part 2

In part 1, we discussed the simple approach to making a nested iterator.  However, we fell short of a completely lazy nested iterator.

In simple cases, we can make an separate iterator method for the subsequence:

IEnumerable<IEnumerable<int>> FullyLazy() {
    for(int i = 0; i < 10; i++) 
        yield return Inner(i);
}
IEnumerable<int> Inner(int i) {
    for(int j = 0; j < 10; j++)
        yield return i * 10 + j;
}
Note that this is actually smaller than the single-method implementation!

This seems to work very well; the inner iterator code for a particular subsequence will not execute at all unless that subsequence is actually enumerated.

However, this approach falls short in practice.  To see why, consider a real-world example.
Here is a fully lazy implementation of a Partition method, which converts a sequence into a 2D “jagged IEnumerable” where each subsequence (partition) contains n elements.

class Ref<T> { 
    public Ref(T value) { Value = value; } 
    public T Value { get; set; } 
}

public static IEnumerable<IEnumerable<T>> Partition<T>
              (this IEnumerable<T> sequence, int size) {
    using(var enumerator = sequence.GetEnumerator()) {
        var isFinished = new Ref<bool>(false);
        while(!isFinished.Value) {
            yield return PartitionInner(
                 enumerator, size, isFinished
            );
        }
    }
}
static IEnumerable<T> PartitionInner<T>
      (IEnumerator<T> enumerator, int size, Ref<bool> isFinished) {
    while(size --> 0) {
          isFinished.Value = !enumerator.MoveNext();
        if (isFinished.Value) yield break;
        yield return enumerator.Current;
    }
}

This method is complicated by the need to communicate back from the inner iterator to the outer one.  Since iterators cannot have ref parameters, I need to make a “box” class that holds a reference to an int.  This allows the outer iterator to find out when the sequence finishes.

In addition, this implementation has a subtle bug: If the last partition is full, it will return an extra, empty, partition after it.
Fixing this issue would require that the outer method call MoveNext() before each call to the inner method.  This makes the code even more complicated; I won’t list it here (unless people really want me to)

This design has a more fundamental problem: The behavior of the outer method is determined by the inner ones.  It will only work if each inner IEnumerable<T> is enumerated exactly once, before the next MoveNext() call to the outer iterator.  If, for example, you iterate each inner iterator twice, it will behave unexpectedly:

Enumerable.Range(1, 8)
          .Partition(3)
          .Select(p => String.Join(", ", p.Concat(p)));
This code is intended to create strings that contain each partition twice.  It is supposed to return
1, 2, 3, 1, 2, 3
4, 5, 6, 4, 5, 6
7, 8, 7, 8

However, it actually creates the strings

1, 2, 3, 4, 5, 6
7, 8

Enumerating the inner iterator a second time will end up consuming extra items from the original sequence.

Thus, in order to produce enumerables that behave correctly, the inner enumerator needs to cache its items; it is impossible to make a fully lazy Partition method.

It gets worse.  In order to allow callers to write thingy.Partition(5).Skip(2), (which should skip the first two partitions) the outer enumerator needs to cache all items, because it cannot assume that the inner iterators will be called at all. 

Thus, the laziest possible Partition method must use the original approach:

public static IEnumerable<IEnumerable<T>> PartitionCorrect<T>
              (this IEnumerable<T> sequence, int size) {
    List<T> partition = new List<T>();
    foreach(var item in sequence) {
        partition.Add(item);
        if (partition.Count == size) {
            yield return partition;
            partition = new List<T>();
        }
    }
    if (partition.Count > 0)
        yield return partition;
}

It would be possible to write a slightly lazier version that combines these two approaches and passes a List<T> to the inner iterator, which would return whatever is in the list, then enumerate if necessary to fill the list. However, I’m too lazy to do it.  (unless people really want me to)

9 comments:

They give a lot to think about. Kelly

You can read information from https://justdomyhomework.com/blog/finish-homework-fast before doing homework. It will help you not to waste your time

Hi there. When I need help to have good grades I use this site https://bestwritingservice.com/essays/Technology/Pros-and-Cons-of-Information-Technology.html. I have used it many times. He helped me find what I was looking for. Thank you.

I have not met such an interesting blog for a long time. You did a great job. Have you ever read about plagiarism facts? I read and was satisfied. It works.

Heya i’m for the first time here. I found this board and I find It truly useful
& it helped me out a lot. I hope to give something back and
help others like you aided me.
토토
온라인경마

Iterator is an interface provided by collection framework to traverse a collection and for a sequential access of items in the collection.

// Iterating over collection 'c' using iterator
for (Iterator i = c.iterator(); i.hasNext(); )
System.out.println(i.next());
In this loop, we can’t modify collection, it will throw a ConcurrentModificationException on the other hand with iterator we can modify collection.

Modifying a collection simply means removing an element or changing content of an item stored in the collection. This occurs because for-each loop implicitly creates an iterator but it is not exposed to the user thus we can’t modify the items in the collections.

- Samantha
Contact here

Slaks Blog" refers to a blog platform or website featuring content created or curated by an individual or group known as Slaks. The specific content and themes covered on Slaks Blog may vary, ranging from personal experiences and opinions to topics of interest or expertise. Readers can explore and engage with the blog to gain insights or perspectives shared by Slaks.
virginia uncontested divorce
virginia personal injury settlements
uncontested divorce in va
uncontested divorce in virginia

pg slot99th โบนัส แจกฟรี เป็นแพลตฟอร์มเกมสล็อตออนไลน์ที่ได้รับความนิยมในประเทศไทย โดยเน้นให้บริการเกม สล็อต ที่มีคุณภาพและหลากหลายตั้งแต่เกมสล็อตดั้งเดิมไปจนถึงเกมสล็อตที่เรียกว่าสุดล้ำ

Post a Comment