 124 Chapter 7 Higher-Order Functions
exists simply provide more meaningful names for min and max. Furthermore, max
and min are referred to as quantiﬁers in addition to the traditional forall and exists
operators.
Just as ran can be used to deﬁne image, sel; can be used to deﬁne filter:
EXAMPLE 7.5
Using the sel Function
filter(p,S) = sel(x::S | p(x))
This application of sel takes every element of S, applies p, and keeps the value from
S if p is satisﬁed.
Possibly the most common use of the sel function is to deﬁne new types. Chapter 8
EXAMPLE 7.6
Using sel to Deﬁne Types discusses how any set can be used as a Rosetta type. All types deﬁned in this and
previous chapters are in fact sets of items. The sel function is used extensively to
deﬁne subtypes of existing types. For example, natural is the subtype of integers
that includes zero and the positive values. The deﬁnition of natural t ype is achieved
natural::subtype(integer) is sel(x::integer|x>=0)
Note the use of the select function to ﬁlter integer to get values greater than or equal
to 0. Most number types are deﬁned in this manner.
7.5 Sequences and Higher-Order Functions
There are two fundamental types of higher-order functions that are useful with
respect to sequences. The ﬁrst includes functions that simply treat the contents of
a sequence as a set. Recall from Chapter 5 that a contents function is deﬁned that
extracts the contents of a sequence as a set. Given a sequence S, its contents can be
extracted as a set using the preﬁx operation ~S. Thus, it is possible to apply any of
the higher-order set functions to sequences. For example, given a sequence S and a
boolean expression P, the set of objects from S satisfying P is deﬁned as:
{sel(x::~S | P(x))}
The contents operator extracts the elements of S as a set and the higher-order sel
function performs the comprehension. Table 7.3 shows how each of the deﬁned
higher-order functions for sets can be applied to sequences using the extraction func-
tion. Like the previous expression, this function evaluates to the subset of items from
S that satisfy P(x).
The second kind of higher-order function treats sequences as sequences generating
new sequences from old sequences. Table 7.4 shows the deﬁnitions of these sequence
functions. Rather than using the set-based higher-order functions, these operations
are deﬁned on sequences directly. The two built-in special operations on sequences
are image and filter.Theimage function takes a sequence and an arbit rar y function
and applies that function to each element in the sequence. To increment the contents
of a sequence and maintain the result as a sequence, the map function is applied as:
image(inc,[1,2,3]) == [2,3,4]; 7.5 Sequences and Higher-Order Functions 125
Table 7.4
Special higher-order functions deﬁned over sequences
Operation Syntax Meaning
Filter filter(P,S) Filter all eleme nts from S
that do not satisfy P
Map image(F,S) Apply F to all elements from S
and return the resulting sequence
Fold Left reduce(P,i,S) Fold left
Fold Right reduce_tail(P,i,S) Fold right
Similarly, the filter function takes a sequence and removes elements that do not
satisfy a predicate. Assuming that the predicate lt3 exists that is true if its argument
is less than three, ﬁltering a sequence for values less than three is achieved by:
filter(lt3,[3,1,2,4]) == [1,2];
Anonymous functions and let forms are particularly useful in conjunction with the
image and ﬁlter operations. It is unlikely that the lt3 function just used will ever
exist in any library. Using anonymous functions, the ﬁltering operation can be imple-
mented as:
filter(<(x::natural)::boolean is x<3>,[3,1,2,4]);
The use of filter is identical in this example, except that the ﬁltering predicate
is deﬁned locally and is discarded after the function is simpliﬁed and resolved. If a
ﬁltering or image function is used repeatedly, the let form is useful for deﬁning a
local function:
let filterFn::<(x::natural)::boolean> be
<(x::natural)::boolean is x<3>
filter(filterFn,[3,1,2,4])
end let;
Again the function is identical, but the local function filterFn is deﬁned in the let
form and is used in the ﬁltering activity. Like the anonymous function deﬁned previ-
ously, filterFn is discarded following the closing of the let form’s scope. It should
be noted that using the let form for local function deﬁnition in this way can be some-
what cumbersome. If filterFn is used repeatedly within the let form, or allowing
the function to have a name increases readability, then the extra syntax is worthwhile.
One application of higher-order functions like exists and forall isaformof
EXAMPLE 7.7
Using Set-Based
Higher-Order Functions on
Sequences
comprehension over sequences. Using the contents extraction operation, one can
extract values from a sequence and perform comprehension. Assume that we have
sequence of integers, S, and we would like to determine if all sequence values are
positive:
allPos(s:sequence(integer))::boolean is
forall(y::(~S) | x>0)

Get System Level Design with Rosetta now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.