ForLoops - MLton Standard ML Compiler (SML Compiler)

A for-loop is typically used to iterate over a range of consecutive integers that denote indices of some sort. For example, in OCaml a for-loop takes either the form

for <name> = <lower> to <upper> do <body> done

or the form

for <name> = <upper> downto <lower> do <body> done

Some languages provide considerably more flexible for-loop or foreach-constructs.

A bit surprisingly, Standard ML provides special syntax for while-loops, but not for for-loops. Indeed, in SML, many uses of for-loops are better expressed using app, foldl/foldr, map and many other higher-order functions provided by the Basis Library for manipulating lists, vectors and arrays. However, the Basis Library does not provide a function for iterating over a range of integer values. Fortunately, it is very easy to write one.

A fairly simple design

The following implementation imitates both the syntax and semantics of the OCaml for-loop.

datatype for = to of int * int
             | downto of int * int

infix to downto

val for =
    fn lo to up =>
       (fn f => let fun loop lo = if lo > up then ()
                                  else (f lo; loop (lo+1))
                in loop lo end)
     | up downto lo =>
       (fn f => let fun loop up = if up < lo then ()
                                  else (f up; loop (up-1))
                in loop up end)

For example,

for (1 to 9)
    (fn i => print (Int.toString i))

would print 123456789 and

for (9 downto 1)
    (fn i => print (Int.toString i))

would print 987654321.

Straightforward formatting of nested loops

for (a to b)
    (fn i =>
        for (c to d)
            (fn j =>
                ...))

is fairly readable, but tends to cause the body of the loop to be indented quite deeply.

Off-by-one

The above design has an annoying feature. In practice, the upper bound of the iterated range is almost always excluded and most loops would subtract one from the upper bound:

for (0 to n-1) ...
for (n-1 downto 0) ...

It is probably better to break convention and exclude the upper bound by default, because it leads to more concise code and becomes idiomatic with very little practise. The iterator combinators described below exclude the upper bound by default.

Iterator combinators

While the simple for-function described in the previous section is probably good enough for many uses, it is a bit cumbersome when one needs to iterate over a cartesian product. One might also want to iterate over more than just consecutive integers. It turns out that one can provide a library of iterator combinators that allow one to implement iterators more flexibly.

Since the types of the combinators may be a bit difficult to infer from their implementations, let's first take a look at a signature of the iterator combinator library:

signature ITER =
  sig
    type 'a iter = ('a -> unit) -> unit

    val to : int * int -> int iter
    val downto : int * int -> int iter

    val inList : 'a list -> 'a iter
    val inVector : 'a Vector.vector -> 'a iter
    val inArray : 'a Array.array -> 'a iter

    val using : ('a -> ('b * 'a) option) -> 'a -> 'b iter

    val when : 'a iter * ('a -> bool) -> 'a iter
    val by : 'a iter * ('a -> 'b) -> 'b iter

    val && : 'a iter * 'b iter -> ('a, 'b) product iter

    val for : 'a -> 'a
  end

Some of the above combinators are meant to be used as infix operators. Here is a set of suitable infix declarations:

infix 2 to downto
infix 1 when by
infix 0 &&

A few notes are in order:

The following implementation of to and downto will omit the upper bound of the range.
for is the identity function. It is purely for syntactic sugar and is not strictly required.
Probably the most interesting combinator is &&. Given two iterators, it produces an iterator for the cartesian product of the iterators.

See ProductType for the type function ('a, 'b) product used in the type of the iterator produced by &&.

The using combinator allows one to iterate over slices, streams and many other kinds of sequences.
when is the filtering combinator. The name when is inspired by OCaml's guard clauses.
by is the mapping combinator.

Here is a structure implementing the ITER signature:

structure Iter :> ITER =
  struct
    type 'a iter = ('a -> unit) -> unit

    fun op to (a, b) f =
        let fun loop a = if a < b then (f a; loop (a+1)) else ()
        in loop a end
    fun op downto (a, b) f =
        let fun loop a = if a > b then (fn a => (f a; loop a)) (a-1) else ()
        in loop a end

    fun inList l f = List.app f l
    fun inVector v f = Vector.app f v
    fun inArray a f = Array.app f a

    fun using get s f =
        let fun loop s = case get s
                          of SOME (x, s) => (f x; loop s)
                           | NONE => ()
        in loop s end

    fun op when (a, p) f = a (fn a => if p a then f a else ())
    fun op by (a, g) f = a (f o g)

    fun op && (a, b) f = a (fn a => b (fn b => f (op& (a, b))))

    val for = fn x => x
  end

To use the above combinators the Iter-structure needs to be opened

open Iter

and one usually also wants to declare the infix status of the operators as shown earlier.

Here is an example that illustrates most of the features:

for (0 to 10 when (fn x => x mod 3 <> 0) && inList ["a", "b"] && 2 downto 1 by real)
    (fn x & y & z =>
       print ("("^Int.toString x^", \""^y^"\", "^Real.toString z^")\n"))