Inspired by the earlier discussion with @rvirding, I am currently creating a library, Iter, that allows to iterate over arbitrary data structures in a possibly non-destructive way.
That is, where Extractable.extract
will extract an item and return a collection with that item removed, Iter.next()
will return the next item and a collection that might or might not be altered.
This means that Iterator structs wrapping things like ETS tables, :gb_sets
and :gb_trees
can be made as well.
There are two kinds of Iterators inside Iter:
- ‘Normal’ iterators which might convert the thing they iterate on to a structure more appropriate for iteration. (This is used for many datatypes that right now do not have built-in
first/1, next/2
-support; they are frequently changed into lists)
- and ‘Persistent’ iterators which are guaranteed to be able to reconstruct the thing they iterate over at the end.
Note that the functionality of a PersistentIterator is a superset of a normal Iterator, possibly at the cost of some time and memory efficiency.
I am not yet sure what (if any) advantage a PersistentIterator has over a non-persistent iterator, as we usually still have access to the original data structure before it was turned into an iterator.
But I wanted to build it, in part because I thought of a fun way to (ab)use improper lists to reverse-concatenate two lists (restoring a zipper back to its original list): https://github.com/Qqwy/elixir-iter/blob/master/lib/iter/implementations/list.ex#L63
And in part because there very well might be a proper use for them.
Because these Iterators only iterate on-demand, they are per definition lazy.
I am going to think about what would be the best way to create higher-order iterators (‘iteratees’ or ‘iterator adaptors’), and how the efficiency of the thing could be improved.
This style of iterating is based on the ‘Iteratee’ concept used in Haskell, and also the Iterators in Rust. (Rusts’ iterators work with owned, mutable data however, and therefore are both faster and guaranteed to extract items returned by the iteration from their containers; two guarantees Iter cannot give you).