Interesting Iterator Trivia - Thought I would share

[jehugaleahsa]

Hello:

Yesterday, I encountered an interesting side-effect of iterators. Even
though the code looked fine, it actually was completely wrong. See if
you can figure out why this code doesn't do as it is expected and how
to fix it:

// Returns indicies of matching items
public static IEnumerable<int> FindAll(IList<T> list, Predicate<T>
predicate)
{
for (int i = 0; i != list.Count; ++i)
{
if (predicate(list))
{
yield return i;
}
}
}

// Removes the items in the IList at the given indicies (if it's not
an T[])
public static void RemoveAt(IList<T> list, IEnumerable<int> indicies)
{
int shift = 0;
foreach (int index in indicies)
{
list.RemoveAt(index - shift);
++shift;
}
}

// Caller
List<int> values = new List<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8,
9 });
IEnumerable<int> indicies = FindAll<int>(values, delegate (int
current) { return i % 2 == 0; });
RemoveAt(values, indicies);


I just forced the RemoveAt method to take the predicate, but there is
a way to fix the caller withouth touching the other methods.

Have fun,
Travis

 

[Jeroen Mostert]

Hello:

Yesterday, I encountered an interesting side-effect of iterators. Even
though the code looked fine, it actually was completely wrong. See if
you can figure out why this code doesn't do as it is expected and how
to fix it:

// Returns indicies of matching items
public static IEnumerable<int> FindAll(IList<T> list, Predicate<T>
predicate)
{
for (int i = 0; i != list.Count; ++i)
{
if (predicate(list))
{
yield return i;
}
}
}

// Removes the items in the IList at the given indicies (if it's not
an T[])
public static void RemoveAt(IList<T> list, IEnumerable<int> indicies)
{
int shift = 0;
foreach (int index in indicies)
{
list.RemoveAt(index - shift);

Bzzzt. Modifying the collection you're iterating through is inherently
unsafe and iterators aren't required to work if you do that. The trick here,
of course, is that it's not clear that "indicies" is iterating through the
same collection. (The plural of "index", by the way, is "indexes" or "indices".)

++shift;
}
}

// Caller
List<int> values = new List<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8,
9 });
IEnumerable<int> indicies = FindAll<int>(values, delegate (int
current) { return i % 2 == 0; });
RemoveAt(values, indicies);


I just forced the RemoveAt method to take the predicate, but there is
a way to fix the caller withouth touching the other methods.

Sure, by forcing it to materialize the indices before removing. Calling
..ToArray() would do it.

Making .RemoveAt() take the predicate and renaming it to .RemoveAll() is a
better solution (you gain really very little by splitting the operations of
obtaining the indices and performing some operation on the elements); so is
making it impossible to call .RemoveAt() incorrectly by making it take an
array of int rather than an IEnumerable<int>. It would be a very common
scenario to apply these methods to the same list, which is exactly how they
can't be used. A little protection is in order.

Yet another approach (if we absolutely want to retain the ability to use
IEnumerable<> in .RemoveAt()) is to custom-code the iterator to keep a
reference to the collection we're iterating through, and make .RemoveAt()
detect when it's being used on the same collection and bail. Of course, this
only works if the client is kind enough to use .FindAll() to obtain the list
of indices, otherwise .RemoveAt() will have no clue.