import Miranda 2.066 from upstream

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
+