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

using the follow ing deﬁnition:

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.