Iterator.head()/tail() does not follow Traversable contract

[digiovinazzo]

Traversable interface is extended by several other interfaces of collections, one of those is Iterator.
But it behaves differently than the others when using head() and tail() methods, see here below the test that fails for Iterator, but not for all other sequential collections.

class ScratchTest {
    public static void main(String[] args) {
        testTraversable(LinkedHashSet.of(0, 1, 2, 3));
        testTraversable(List.of(0, 1, 2, 3));
        testTraversable(Queue.of(0, 1, 2, 3));
        testTraversable(Array.of(0, 1, 2, 3));
        testTraversable(Vector.of(0, 1, 2, 3));
        testTraversable(Iterator.of(0, 1, 2, 3)); // fails!
    }

    private static void testTraversable(Traversable<Integer> traversable) {
        assertEquals(Integer.valueOf(0), traversable.head());
        traversable = traversable.tail();
        assertEquals(Integer.valueOf(1), traversable.head());
        traversable = traversable.tail();
        assertEquals(Integer.valueOf(2), traversable.head());
        traversable = traversable.tail();
        assertEquals(Integer.valueOf(3), traversable.head());
    }
}

[pivovarit]

That's a great finding - thanks! Definitely a bug.

[sam-chakrabarty]

I can take a look at this if we need a contributor @pivovarit

[xelavopelk]

May be it's not bug. Because all methods of iterator except "hasNext" aren't idempotent:
` * Note: Iterators encapsulate mutable state.

• Caution: Other methods than {@code hasNext} and {@code next} can be called only once (exclusively).
• More specifically, after calling a method it cannot be guaranteed that the next call will succeed.

• `

For example I can fix Iterator to pass test that "class ScratchTest ". But there is another test for size:

    @Test
    public void shouldCorrectForList2() {
        Traversable<Integer> traversableList = List.of(0, 1);
        assertEquals(2,testTraversableSize(traversableList)); //success
        Traversable<Integer> traversableIter = Iterator.of(0, 1);
        assertEquals(2,testTraversableSize(traversableIter)); // fail
    }
    public int testTraversableSize(Traversable<Integer> traversable){
        traversable.size();
        traversable.size();
        return traversable.size();
    }```

[xelavopelk]

the iterator interface does not guarantee that it has an end. it's the second big problem. so some "enadable" functions like "sum" or "size" havn't sense for iterator. Example:

    class InfiniteIterator implements java.util.Iterator<Integer> {
        private final Random rnd = new Random();
        @Override
        public boolean hasNext() { return true; }
        @Override
        public java.lang.Integer next() { return rnd.nextInt();}
    }
    @Test
    public void infinity() {
        InfiniteIterator iter = new InfiniteIterator();
        Traversable<Integer> traversable = Iterator.ofAll(iter);
        int size = traversable.size(); //infinite loop!!!!!!
        //Number sum1 = traversable.sum(); //infinite loop!!!!!!
    }

[chav-n]

For the Iterator object to make sense, the head() method has to mutate the Iterator object with what tail() would return. The example test would succeed if the testTraversable() method did not call the tail() method on the test object if it was of Iterator type.

If the next() method of the Iterator object is the only way to get the "head" of the "Traversable", then the Iterator type cannot be a "true" (100% conforming) Traversable.

[chav-n]

What about a new tag-interface for the "Traversable" types that are "true" (100% conforming) Traversables? Something like StrictlyTraversable/StronglyTraversable/PurelyTraversable/FullyTraversable/(etc).

[xelavopelk]

For the Iterator object to make sense, the head() method has to mutate the Iterator object with what tail() would return.
I can suggest a solution to make idempotent method "head". But "tail", "size" and other methods will be breaking "traversable" contract