Programmers coming from languages that have a return statement, such as C, Java, and Python, often ask how one can translate functions that return early into SML. This page briefly describes a number of ways to translate uses of return to SML.

Conditional iterator function

A conditional iterator function, such as List.find, List.exists, or List.all is probably what you want in most cases. Unfortunately, it might be the case that the particular conditional iteration pattern that you want isn’t provided for your data structure. Usually the best alternative in such a case is to implement the desired iteration pattern as a higher-order function. For example, to implement a find function for arrays (which already exists as Array.find) one could write

fun find predicate array = let
   fun loop i =
       if i = Array.length array then
          NONE
       else if predicate (Array.sub (array, i)) then
          SOME (Array.sub (array, i))
       else
          loop (i+1)
in
   loop 0
end

Of course, this technique, while probably the most common case in practice, applies only if you are essentially iterating over some data structure.

Escape handler

Probably the most direct way to translate code using return statements is to basically implement return using exception handling. The mechanism can be packaged into a reusable module with the signature (exit.sig):

<!IncludeSVN(mltonlib/trunk/com/ssh/extended-basis/unstable/public/control/exit.sig,sml,6:)>

(Typing First-Class Continuations in ML discusses the typing of a related construct.) The implementation (exit.sml) is straightforward:

<!IncludeSVN(mltonlib/trunk/com/ssh/extended-basis/unstable/detail/control/exit.sml,sml,6:)>

Here is an example of how one could implement a find function given an app function:

fun appToFind (app : ('a -> unit) -> 'b -> unit)
              (predicate : 'a -> bool)
              (data : 'b) =
    Exit.call
       (fn return =>
           (app (fn x =>
                    if predicate x then
                       return (SOME x)
                    else
                       ())
                data
          ; NONE))

In the above, as soon as the expression predicate x evaluates to true the app invocation is terminated.

Continuation-passing Style (CPS)

A general way to implement complex control patterns is to use CPS. In CPS, instead of returning normally, functions invoke a function passed as an argument. In general, multiple continuation functions may be passed as arguments and the ordinary return continuation may also be used. As an example, here is a function that finds the leftmost element of a binary tree satisfying a given predicate:

datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree

fun find predicate = let
   fun recurse continue =
       fn LEAF =>
          continue ()
        | BRANCH (lhs, elem, rhs) =>
          recurse
             (fn () =>
                 if predicate elem then
                    SOME elem
                 else
                    recurse continue rhs)
             lhs
in
   recurse (fn () => NONE)
end

Note that the above function returns as soon as the leftmost element satisfying the predicate is found.