diff options
Diffstat (limited to 'miralib/manual/16')
| -rw-r--r-- | miralib/manual/16 | 174 |
1 files changed, 174 insertions, 0 deletions
diff --git a/miralib/manual/16 b/miralib/manual/16 new file mode 100644 index 0000000..143a27d --- /dev/null +++ b/miralib/manual/16 @@ -0,0 +1,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 + |