Is Seq.t an iterator?


I’m very happy about the release of OCaml 4.07.0.

One thing that’s bothering me is the header for Seq: “Functional Iterators”. To me an iterator is an object or function that will iterate, but as the next line of the docs says “The type 'a t is a delayed list”.

That is, to me Seq.t is a sequence, not an iterator, as I understand the concept. The Iterator Wikipedia page says that "Internal iterators are higher order functions (often taking anonymous functions) such as map, reduce etc., implementing the traversal across a container, applying the given function to every element in turn. "

Maybe there’s a way of conceptualizing Seq that I’m not seeing.



I am not sure there is a really established terminology with a consensus on what precisely “iterator”, “generator” etc. mean, and in particular I think that the Wikipedia page is not very good right now. That said, lazy lists are precisely “immutable external iterators” in the page’s terminology: they give you the ability to ask for the next element, or go to the rest of the iterator (which you have to pass explicitly, instead of getting it through a side-effect).

Iterators in this style are more powerful for the consumer than folds (what the page call internal iterators), for example it is easy to iterate over two sequences in parallel. This makes them a convenient thing to expose out of the standard library’s data-structures. (For more details on the fact that some APIs are better for the consumer and others for the producer, see my blog post Generators, iterators, control and continuations.)


Thanks @gasche. That way of framing things is helpful.