Should Iterators have `peek` as well as `next`?

[apblack]

By analogy with Java, our iterators have a next method than both modifies the object and returns a result. (Isn't there a pattern that says that modifiers and observers should be separate? Or is that just in distributed systems?)

The lack of an observer method that answers the next value in the Iterator without modifying it makes some code much harder to write. For example, here is a merge method, written with such an observer method, here named peek.

method merge (cs) and (ds) -> List {
    def cIter = cs.iterator
    def dIter = ds.iterator
    def result = list.empty
    while {cIter.hasNext && dIter.hasNext} do {
        if (cIter.peek <= dIter.peek) then { 
            result.addLast(cIter.next) 
        } else {
            result.addLast(dIter.next)
        }
    }
    while {cIter.hasNext} do { result.addLast(cIter.next) }
    while {dIter.hasNext} do { result.addLast(dIter.next) }
    result
}

Here it is without peek:

method merge (cs) and (ds) -> List {
    def cIter = cs.iterator
    def dIter = ds.iterator
    def result = list.empty
    if (cIter.hasNext.not) then { return result.addAll(ds) }
    if (dIter.hasNext.not) then { return result.addAll(cs) }
    var c := cIter.next
    var d := dIter.next
    while {cIter.hasNext && dIter.hasNext} do {
        if (c <= d) then { 
            result.addLast(c) 
            c := cIter.next
        } else {
            result.addLast(d)
            d := dIter.next
        }
    }
    if (c <= d) then {
        result.addLast(c, d)
    } else {
        result.addLast(d, c)
    }
    while {cIter.hasNext} do { result.addLast(cIter.next) }
    while {dIter.hasNext} do { result.addLast(dIter.next) }
    result
}

Is the gain sufficient to put peek into the Iterator type? If so, what should we call it?

[KimBruce]

I think it does make sense to add it, but I’d make it in a subtype rather than add the method to Iterator. The reason is that there may be some implementations (lazy lists?) where a ”peek” style operation would complicate the implementation more than it would help applications. I don’t have a great idea for the name, maybe “PeekableIterator”, but surely somebody can come up with something better.

As for names, I’m not sure. Current seemed promising, but there are two disadvantages: 1) probably several implementations are already using current in the implementation — maybe in a compatible way, maybe not. 2) Unfortunately, current and next would both return the same element — though have a different side effect — making everyone crazy. That leaves me with get and peek as the two options. Of those two, peek works best with things like lazy I/O, but I’m not sure otherwise.

I also was trained early on that value-returning functions/methods should not have (visible) side effects. Thus I’d be tempted to teach it so peek is always used to return the value, and next is used to move along (though it also returns a value that falls on the floor).

I think this is one of those issues where my view of what to do depends on how much I value compatibility. De novo, next has no side effects and use peek to get values, but for compatibility don’t use peek and use next with the side effect. Sigh!

[apblack]

The problem with putting peek in a subtype, and not in Iterator itself, is that, if one can't be sure that it's always available, one can't write methods that depend on it, which is the whole point of having it.

I can't see that implementing peek can ever be problematic. For lazy streams, the existence of hasNext already forces the implementor to generate the next element and cache it.

[zmthy]

C# only has non-modifying access to the current element of an enumerator. The MoveNext method returns a boolean indicating whether there are more elements to consider: https://msdn.microsoft.com/en-us/library/system.collections.ienumerator(v=vs.110).aspx

Rust just has a next method, which returns an optional value, so you can just call that until it returns None: http://doc.rust-lang.org/std/iter/trait.Iterator.html

Neither of those interfaces can raise exceptions for moving the iterator beyond the end of the underlying collection.

[apblack]

Thanks, Tim, for those links. C# also has Current for what what we have tentatively called peek. In C#, current is initially undefined; a request of MoveNext is required before current will answer the first element of the enumeration.

While, as you say, attempting to MoveNext on an exhausted iterator does not raise an exception, requesting Current on that same iterator does raise an exception. This makes sense since MoveNext is also playing the role of hasNext in Grace's interface. By combining the action of advancing the iterator with that of testing whether advance is possible, C# manages to use just two requests on the iterator to move through the collection, as do Grace and Java. But it fails to separate observers from modifiers.

Another possibility is to Gracify the Rust interface:

    method withNextDo(nextAction:Block1) ifNone(exhaustedAction:Block0)
    // if this iterator contains another element, apply nextAction to it.  Otherwise, apply
    // exhaustedAction. Returns the result of whichever action is applied.

But that won't help to simplify the motivating example.

[kjx]

On 17/11/2015, at 11:48am, Andrew Black notifications@github.com wro

Is the gain sufficient to put peek into the Iterator type. If so, what should we call it?

I think you can always write an adapter that turns an iterator in to a peekable interator.

the real question is how rich should our core interfaces be?
And interators - or streams - are one of our core interfaces. It would be good to look at e.g. the Java Stream designs, and the new Java 8 iterators to see what we can crib before deciding.

Given that C#, Python, and now JS are getting support for control flow inversion for iterators, I do wonder if we should at least see what we can do there to make writing iterators easier.

We can’t do everything they do with yeild without committing to callCC but someting like

begin {init code} for (collection) iterate { x -> }

which would run the init code block, get an iterator over the collection, and return a new iterator based on the iterate block (kind of like a map)

we might even be able to do something like

iterator { yield -> do stuff…
yield.apply(x) }

but i think that the iterator block would start again from the top each time, rather than carrying on from directly after the yeild as in python or C#

James

[apblack]

James, you have done it again!

I opened this issue by asking a small, simple question about one particular interface, based on a real problem encountered writing real code. I was hoping for an answer.

You managed to generalize it to a huge question requiring a large amount of research and debate:

the real question is how rich should our core interfaces be?

and

Given that C#, Python, and now JS are getting support for control flow inversion for iterators, I do wonder if we should at least see what we can do there to make writing iterators easier. We can’t do everything they do with yield without committing to callCC …

We don't have the resources to thoroughly investigate these possibilities, so the original, simple question remains unanswered.