Algebraic type definitions

The simplest method of introducing a new data type into a Miranda script
is  by  means of an algebraic type definition.  This enables the user to
introduce a new concrete  data  type  with  specified  constructors.   A
simple example would be
	tree ::= Nilt | Node num tree tree

The  `::='  sign (pronounced `comprises') is always used to introduce an
algebraic data type.  This definition introduces three new identifiers -
`tree', a typename - `Nilt' a nullary constructor of type tree (i.e.  an
atomic tree) - and `Node', a constructor of type  num->tree->tree->tree.
Now  we  can  define  a particular tree, using the constructors Nilt and
Node, for example
	t = Node 3 Nilt Nilt

It is not necessary to have names for the selector functions because the
constructors  can  be  used in pattern matching.  For example a function
for counting the number of nodes in a tree could be written
	size Nilt = 0
	size (Node a x y) = 1 + size x + size y

Note that the names of constructors must begin with an upper case letter
(and  conversely,  any identifier beginning with an upper case letter is
assumed to be a constructor).

An algebraic type can have any number (>=1)  of  constructors  and  each
constructor  can  have any number (>=0) fields, of specified types.  The
number of fields taken by  a  constructor  is  called  its  `arity'.   A
constructor  of  arity zero is said to be atomic.  Algebraic types are a
very general idea and include a number of special cases  that  in  other
languages require separate constructions.

One  interesting case that all of the constructors can be atomic, giving
us what is called in PASCAL a `scalar enumeration type'.  Example
	day ::= Mon|Tue|Wed|Thu|Fri|Sat|Sun

The union of two types can also be represented as an algebraic data type
- for example here is a union of num and bool.
	boolnum ::= Left bool | Right num

Notice  that  this  is  a `labelled union type' (the other kind of union
type, in which the parts of the union are not distinguished  by  tagging
information, is not permitted in Miranda).

An  algebraic typename can take parameters, thus introducing a family of
types.   This  is  done  be  using  generic  type  variables  as  formal
parameters  of the `::=' definition.  To modify our definition of `tree'
to allow trees with different types of labels at the nodes  (instead  of
all `num' as above) we would write
	tree * ::= Nilt | Node * (tree *) (tree *)

Now  we  have  many  different  tree  types  -  `tree num', `tree bool',
`tree([char]->[char])', and so on.  The constructors `Node'  and  `Nilt'
are  both  polymorphic, with types `tree *' and `*->tree *->tree *->tree
*' respectively.

Notice that in Miranda objects of a recursive user defined type are  not
restricted  to  being  finite.   For example we can define the following
infinite tree of type `tree num'
	bigtree = Node 1 bigtree bigtree

Obsolete Language Features
 Algebraic data types in Miranda originally (see Turner 1985)  supported
two additional features, which have now been dropped from the definition
of the language.  These are  laws  (equations  on  constructors  written
using  `=>')  and  strictness annotations on fields in `::=' definitions
(written as ! following the field type).

The release-two compiler continues to support these features, so  former
users  of Miranda release one do not lose working programs at the change
to release two.  However, they will eventually cease to be supported  by
the  Miranda  compiler (sorry!).  An `obsolete feature' warning given at
each compilation of a script using them.  A methodology for  translating
out these features is given in the CHANGES section of this manual.

Laws and strictness annotations  are  no  longer  part  of  the  Miranda
language, and should not be taught to new users.

------------------------------------------------------------------------
Reference: D. A. Turner ``Miranda: A Non-Strict Functional Language with
Polymorphic   Types'',   Proceedings   IFIP   Conference  on  Functional
Programming  Languages  and  Computer   Architecture,   Nancy,   France,
September 1985 (Springer Lecture Notes in Computer Science 201:1-16).

this can be found at http://miranda.org.uk

