Next: Modules, Previous: User-defined equality and comparison, Up: Top [Contents]

Mercury supports higher-order functions and predicates with currying, closures, and lambda expressions. (To be pedantic, it would be more accurate to say that Mercury supports higher-order procedures. This is because in Mercury, when you construct a higher-order term, you only get one mode of a predicate or function. If you want multiple modes, you must pass multiple higher-order procedures.)

To create a higher-order predicate or function term, you can use a lambda expression, or, if the predicate or function has only one mode and it is not a zero-arity function, you can just use its name. For example, if you have declared a predicate

:- pred sum(list(int), int). :- mode sum(in, out) is det.

the following unifications have the same effect:

X = (pred(List::in, Length::out) is det :- sum(List, Length)) Y = sum

In the above example,
the type of `X`

, and `Y`

is ‘`pred(list(int), int)`’,
which means a predicate of two arguments
of types `list(int)`

and `int`

respectively.

Similarly, given

:- func scalar_product(int, list(int)) = list(int). :- mode scalar_product(in, in) = out is det.

the following three unifications have the same effect:

X = (func(Num, List) = NewList :- NewList = scalar_product(Num, List)) Y = (func(Num::in, List::in) = (NewList::out) is det :- NewList = scalar_product(Num, List)) Z = scalar_product

In the above example,
the type of `X`

, `Y`

, and `Z`

is
‘`func(int, list(int)) = list(int)`’,
which means a function of two arguments,
whose types are `int`

and `list(int)`

,
with a return type of `int`

.
As with ‘`:- func`’ declarations,
if the modes and determinism of the function
are omitted in a higher-order function term,
then the modes default to `in`

for the arguments,
`out`

for the function result,
and the determinism defaults to `det`

.

The Melbourne Mercury implementation currently requires that you use an explicit lambda expression to specify which mode you want, if the predicate or function has more than one mode (but see below for an exception to this rule).

You can also create higher-order function terms of non-zero arity and higher-order predicate terms by “currying”, i.e. specifying the first few arguments to a predicate or function, but leaving the remaining arguments unspecified. For example, the unification

Sum123 = sum([1,2,3])

binds `Sum123`

to a higher-order predicate term of type ‘`pred(int)`’.
Similarly, the unification

Double = scalar_product(2)

binds `Double`

to a higher-order function term of type
‘`func(list(int)) = list(int)`’.

As a special case, currying of a multi-moded predicate or function is allowed
provided that the mode of the predicate or function
can be determined from the insts of the higher-order curried arguments.
For example, ‘`P = list.foldl(io.write)`’ is allowed
because the inst of ‘`io.write`’ matches
exactly one mode of ‘`list.foldl`’.

For higher-order predicate expressions that thread an accumulator pair, we have syntax that allows you to use DCG notation in the goal of the expression. For example,

Pred = ( pred(Strings::in, Num::out, di, uo) is det --> io.write_string("The strings are: "), { list.length(Strings, Num) }, io.write_strings(Strings), io.nl )

is equivalent to

Pred = ( pred(Strings::in, Num::out, IO0::di, IO::uo) is det :- io.write_string("The strings are: ", IO0, IO1), list.length(Strings, Num), io.write_strings(Strings, IO1, IO2), io.nl(IO2, IO) )

Higher-order function terms of zero arity
can only be created using an explicit lambda expression;
you have to use e.g. ‘`(func) = foo`’ rather than plain ‘`foo`’,
because the latter denotes the result of evaluating the function,
rather than the function itself.

Note that when constructing a higher-order term,
you cannot just use the name of a builtin language construct
such as ‘`=`’, ‘`\=`’, ‘`call`’, or ‘`apply`’,
and nor can such constructs be curried.
Instead, you must either use an explicit lambda expression,
or you must write a forwarding predicate or function.
For example, instead of

list.filter(\=(2), [1, 2, 3], List)

you must write either

list.filter((pred(X::in) is semidet :- X \= 2), [1, 2, 3], List)

or

list.filter(not_equal(2), [1, 2, 3], List)

where you have defined ‘`not_equal`’ using

:- pred not_equal(T::in, T::in) is semidet. not_equal(X, Y) :- X \= Y.

Another case when this arises is when want to curry a higher-order term.
Suppose, for example, that you have
a higher-order predicate term ‘`OldPred`’
of type ‘`pred(int, char, float)`’,
and you want to construct a new higher-order predicate term
‘`NewPred`’ of type ‘`pred(char, float)`’ from ‘`OldPred`’
by supplying a value for just the first argument.
The solution is the same:
use an explicit lambda expression or a forwarding predicate.
In either case, the body of the lambda expression or the forwarding predicate
must contain a higher-order call with all the arguments supplied.

Once you have created a higher-order predicate term (sometimes known as a closure), the next thing you want to do is to call it. For predicates, you use the builtin goal call/N:

`call(Closure)`

`call(Closure1, Arg1)`

`call(Closure2, Arg1, Arg2)`

- …
A higher-order predicate call. ‘

`call(Closure)`’ just calls the specified higher-order predicate term. The other forms append the specified arguments onto the argument list of the closure before calling it.

For example, the goal

call(Sum123, Result)

would bind `Result`

to the sum of ‘`[1, 2, 3]`’, i.e. to 6.

For functions, you use the builtin expression apply/N:

`apply(Closure)`

`apply(Closure1, Arg1)`

`apply(Closure2, Arg1, Arg2)`

- …
A higher-order function application. Such a term denotes the result of invoking the specified higher-order function term with the specified arguments.

For example, given the definition of ‘`Double`’ above, the goal

List = apply(Double, [1, 2, 3])

would be equivalent to

List = scalar_product(2, [1, 2, 3])

and so for a suitable implementation of the function ‘`scalar_product/2`’
this would bind `List`

to ‘`[2, 4, 6]`’.

One useful higher-order predicate in the Mercury standard library
is ‘`solutions/2`’, which has the following declaration:

:- pred solutions(pred(T), list(T)). :- mode solutions(in(pred(out) is nondet), out) is det.

The term which you pass to ‘`solutions/2`’ is a higher-order predicate term.
You can pass the name of a one-argument predicate,
or you can pass a several-argument predicate
with all but one of the arguments supplied (a closure).
The declarative semantics of ‘`solutions/2`’ can be defined as follows:

solutions(Pred, List) is true iff all [X] (call(Pred, X) <=> list.member(X, List)) and List is sorted without any duplicates.

where ‘`call(Pred, X)`’
invokes the higher-order predicate term `Pred`

with argument `X`

,
and where ‘`list.member/2`’
is the standard library predicate for list membership.
In other words, ‘`solutions(Pred, List)`’ finds all the values of `X`

for which ‘`call(Pred, X)`’ is true,
collects these solutions in a list,
sorts the list, and returns that list as its result.
Here is an example: the standard library defines a predicate
‘`list.perm(List0, List)`’

:- pred list.perm(list(T), list(T)). :- mode list.perm(in, out) is nondet.

which succeeds iff List is a permutation of List0. Hence the following call to solutions

solutions(list.perm([3,1,2]), L)

should return
all the possible permutations of the list ‘`[3,1,2]`’ in sorted order:

L = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].

See also ‘`unsorted_solutions/2`’ and ‘`solutions_set/2`’,
which are defined in the standard library module ‘`solutions`’
and documented in the Mercury Library Reference Manual.

In Mercury, it is an error to attempt to unify or to compare two higher-order terms. This is because the question of whether two higher-order terms are equivalent is undecidable in the general case.

Note that the compiler will catch only
*direct* attempts at unifications or comparisons of higher-order terms.
Indirect attempts,
using for example polymorphic predicates
such as ‘`(list.append([], [P], [Q])`’,
will result in an error at run-time rather than at compile-time.

In Mercury, the mode and determinism
of a higher-order predicate or function term
are generally part of that term’s *inst*, not its *type*.
This allows a single higher-order predicate to work
on argument predicates that differ in their modes and in their determinisms,
which is particularly useful for library predicates
such as ‘`list.map`’ and ‘`list.foldl`’.

Consider ‘`list.foldl`’, one of the standard fold predicates on lists.
The types of its arguments are given by this predicate declaration:

:- pred foldl(pred(L, A, A), list(L), A, A).

The first argument is a higher order value (a predicate in this case),
whose types are the types bound by the caller
to the type variables `L`, `A` and `A` respectively,
where `L` is the type of the elements in the list in the second argument,
and `A` is the type of the accumulator
whose initial and final values are the third and fourth arguments.
The job of the predicate passed in the first argument
is to combine each element in the list
with the current value of the accumulator
to generate the next value of the accumulator,
so in most calls to ‘`list.foldl`’,
the argument modes and the determinism of that predicate will be

pred(in, in, out) is det

This is a *higher order inst*:
an inst describing the modes of the arguments and the determinism
of a higher order value, which in this case is a predicate.
A *higher order mode* is a mode in which
the initial and/or final inst is a higher order inst.
These *can* be written like this:

pred(in, in, out) is det >> pred(in, in, out) is det

for a predicate being passed to another predicate or function, and like this

free >> pred(in, in, out) is det

for a predicate being returned from another predicate or function.
In practice, it is far more convenient
to use the builtin mode constructors ‘`in/1`’ and ‘`out/1`’ to write

in(pred(in, in, out) is det) out(pred(in, in, out) is det)

which are each equivalent to the corresponding example just above.

You can use higher order insts and modes in mode declarations like this:

:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.

The ‘`in()`’ wrapper around the higher order inst here
declares the first argument of ‘`list.foldl`’ to be an input,
but the higher order inst inside the wrapper goes further,
by specifying the argument modes and the determinism
of the predicate that ‘`list.foldl`’ takes *in this mode*.

That last qualification is important,
because ‘`list.foldl`’ has several modes,
each differing in the argument modes, in the determinism, or both.
The set of mode declarations for ‘`list.foldl`’ includes

:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det. :- mode foldl(in(pred(in, di, uo) is det), in, di, uo) is det. :- mode foldl(in(pred(in, in, out) is semidet), in, in, out) is semidet. :- mode foldl(in(pred(in, in, out) is cc_multi), in, in, out) is cc_multi. :- mode foldl(in(pred(in, di, uo) is cc_multi), in, di, uo) is cc_multi.

That means you can pass predicates
with several different argument mode/determinism combinations
as the first argument.
In the case of ‘`list.foldl`’,
the modes of the accumulator arguments
and the determinism of the whole predicate will follow
the argument modes and the determinism of the higher-order argument,
but one can create predicates (and functions) where this would not be true.

You can give names to such insts and modes using declarations such as

:- inst std_fold_pred == (pred(in, in, out) is det). :- mode std_fold_pred_in == in(pred(in, in, out) is det).

Note that the parentheses around the right hand side of the inst declaration
are required, due to the relative precedences
of the ‘`==`’ and ‘`is`’ operators.

Given these definitions, the declarations

:- mode foldl(in(std_fold_pred), in, in, out) is det. :- mode foldl(std_fold_pred_in, in, in, out) is det.

are both equivalent to

:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.

but they may be more convenient to write,
especially in the presence of more arguments.
^{3}

The general form of higher order insts follows one of two patterns, one for predicates, and one for functions.

The pattern for predicates is

(pred) isDeterminismpred(Mode) isDeterminismpred(Mode1,Mode2) isDeterminism…

while the pattern for functions is

(func) =ModeisDeterminismfunc(Mode1) =ModeisDeterminismfunc(Mode1,Mode2) =ModeisDeterminism…

In the case of zero-argument predicates and functions,
the parentheses around ‘`pred`’ and ‘`func`’
are required to tell the compiler that these words
are not being used as operators in this case.
And, as explained above, one will usually need parentheses
around any instances of these patterns in Mercury code.

As a convenience,
the language allows you to write a higher order *mode*
using the same syntax as a higher order *inst*.
If `HOInst` has the form of a higher order inst,
then writing `HOInst` where a mode is required
is the same as writing ‘`in(HOInst)`’,
which is in turn equivalent to ‘`HOInst >> HOInst`’.
Therefore,
you can omit ‘`in()`’ around the higher order inst of an input argument.
For example,

:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.

can also be written as

:- mode foldl(pred(in, in, out) is det, in, in, out) is det.

though the former may be easier to understand.

As usual,
if a predicate or function has only one mode,
the ‘`pred`’ or ‘`func`’ declaration
can be combined with the ‘`mode`’ declaration.
Consider the declaration of a function
that computes the intersection of two maps from keys to values:

:- func intersect(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).

One could declare the mode of this function either using a separate mode declaration, like this:

:- mode intersect(in(func(in, in) = out is det), in, in) = (out) is det.

or by combining the mode declaration with the function declaration, like this:

:- func intersect((func(V, V) = V)::in(func(in, in) = out is det), map(K, V)::in, map(K, V)::in) = (map(K, V)::out) is det.

In both cases, just as for the predicate examples above,
the ‘`in()`’ wrapper around the higher order inst is optional,
though in the combined declaration the parentheses must stay.

Mercury also provides builtin ‘`inst`’ values for use with solver types.
These follow the patterns

any_pred isDeterminismany_pred(Mode) isDeterminismany_pred(Mode1,Mode2) isDeterminism… any_func =ModeisDeterminismany_func(Mode1) =ModeisDeterminismany_func(Mode1,Mode2) =ModeisDeterminism…

See Solver types for more details.

In order to call a higher-order term,
the compiler must know its higher-order inst.
This can cause problems when
higher-order terms are placed into a polymorphic collection type
and then extracted,
since the declared mode for the extraction will typically be `out`

and the higher-order inst information will be lost.
To partially alleviate this problem,
and to make higher-order functional programming easier,
if the term to be called has a function type,
but no higher-order inst information is explicitly provided,
we assume that it has the default higher-order function inst
‘`func(in, …, in) = out is det`’.

As a consequence of this,
a higher-order function term can *only* be passed
where a term with no higher-order inst information is expected
if it can be passed
where a term with the default higher-order function inst is expected.
Higher-order predicate terms can always be passed to such a place,
but there is little value in doing so,
because there is no default higher-order inst for predicates,
and therefore it will not be possible to call those terms.

A higher-order type may optionally specify an inst in the following manner:

(pred) isDeterminismpred(Type::Mode) isDeterminismpred(Type1::Mode1,Type2::Mode2) isDeterminism… (func) = (Type::Mode) isDeterminismfunc(Type1::Mode1) = (Type::Mode) isDeterminismfunc(Type1::Mode1,Type2::Mode2) = (Type::Mode) isDeterminism…

When used as argument types of functors in type declarations, types of this form have two effects. First, for any unification that constructs a term using such an argument, there is an additional mode constraint that the argument must be approximated by the inst. In other words, to be mode correct, a program must not construct any term where a functor has an argument that does not have the declared inst, if one is present.

The second effect is that when a unification deconstructs a ground term to extract an argument with such a declared inst, the extracted argument may then be used as if it had that inst.

For example, given this type declaration:

:- type job ---> job(pred(int::out, io::di, io::uo) is det).

the following goal is correct:

:- pred run(job::in, io::di, io::uo) is det. run(Job, !IO) :- Job = job(Pred), Pred(Result, !IO), % Pred has the necessary inst write_line(Result, !IO).

However, the following would be a mode error:

:- pred bad(job::out) is det. bad(job(p)). % Error: p does not have required mode :- pred p(int::in, io::di, io::out) is det. …

As a new feature, combined higher-order types and insts are only permitted as direct arguments of functors in discriminated unions. So the following examples currently result in errors.

% Error: use on the RHS of equivalence types. :- type p == (pred(io::di, io::uo) is det). :- type f == (func(int::in) = (int::out) is semidet). % Error: use inside a type constructor. :- type jobs ---> jobs(list(pred(int::out, io::di, io::uo) is det)). % Error: use in a pred/func declaration. :- pred p((pred(io::di, io::uo) is det)::in, io::di, io::uo) is det. :- func f(func(int::in) = (int::out) is semidet, int) = int.

Future versions of the language may allow these forms.

If all instances of a given type are expected to use
a single inst or a single mode,
there is a convention where programmers will give that inst or mode
the same name as the type.
This works because types, insts and modes belong to separate namespaces,
so the names do not conflict.
Nonetheless, there is usually no need to define a named mode.
It is clearer to write a mode using ‘`in()`’ or ‘`out()`’
around a named inst.

Previous: Default insts for functions, Up: Higher-order insts and modes [Contents]