1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
_P_a_t_t_e_r_n_ _M_a_t_c_h_i_n_g
The notion of `pattern' plays an important role in Miranda. There are
three contexts in which patterns can be used - in function definitions,
in conformal definitions, and on the left of the `<-' in list
comprehensions. We first explain the general rules for pattern
formation, which are the same in all three contexts.
Patterns are built from variables and constants, using constructors.
Here are some simple examples.
x
3
(x,y,3)
The first pattern is just the variable x, the second is the constant 3,
the last example is built from two variables and a constant, using the
(,,) constructor for 3-tuples. The components of a structured pattern
can themselves be arbitrary patterns, permitting nested structures of
any depth.
A pattern can also contain repeated variables, e.g. `(x,1,x)'. A
pattern containing repeated variables matches a value only when the
parts of the value corresponding to occurrences of the same variable are
equal.
The constructors which can be used in a pattern include those of tuple
formation `(..,..)', list formation `[..,..]', and the constructors of
any user defined Algebraic Type (see separate manual section). In
addition there are special facilities for matching on lists and natural
numbers, as follows.
(Lists) The `:' operator can be used in patterns, so for example the
following three patterns are all equivalent (and will match any 2-list).
a:b:[]
a:[b]
[a,b]
Note that `:' is right associative (see manual section on Operators).
(Natural numbers) It is permitted to write patterns of the form `p+k'
where p is a pattern and k is a literal integer constant. This
construction will succeed in matching a value n, if and only if n is an
integer >=k, and in this case p is bound to (n-k). Example, `y+1'
matches any positive integer, and `y' gets bound to the
integer-minus-one.
Note that the automatic coercion from integer to floating point, which
takes place in expression evaluation, does not occur in pattern
matching. An integer pattern such as `3' or `n+1' will not match any
floating point number. It is not permitted to write patterns containing
floating point constants.
_C_a_s_e_ _a_n_a_l_y_s_i_s
The main use of pattern matching in Miranda is in the left hand side of
function definitions. In the simplest case a pattern is used simply to
provide the right hand side of the function definition with names for
subcomponents of a data structure. For example, functions for accessing
the elements of a 2-tuple may be defined,
fst_of_two (a,b) = a
snd_of_two (a,b) = b
More generally a function can be defined by giving a series of
equations, in which the use of different patterns on the left expresses
case analysis on the argument(s). Some simple examples
factorial 0 = 1
factorial(n+1) = (n+1)*factorial n
reverse [] = []
reverse (a:x) = reverse x ++ [a]
last [a] = a
last (a:x) = last x, if x~=[]
last [] = error "last of empty list"
Many more examples can be found in the definition of the standard
environment (see separate manual section). Note that pattern matching
can be combined with the use of guards (see last example above).
Patterns in a case analysis do not have to be mutually exclusive
(although as a matter of programming style that is good practice) - the
rule is that cases are tried in order from top to bottom, and the first
equation which `matches' is used.
_C_o_n_f_o_r_m_a_l_ _d_e_f_i_n_i_t_i_o_n_s
Apart from the simple case where the pattern is a single variable, the
construction
pattern = rhs
is called a `conformal definition'. If the value of the right hand hand
side matches the structure of the given pattern, the variables on the
left are bound to the corresponding components of the value. Example
[a,b,3] = [1,2,3]
defines a and b to have the values 1 and 2 respectively. If the match
fails anywhere, all the variables on the left are _u_n_d_e_f_i_n_e_d. For
example, within the scope of the definition
(x,x) = (1,2)
the value of x is neither 1 nor 2, but _u_n_d_e_f_i_n_e_d (i.e. an error message
will result if you try to access the value of x in any way).
As a constraint to prevent "nonsense" definitions, it is a rule that the
pattern on the left hand side of a conformal definition must contain at
least one variable. So e.g. `1 = 2' is not a syntactically valid
definition.
_P_a_t_t_e_r_n_s_ _o_n_ _t_h_e_ _l_e_f_t_ _o_f_ _g_e_n_e_r_a_t_o_r_s
In a list comprehension (see separate manual entry) the bound entity on
the left hand side of an `<-' symbol can be any pattern. We give two
simple examples - in both examples we assume x is a list of 2-tuples.
To denote a similar list but with the elements of each tuple swapped
over we can write
[(b,a)|(a,b)<-x]
To extract from x all second elements of a 2-tuple whose first member is
17, we can write
[ b |(17,b)<-x]
_I_r_r_e_f_u_t_a_b_l_e_ _p_a_t_t_e_r_n_s (*)
(Technical note, for people interested in denotational semantics)
DEFINITION:- an algebraic type having only one constructor and for which
that constructor is non-nullary (ie has at least one field) is called a
_p_r_o_d_u_c_t _t_y_p_e. The constructor of a product type is called a `product
constructor'.
Each type of n-tuple (n~=0) is also defined to be a product type. In
fact it should be clear that any user defined product type is isomorphic
to a tuple type. Example, if we define
wibney ::= WIB num bool
then the type wibney is isomorphic to the tuple type (num,bool).
A pattern composed only of product-constructors and identifiers, and
containing no repeated identifiers, is said to be "irrefutable". For
example `WIB p q', `(x,y,z)' and `(a,(b,c))' are irrefutable patterns.
We show what this means by an example. Suppose we define f, by
f :: (num,num,bool) -> [char]
f (x,y,z) = "bingo"
As a result of the constraints of strong typing, f can only be applied
to objects of type (num,num,bool) and given any actual parameter of that
type, the above equation for f MUST match.
Interestingly, this works even if the actual parameter is an expression
which does not terminate, or contains an error. (For example try typing
f undef
and you will get "bingo", not an error message.)
This is because of a decision about the denotational semantics of
algebraic types in Miranda - namely that product types (as defined
above) correspond to the domain construction DIRECT PRODUCT (as opposed
to lifted product). This means that the bottom element of a type such
as (num,num,bool) behaves indistinguishably from (bottom,bottom,bottom).
Note that singleton types such as the empty tuple type `()', or say,
it ::= IT
are not product types under the above definition, and therefore patterns
containing sui-generis constants such as () or IT are not irrefutable.
This corresponds to a semantic decision that we do NOT wish to identify
objects such as () or IT with the bottom element of their type.
For a more detailed discussion of the semantics of Miranda see the
formal language definition (in preparation).
------------------------------------------------------------------------
(*) A useful discussion of the semantics of pattern-matching, including
the issue of irrefutable patterns, can be found in (chapter 4 of) the
following
S. L. Peyton-Jones ``The Implementation of Functional Programming
Languages'', Prentice Hall International, March 1987.
ISBN 0-13-453333-X
|
