B.8 User-Defined Functions

A key language concept in ML is that all functions have types.

B.8.1 Simple User-Defined Functions

Named functions are introduced with fun:

Here, the type of square is a function int -> int or, in other words, a function that maps an int to an int. Similarly, the type of add is a function int * int -> int or, in other words, a function that maps a tuple of type int * int to an int. Notice that the interpreter prints the domain of a function that accepts more than one parameter as a Cartesian product using the notation described in Section B.7. These functions are the ML analogs of the following Scheme functions:

Notice that the ML syntax involves fewer lexemes than Scheme (e.g., define is not included). Without excessive parentheses, ML is also more readable than Scheme.

B.8.2 Lambda Functions

Lambda functions (i.e., anonymous or literal functions) are introduced with fn. They are often used, as in other languages, in concert with higher-order functions including map, which is built into ML as in Scheme:

These expressions are the ML analogs of the following Scheme expressions:

Moreover, the functions

are the ML analogs of the following Scheme functions:

Anonymous functions are often used as arguments to higher-order functions.

B.8.3 Pattern-Directed Invocation

A key feature of ML is its support for the definition and invocation of functions using a pattern-matching mechanism called pattern-directed invocation. In pattern-directed invocation, the programmer writes multiple definitions of the same function. When that function is called, the determination of the particular definition of the function to be executed is made based on pattern matching the arguments passed to the function with the patterns used as parameters in the signature of the function. For instance, consider the following definitions of a greatest common divisor function:

The first version (defined on line 2) does not use pattern-directed invocation; that is, there is only one definition of the function. The second version (defined on lines 6–7) uses pattern-directed invocation. If the literal 0 is passed as the second argument to the function gcd, then the first definition of gcd is used (line 6); otherwise, the second definition (line 7) is used.

Pattern-directed invocation is not identical to operator/function overloading. Overloading involves determining which definition of a function to invoke based on the number and types of arguments it is passed at run-time. With pattern-directed invocation, no matter how many definitions of the function exist, all have the same type signature (i.e., number and type of parameters).

Native support for pattern-directed invocation is one of the most convenient features of user-defined functions in ML because it obviates the need for an if–then–else expression to differentiate between the various inputs to a function. Conditional expressions are necessary in languages without built-in pattern-directed invocation (e.g., Scheme). The following are additional examples of pattern-directed invocation:

Argument Decomposition Within Argument List: reverse

Readers with an imperative programming background may be familiar with composing an argument to a function within a function call. For instance, in C:

Here, the expression 2+3 is the first argument to the function f that is called on line 6. Since C uses an eager evaluation parameter-passing strategy, the expression 2+3 is evaluated as 5 and then 5 is passed to f. However, in the body of f, there is no way to conveniently decompose 5 back to 2+3.

Pattern-directed invocation allows ML to support the decomposition of an argument from within the signature itself by using a pattern in a parameter. For instance, consider these three versions of a reverse function:

While the pattern-directed invocation in the second version (lines 10–11) obviates the need for the if–then–else expression (lines 5–6), the functions hd and tl (lines 6 and 11) are required to decompose lst into its head and tail. Calls to the functions hd and tl are obviated by using the pattern x::xs (line 16) in the parameter to reverse. When the third version of reverse is called with a non-empty list, the second definition of it is executed (line 16), the head of the list passed as the argument is bound to x, and the tail of the list passed as the argument is bound to xs.

The cases form in the EOPL extension to Racket Scheme, which may be used to decompose the constituent parts of a variant record as described in Chapter 9 (Friedman, Wand, and Haynes 2001), is the Racket Scheme analog of the use of patterns in parameters to decompose arguments to a function. Pattern-directed invocation, including the use of patterns for decomposing arguments, and the pattern-action style of programming, is common in the programming language Prolog.

A Handle to Both Decomposed and Undecomposed Form of an Argument: as

Sometimes we desire access to both the decomposed argument and the undecomposed argument to a function without calling functions to decompose or recompose it. The use of as between a decomposed parameter and an undecomposed parameter maintains both throughout the definition of the function (line 3):

Anonymous Parameters

The underscore (_) pattern on lines 1 and 2 of the definition of the konsMinHeadtoOther function represents an anonymous parameter—a parameter whose name is unnecessary to the definition of the function. As an additional example, consider the following definition of a list member function:

Type Variables

While some functions, such as square and add, require arguments of a particular type, others, such as reverse and member, accept arguments of any type or arguments whose types are partially restricted. For instance, the type of the function reverse is ′a list -> ′a list. Here, the ′a means “any type.” Therefore, the function reverse accepts a list of any type ′a and returns a list of the same type. The ′a is called a type variable. In programming languages, the ability of a single function to accept arguments of different types is called polymorphism because poly means “many” and morph means “form.” Such a function is called polymorphic. A polymorphic type is a type expression containing type variables. The type of polymorphism discussed here is called parametric polymorphism, where a function or data type can be defined generically so that it can handle values identically without depending on their type. (The type variable ″a means “any type that can be compared for equality.”)

Neither pattern-directed invocation nor operator/function overloading (sometimes called ad hoc polymorphism) is the identical to (parametric) polymorphism. Overloading involves using the same operator/function name to refer to different definitions of a function, each of which is identifiable by the different number or types of arguments to which it is applied. Parametric polymorphism, in contrast, involves only one operator/function name referring to only one definition of the function that can accept arguments of multiple types. Thus, ad hoc polymorphism typically only supports a limited number of such distinct types, since a separate implementation must be provided for each type.

B.8.4 Local Binding and Nested Functions: let Expressions

A let–in–end expression in ML is used to introduce local binding for the purposes of avoiding recomputation of common subexpressions and creating nested functions for both protection and factoring out constant parameters so as to avoid passing (and copying) arguments that remain constant between successive recursive function calls.

Local Binding

Lines 8–12 of the following example demonstrate local binding in ML:

These functions are the ML analogs of the following Scheme functions:

Nested Functions

Since the function insertineach is intended to be only visible, accessible, and called by the powerset function, we can also use a let ...in ...end expression to nest it within the powerset function (lines 3–11 in the next example):

The following example uses a let–in–end expression to define a nested function that implements the difference lists technique to avoid appending in a definition of a reverse function:

Note that the polymorphic type of reverse, [a] -> [a], indicates that reverse can reverse a list of any type.

B.8.5 Mutual Recursion

Unlike in Scheme, in ML a function must first be defined before it can be used in other functions:

This makes the definition of mutually recursive functions (i.e., functions that call each other) problematic without direct language support. Mutually recursive functions in ML must be defined with the and reserved word between each definition. For instance, consider the functions isodd and iseven, which rely on each other to determine if an integer is odd or even, respectively:

Note that more than two mutually recursive functions can be defined. Each but the last must be followed by an and, and the last is followed with a semicolon (;). ML performs tail-call optimization.

B.8.6 Putting It All Together: Mergesort

Consider the following definitions of a recursive mergesort function.

Unnested, Unhidden, Flat Version

Nested, Hidden Version

Nested, Hidden Version Accepting a Comparison Operator as a Parameter

When passing an operator as an argument to a function, the operator passed must be a prefix operator. Since the operators < and > are infix operators, we cannot pass them to this version of mergesort without first converting each to a prefix operator. We can convert an infix operator to a prefix operator by wrapping it in a user-defined function (lines 1 and 4) or by using the built-in function op, which converts an infix operator to a prefix operator (lines 7, 10, and 13):

Since the closing lexeme for a comment in ML is *), we must add a whitespace character after the * when converting the infix multiplication operator to a prefix operator:

Final Version

The following code is the final version of mergesort using nested, protected functions and accepting a comparison operator as a parameter, which is factored out to avoid passing it between successive recursive calls:

Notice also that we factored the argument compop out of the function merge in this version since it is visible from an outer scope.