4 A `for`-loop is typically used to iterate over a range of consecutive
5 integers that denote indices of some sort. For example, in <:OCaml:>
6 a `for`-loop takes either the form
8 for <name> = <lower> to <upper> do <body> done
12 for <name> = <upper> downto <lower> do <body> done
15 Some languages provide considerably more flexible `for`-loop or
18 A bit surprisingly, <:StandardML:Standard ML> provides special syntax
19 for `while`-loops, but not for `for`-loops. Indeed, in SML, many uses
20 of `for`-loops are better expressed using `app`, `foldl`/`foldr`,
21 `map` and many other higher-order functions provided by the
22 <:BasisLibrary:Basis Library> for manipulating lists, vectors and
23 arrays. However, the Basis Library does not provide a function for
24 iterating over a range of integer values. Fortunately, it is very
28 == A fairly simple design ==
30 The following implementation imitates both the syntax and semantics of
35 datatype for = to of int * int
42 (fn f => let fun loop lo = if lo > up then ()
43 else (f lo; loop (lo+1))
46 (fn f => let fun loop up = if up < lo then ()
47 else (f up; loop (up-1))
56 (fn i => print (Int.toString i))
59 would print `123456789` and
64 (fn i => print (Int.toString i))
67 would print `987654321`.
69 Straightforward formatting of nested loops
80 is fairly readable, but tends to cause the body of the loop to be
81 indented quite deeply.
86 The above design has an annoying feature. In practice, the upper
87 bound of the iterated range is almost always excluded and most loops
88 would subtract one from the upper bound:
93 for (n-1 downto 0) ...
96 It is probably better to break convention and exclude the upper bound
97 by default, because it leads to more concise code and becomes
98 idiomatic with very little practice. The iterator combinators
99 described below exclude the upper bound by default.
102 == Iterator combinators ==
104 While the simple `for`-function described in the previous section is
105 probably good enough for many uses, it is a bit cumbersome when one
106 needs to iterate over a Cartesian product. One might also want to
107 iterate over more than just consecutive integers. It turns out that
108 one can provide a library of iterator combinators that allow one to
109 implement iterators more flexibly.
111 Since the types of the combinators may be a bit difficult to infer
112 from their implementations, let's first take a look at a signature of
113 the iterator combinator library:
119 type 'a t = ('a -> unit) -> unit
121 val return : 'a -> 'a t
122 val >>= : 'a t * ('a -> 'b t) -> 'b t
126 val to : int * int -> int t
127 val downto : int * int -> int t
129 val inList : 'a list -> 'a t
130 val inVector : 'a vector -> 'a t
131 val inArray : 'a array -> 'a t
133 val using : ('a, 'b) StringCvt.reader -> 'b -> 'a t
135 val when : 'a t * ('a -> bool) -> 'a t
136 val by : 'a t * ('a -> 'b) -> 'b t
137 val @@ : 'a t * 'a t -> 'a t
138 val ** : 'a t * 'b t -> ('a, 'b) product t
144 Several of the above combinators are meant to be used as infix
145 operators. Here is a set of suitable infix declarations:
154 A few notes are in order:
156 * The `'a t` type constructor with the `return` and `>>=` operators forms a monad.
158 * The `to` and `downto` combinators will omit the upper bound of the range.
160 * `for` is the identity function. It is purely for syntactic sugar and is not strictly required.
162 * The `@@` combinator produces an iterator for the concatenation of the given iterators.
164 * The `**` combinator produces an iterator for the Cartesian product of the given iterators.
165 ** See <:ProductType:> for the type constructor `('a, 'b) product` used in the type of the iterator produced by `**`.
167 * The `using` combinator allows one to iterate over slices, streams and many other kinds of sequences.
169 * `when` is the filtering combinator. The name `when` is inspired by <:OCaml:>'s guard clauses.
171 * `by` is the mapping combinator.
173 The below implementation of the `ITER`-signature makes use of the
174 following basic combinators:
179 fun flip f x y = f y x
181 fun opt fno fso = fn NONE => fno () | SOME ? => fso ?
185 Here is an implementation the `ITER`-signature:
189 structure Iter :> ITER =
191 type 'a t = ('a -> unit) -> unit
194 fun (iA >>= a2iB) f = iA (flip a2iB f)
198 fun (l to u) f = let fun `l = if l<u then (f l; `(l+1)) else () in `l end
199 fun (u downto l) f = let fun `u = if u>l then (f (u-1); `(u-1)) else () in `u end
201 fun inList ? = flip List.app ?
202 fun inVector ? = flip Vector.app ?
203 fun inArray ? = flip Array.app ?
205 fun using get s f = let fun `s = opt (const ()) (fn (x, s) => (f x; `s)) (get s) in `s end
207 fun (iA when p) f = iA (fn a => if p a then f a else ())
208 fun (iA by g) f = iA (f o g)
209 fun (iA @@ iB) f = (iA f : unit; iB f)
210 fun (iA ** iB) f = iA (fn a => iB (fn b => f (a & b)))
216 Note that some of the above combinators (e.g. `**`) could be expressed
217 in terms of the other combinators, most notably `return` and `>>=`.
218 Another implementation issue worth mentioning is that `downto` is
219 written specifically to avoid computing `l-1`, which could cause an
222 To use the above combinators the `Iter`-structure needs to be opened
229 and one usually also wants to declare the infix status of the
230 operators as shown earlier.
232 Here is an example that illustrates some of the features:
236 for (0 to 10 when (fn x => x mod 3 <> 0) ** inList ["a", "b"] ** 2 downto 1 by real)
238 print ("("^Int.toString x^", \""^y^"\", "^Real.toString z^")\n"))
241 Using the `Iter` combinators one can easily produce more complicated
242 iterators. For example, here is an iterator over a "triangle":
246 fun triangle (l, u) = l to u >>= (fn i => i to u >>= (fn j => return (i, j)))