Algorithms on iterators (consuming vs buffering)

[dabrahams]

This is probably just a tangent in a larger conversation we're having about iteration protocols, by which I mean we shouldn't get too far into the larger topic in this discussion.

Supposing you have

trait Equatable {
  fun equals(_ x: Self) -> Bool
}

trait Hashable: Equatable {
  fun hash(into: inout Hasher)
}

trait Iterator {
  type Element: Movable
  fun next() inout -> Optional<Element>
}

We could write an algorithm for Iterator that tells whether two iterators have equal elements:

extension Iterator {

  fun elements_equal<X: Iterator>(those_in s: inout X) inout -> Bool 
    where X.Element == Self.element
  {
    while let x = self.next() {
      if let y = s.next() {
        if x != y { return false }
      }
      else {
        return false
      }
    }
    return s.next() == nil
  }

}

The semantics of where it leaves self and other are a bit hard to describe:

Comparison	Remaining Sequences
(1, 2, 3) == (1, 2, 3)	(x), (x)
(1, 9, 3) == (1, 2, 3)	(3), (3)
(1, 2, 3) == (1, 9, 3)	(3), (3)
(1, 2) == (1, 2, 3)	(x), ()
(1, 2, 3) == (1, 2)	(), (x)
(1, 2) == (1, 2, 3, 4)	(x), (4)
(1, 2, 3, 4) == (1, 2)	(4), (x)
() == (1, 2)	(x), (2)
(1, 2) == ()	(2), (x)

[(x) means not only is the iterator exhausted, but it has returned nil from next(). That would only be significant if don't require iterators to keep returning nil once exhausted. I think we should require that, especially looking at these results.]

At least it looks symmetrical!

The rule seems to be,

• if there is a first mismatched pair of elements, both iterators are consumed through those elements.
• Otherwise, if one iterator's sequence is shorter at N elements, it is entirely consumed and N+1 elements of the other iterator are consumed.
• Otherwise, both iterators are entirely consumed.

I don't know whether that semantics is useful or not. Certainly if not, such an algorithm should be made to sink both iterators in question. One alternative I don't love is to simplify the semantics by leaving the middle case unspecified, and only giving guarantees in the other two cases.

We could have a kind of iterator that could buffer its last element, so we could check for exhaustion without consuming an element. That would allow us to create a much more useful semantics, stopping the iterators in a place where the first mismatch could be examined, and always consuming the same number of elements from both iterators. However, IIRC we discussed schemes like this and decided that once you require buffering, you may as well require multipass, and it wasn't worth complicating the design space by separating the two aspects. Please correct me if I'm wrong.

[kyouko-taiga]

It may still be useful to have that kind of iterator with the buffer separate from the one that simply presents a collection. One issue to consider is that if you give me a T: Iterator I can't really create T: Collection because pulling elements from the iterator requires mutation. So really we'd need a wrapper that can hide this mutation, which may be a questionable thing to add in a standard library.

At the same time, I am partial to the simpler approach of saying that elements_equal sinks its arguments. That's an idea we have floated for other algorithms in this category too.

Perhaps one way to refine our opinion could be to think of how we want to use these iterators. It seems to me that the most common use case will be consuming iteration, in which case any algorithm that may exhaust its input could sink it.