Repository files navigation

Clean and efficient loop fusion for all your iterating needs!

##require"iter";;#letpx= xmod5=0inIter.(1--5_000|> filter p|> map (funx -> x* x)|> fold (+)0);;- :int=8345837500

Iter is a simple abstraction overiter functionsintended to iterate efficientlyon collections while performing some transformations.Common operations supported byIter includefilter,map,take,drop,append,flat_map, etc.Iter is not designed to be as general-purpose or flexible asSeq.Rather, it aims at providing a very simple and efficientway of iterating on a finite number of values, only allocating (most of the time)one intermediate closure to do so. For instance, iterating on keys, or values,of aHashtbl.t, without creating a list.Similarly, the code above is turned into a single optimizedfor loop withflambda.

There is only one important type,'a Iter.t, and lots of functions builtaround this type.Seethe online APIfor more details on the set of available functions.Some examples can be found below.

The library used to be calledSequence.Some historical perspective is providedinthis talkgiven by @c-cube at some OCaml meeting.

Conversion between n container typeswould take n² functions. In practice, for a given collectionwe can at best hope forto_list andof_list.With iter, if the source structure provides aiter function (or ato_iter wrapper), it becomes:

#letq :int Queue.t=Queue.create();;valq :intQueue.t=<abstr>#Iter.(1--10 |>to_queueq);;- :unit= ()#Iter.of_queueq |>Iter.to_list ;;- :intlist= [1;2;3;4;5;6;7;8;9;10]#lets :int Stack.t=Stack.create();;vals :intStack.t=<abstr>#Iter.(of_queueq |>to_stacks);;- :unit= ()#Iter.of_stacks |>Iter.to_list ;;- :intlist= [10;9;8;7;6;5;4;3;2;1]

Note how the list of elements is reversed when we transfer themfrom the queue to the stack.

Another example is extracting the list of values ofa hashtable (in an undefined order that depends on theunderlying hash function):

#let h: (int,string)Hashtbl.t=Hashtbl.create16;;valh : (int,string)Hashtbl.t=<abstr>#fori=0to10doHashtbl.addhi (string_of_inti)done;;- :unit= ()#Hashtbl.length h;;- :int=11#(* now to get the values*)Iter.of_hashtbl h|>Iter.map snd|>Iter.to_list;;- :stringlist= ["6";"2";"8";"7";"3";"5";"4";"9";"0";"10";"1"]

Thefor loop is a bit limited, and lacks compositionality.Instead, it can be more convenient and readable touseIter.(--) : int -> int -> int Iter.t.

#Iter.(1--10_000_000|> fold (+)0);;- :int=50000005000000#letpx= xmod5=0inIter.(1--5_000|> filter p|> map (funx -> x* x)|> fold (+)0  );;- :int=8345837500

NOTE: withflambda under sufficiently strongoptimization flags, such compositions of operatorsshould be compiled to an actual loop with no overhead!

A small λ-calculus AST, and some operations on it.

#type term=|Var ofstring|App of term* term|Lambda of term ;;typeterm=Varofstring |Appofterm*term |Lambdaofterm#letrecsubterms :term -> term Iter.t=funt ->letopenIter.InfixinIter.cons t      (match twith|Var_ ->Iter.empty|Lambdau -> subterms u|App (a,b) ->Iter.append (subterms a) (subterms b))  ;;valsubterms :term ->termIter.t=<fun>#(* Now we can define many other functions easily!*)letvarst=Iter.filter_map      (functionVars ->Some s|_ ->None)      (subterms t) ;;valvars :term ->stringIter.t=<fun>#letsizet=Iter.length (subterms t) ;;valsize :term ->int=<fun>#letvars_listl=Iter.(of_list l|> flat_map vars);;valvars_list :termlist ->stringIter.t=<fun>

Makes it easy to write backtracking code (a non-deterministicfunction returning several'awill just return a'a Iter.t).Here, we generate all permutations of a list byenumerating the ways we can insert an element in a list.

#openIter.Infix;;#letrecinsertxl=match lwith|[] ->Iter.return [x]|y ::tl ->Iter.append      (insert x tl>|=funtl' -> y :: tl')      (Iter.return (x :: l)) ;;valinsert :'a ->'alist ->'alistIter.t=<fun>#letrecpermutel=match lwith|[] ->Iter.return[]|x ::tl -> permute tl>>= insert x ;;valpermute :'alist ->'alistIter.t=<fun># permute [1;2;3;4]|>Iter.take2|>Iter.to_list ;;- :intlistlist= [[4;3;2;1]; [4;3;1;2]]

The moduleexamples/sexpr.mli exposes the interface of the S-expressionexample library. It requires OCaml>=4.0 to compile, because of the GADTstructure used in the monadic parser combinators part ofexamples/sexpr.ml.Be careful that this is quite obscure.

• Seq is anexternal iterator.It means that the code which consumessome iterator of type'a Seq.t is the one which decides when togo to the next element. This gives a lot of flexibility, for examplewhen iterating on several iterators at the same time:

  letreczipab()=match a(), b()with|Nil, _|_,Nil ->Nil|Cons (x,a'),Cons (y,b') ->Cons ((x,y), zip a' b')

• Iter is aninternal iterator. When one wishes to iterate overan'a Iter.t, one has to give a callbackf : 'a -> unitthat is called in succession over every element of the iterator.Control is not handed back to the caller before the whole iteration is over.This makeszip impossible to implement. However, the type'a Iter.tis general enough that it can be extracted from any classiciter function,including from data structures such asMap.S.t orSet.S.t orHashtbl.t;one cannot obtain a'a Seq.t from these without having access to the internaldata structure.

• Gen (fromthe gen library)is anexternal iterator, likeSeq, but it is imperative, mutable, and consumable(you can't iterate twice on the same'a Gen.t).It looks a lot like iterators in rust/java/… and can be pretty efficient in some cases.Since you control iteration you can also writemap2,for_all2, etc butonly with linear use of input generators (since you can traverse them only once).That requires some trickery for cartesian_product (like storing already produced elements internally).

In short,'a Seq.t is more expressive than'a Iter.t, but it alsorequires more knowledge of the underlying source of items.For some operations such asmap orflat_map, Iter is also extremelyefficient and will, if flambda permits, be totally removed atcompile time (e.g.Iter.(--) becomes a for loop, andIter.filterbecomes a if test).

For more details, you can readhttp://gallium.inria.fr/blog/generators-iterators-control-and-continuations/ orseethe slides about Iterby me (c-cube) whenIter was still calledSequence.

1. via opamopam install iter
2. manually (need OCaml >= 4.02.0):make all install

If you haveqtest installed,you can build and run tests with

$ make test

If you havebenchmarks installed,you can build and run benchmarks with

$ make benchs

To see how to use the library, check the following tutorial.Thetests andexamples directories also have some examples, but they're a bit arcane.

Iter is available under the BSD license.