124 Chapter 7 Higher-Order Functions
exists simply provide more meaningful names for min and max. Furthermore, max
and min are referred to as quantifiers in addition to the traditional forall and exists
operators.
Just as ran can be used to define image, sel; can be used to define 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 satisfied.
Possibly the most common use of the sel function is to define new types. Chapter 8
EXAMPLE 7.6
Using sel to Define Types discusses how any set can be used as a Rosetta type. All types defined in this and
previous chapters are in fact sets of items. The sel function is used extensively to
define subtypes of existing types. For example, natural is the subtype of integers
that includes zero and the positive values. The definition of natural t ype is achieved
using the follow ing definition:
natural::subtype(integer) is sel(x::integer|x>=0)
Note the use of the select function to filter integer to get values greater than or equal
to 0. Most number types are defined 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 first includes functions that simply treat the contents of
a sequence as a set. Recall from Chapter 5 that a contents function is defined that
extracts the contents of a sequence as a set. Given a sequence S, its contents can be
extracted as a set using the prefix 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 defined 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 defined
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 definitions of these sequence
functions. Rather than using the set-based higher-order functions, these operations
are defined 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 defined 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, filtering 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 filter operations. It is unlikely that the lt3 function just used will ever
exist in any library. Using anonymous functions, the filtering 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 filtering predicate
is defined locally and is discarded after the function is simplified and resolved. If a
filtering or image function is used repeatedly, the let form is useful for defining 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 defined in the let
form and is used in the filtering activity. Like the anonymous function defined 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 definition 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.