package iter
Install
Dune Dependency
Authors
Maintainers
Sources
md5=68ddbe4a3626943308d9a4f2be9fa146
sha512=ab4c1002cb1fbc83d6dc71bae6f47666eb12f63e23c83dd38a5a2e9a9a6f2b3368ef477a7e269b7c6352035e274b745aa37bf082b7aef8d3a88e380097310678
Description
README
Iter
Clean and efficient loop fusion for all your iterating needs!
# #require "iter";;
# let p x = x mod 5 = 0 in
Iter.(1  5_000 > filter p > map (fun x > x * x) > fold (+) 0);;
 : int = 8345837500
Iter
is a simple abstraction over iter
functions intended to iterate efficiently on collections while performing some transformations. Common operations supported by Iter
include filter
, map
, take
, drop
, append
, flat_map
, etc. Iter
is not designed to be as generalpurpose or flexible as Seq
. Rather, it aims at providing a very simple and efficient way 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 a Hashtbl.t
, without creating a list. Similarly, the code above is turned into a single optimized for loop with flambda
.
Documentation
There is only one important type, 'a Iter.t
, and lots of functions built around this type. See the online API for more details on the set of available functions. Some examples can be found below.
The library used to be called Sequence
. Some historical perspective is provided in this talk given by @ccube at some OCaml meeting.
Short Tutorial
Transferring Data
Conversion between n container types would take n² functions. In practice, for a given collection we can at best hope for to_list
and of_list
. With iter, if the source structure provides a iter
function (or a to_iter
wrapper), it becomes:
# let q : int Queue.t = Queue.create();;
val q : int Queue.t = <abstr>
# Iter.( 1  10 > to_queue q);;
 : unit = ()
# Iter.of_queue q > Iter.to_list ;;
 : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
# let s : int Stack.t = Stack.create();;
val s : int Stack.t = <abstr>
# Iter.(of_queue q > to_stack s);;
 : unit = ()
# Iter.of_stack s > Iter.to_list ;;
 : int list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]
Note how the list of elements is reversed when we transfer them from the queue to the stack.
Another example is extracting the list of values of a hashtable (in an undefined order that depends on the underlying hash function):
# let h: (int, string) Hashtbl.t = Hashtbl.create 16;;
val h : (int, string) Hashtbl.t = <abstr>
# for i = 0 to 10 do
Hashtbl.add h i (string_of_int i)
done;;
 : unit = ()
# Hashtbl.length h;;
 : int = 11
# (* now to get the values *)
Iter.of_hashtbl h > Iter.map snd > Iter.to_list;;
 : string list = ["6"; "2"; "8"; "7"; "3"; "5"; "4"; "9"; "0"; "10"; "1"]
Replacing for
loops
The for
loop is a bit limited, and lacks compositionality. Instead, it can be more convenient and readable to use Iter.() : int > int > int Iter.t
.
# Iter.(1  10_000_000 > fold (+) 0);;
 : int = 50000005000000
# let p x = x mod 5 = 0 in
Iter.(1  5_000
> filter p
> map (fun x > x * x)
> fold (+) 0
);;
 : int = 8345837500
NOTE: with flambda under sufficiently strong optimization flags, such compositions of operators should be compiled to an actual loop with no overhead!
Iterating on subtrees
A small λcalculus AST, and some operations on it.
# type term =
 Var of string
 App of term * term
 Lambda of term ;;
type term = Var of string  App of term * term  Lambda of term
# let rec subterms : term > term Iter.t =
fun t >
let open Iter.Infix in
Iter.cons t
(match t with
 Var _ > Iter.empty
 Lambda u > subterms u
 App (a,b) >
Iter.append (subterms a) (subterms b))
;;
val subterms : term > term Iter.t = <fun>
# (* Now we can define many other functions easily! *)
let vars t =
Iter.filter_map
(function Var s > Some s  _ > None)
(subterms t) ;;
val vars : term > string Iter.t = <fun>
# let size t = Iter.length (subterms t) ;;
val size : term > int = <fun>
# let vars_list l = Iter.(of_list l > flat_map vars);;
val vars_list : term list > string Iter.t = <fun>
Permutations
Makes it easy to write backtracking code (a nondeterministic function returning several 'a
will just return a 'a Iter.t
). Here, we generate all permutations of a list by enumerating the ways we can insert an element in a list.
# open Iter.Infix;;
# let rec insert x l = match l with
 [] > Iter.return [x]
 y :: tl >
Iter.append
(insert x tl >= fun tl' > y :: tl')
(Iter.return (x :: l)) ;;
val insert : 'a > 'a list > 'a list Iter.t = <fun>
# let rec permute l = match l with
 [] > Iter.return []
 x :: tl > permute tl >>= insert x ;;
val permute : 'a list > 'a list Iter.t = <fun>
# permute [1;2;3;4] > Iter.take 2 > Iter.to_list ;;
 : int list list = [[4; 3; 2; 1]; [4; 3; 1; 2]]
Advanced example
The module examples/sexpr.mli
exposes the interface of the Sexpression example library. It requires OCaml>=4.0 to compile, because of the GADT structure used in the monadic parser combinators part of examples/sexpr.ml
. Be careful that this is quite obscure.
Comparison with Seq
from the standard library, and with Gen
Seq
is an external iterator. It means that the code which consumes some iterator of type'a Seq.t
is the one which decides when to go to the next element. This gives a lot of flexibility, for example when iterating on several iterators at the same time:let rec zip a b () = match a(), b() with  Nil, _  _, Nil > Nil  Cons (x, a'), Cons (y, b') > Cons ((x,y), zip a' b')
Iter
is an internal iterator. When one wishes to iterate over an'a Iter.t
, one has to give a callbackf : 'a > unit
that 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.t
is 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 internal data structure.Gen
(from the gen library) is an external 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 but only 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 also requires more knowledge of the underlying source of items. For some operations such as map
or flat_map
, Iter is also extremely efficient and will, if flambda permits, be totally removed at compile time (e.g. Iter.()
becomes a for loop, and Iter.filter
becomes a if test).
For more details, you can read http://gallium.inria.fr/blog/generatorsiteratorscontrolandcontinuations/ or see the slides about Iter by me (ccube) when Iter
was still called Sequence
.
Build
via opam
opam install iter
manually (need OCaml >= 4.02.0):
make all install
If you have qtest installed, you can build and run tests with
$ make test
If you have benchmarks installed, you can build and run benchmarks with
$ make benchs
To see how to use the library, check the following tutorial. The tests
and examples
directories also have some examples, but they're a bit arcane.
License
Iter is available under the BSD license.
Dependencies (5)
 duneconfigurator

dune
>= "1.1" & < "3.0"

ocaml
>= "4.03.0"
 result
 basebytes
Dev Dependencies (4)
Used by (21)

archsat
>= "1.1"
 benchpress

calculon
= "0.5"

containers
>= "2.6"
 containersdata
 containersthread
 dirspproscriptmirage

earlybird
>= "1.0.0"
 ego

electrod
>= "0.2.3"
 grace
 libzipperposition

logtk
>= "1.5.1"
 mc2

msat
>= "0.8"

mssql
>= "2.0.3"

regenerate
>= "0.2"

smbc
>= "0.6"

tree_layout
>= "0.2"

zipperposition
>= "1.5.1"
 zipperpositiontools
Conflicts
None