Strictly speaking, in an immutable world, your iterator only gives you access to the head of your collection. I think this is a fairly standard functional repr

Strictly speaking, in an immutable world, your iterator only gives you access to the head of your collection. I think this is a fairly standard functional representation of iterable entities: next :: T a -> Maybe a rest :: T a -> Maybe (T a) We could (and you should) argue that this is correct by intuition, but it's also possible to sketch a proof that these structures all "behave" the same as lists would. We can first combine `next` and `rest` into a single function -- note that we can always interconvert between (next, rest) and step: step :: T a -> Maybe (a, T a) This has the form of something called a "co-algebra", which consists of (1) a functor `F`, (2) a type `k`, and (3) and a function `k -> F k`. In this case, `k = T a` and `F = Maybe (a, -)`. The interesting thing is that the functor `Maybe (a, -)` can have many co-algebras, depending on which type and step function you pick. The type [a] -- that is, picking T to be [] -- gives a particularly special co-algebra, called the "terminal" coalgebra for `Maybe (a, -)`. In short, while any other choice of coalgebra may support additional operations, you can convert any one of them to a list without disturbing a process that only makes use of the nominated `step` function. They're observationally equivalent to lists.