home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / lang / gofer223.lha / doc / ch11 < prev    next >
Encoding:
Text File  |  1992-11-10  |  6.6 KB  |  199 lines
  1.  
  2.  
  3. Introduction to Gofer         11. USER-DEFINED DATATYPES AND TYPE SYNONYMS      
  4.  
  5.  
  6. 11. USER-DEFINED DATATYPES AND TYPE SYNONYMS
  7.  
  8. 11.1 Datatype definitions
  9. -------------------------
  10. In addition to the  wide  range  of  built-in  datatypes  described  in
  11. section 7, Gofer also allows the  definition  of  new  datatypes  using
  12. declarations of the form:
  13.  
  14.      data DatatypeName a1 ... an = constr1 | ... | constrm
  15.  
  16. where DatatypeName is the name of a new type constructor of arity n>=0,
  17. a1, ..., an are distinct type variables representing the  arguments  of
  18. DatatypeName and constr1, ..., constrm (m>=1) describe the way in which
  19. elements of the new datatype are constructed.  Each constr can take one
  20. of two forms:
  21.  
  22.   o  Name type1 ... typer where Name is a previously unused constructor
  23.      function  name  (i.e.  an  identifier  beginning  with  a  capital
  24.      letter).  This declaration introduces Name as  a  new  constructor
  25.      function of type: type1 -> ...-> typer -> DatatypeName a1 ... an.
  26.  
  27.   o  type1 CONOP type2 where CONOP is a previously  unused  constructor
  28.      function  operator (i.e.  an  operator  symbol  beginning  with  a
  29.      colon).  This declaration introduces (CONOP) as a new  constructor
  30.      function of type: type1 -> type2 -> DatatypeName a1 ... an.
  31.  
  32. [N.B. only the type variables a1, ..., an may appear in the type expressions
  33. in each constr in the definition of DatatypeName.]
  34.  
  35.  
  36. As a simple example, the following definition introduces a new type Day
  37. with elements Sun, Mon, Tue, Wed, Thu, Fri and Sat:
  38.  
  39.     data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
  40.  
  41. Simple functions manipulating elements of type Day can be defined using
  42. pattern matching:
  43.  
  44.     what_shall_I_do Sun = "relax"
  45.     what_shall_I_do Sat = "go shopping"
  46.     what_shall_I_do _   = "looks like I'll have to go to work"
  47.  
  48. Another example uses a pair of constructors to provide a representation
  49. for temperatures which may be given using either of the  centigrade  or
  50. fahrenheit scales:
  51.  
  52.     data Temp = Centigrade Float | Fahrenheit Float
  53.  
  54.     freezing                  :: Temp -> Bool
  55.     freezing (Centigrade temp) = temp <= 0.0
  56.     freezing (Fahrenheit temp) = temp <= 32.0
  57.  
  58. The following example uses a type variable on the left hand side of the
  59. datatype  definition  to  implement  a   Set   type   constructor   for
  60. representing sets using a list of values:
  61.  
  62.  
  63.  
  64.                                       46
  65.  
  66.  
  67.  
  68.  
  69. Introduction to Gofer         11.1 Datatype definitions                         
  70.  
  71.  
  72.     data Set a = Set [a]
  73.  
  74. For example, Set [1,2,3] is an element of type  Set  Int,  representing
  75. the set of integers {1, 2, 3} whilst Set ['a'] represents  a  singleton
  76. set of type Set Char.  As this example shows, it is possible to use the
  77. same  name  simultaneously  as  both  a  type  constructor  and  as   a
  78. constructor function.
  79.  
  80. Datatype definitions may also be  recursive,  using  the  name  of  the
  81. datatype  being  defined  on  the  right  hand  side  of  the  datatype
  82. definition  (mutually   recursive   datatype   definitions   are   also
  83. permitted).  The following example is taken from the Haskell report [5]
  84. and  defines  a  type  representing  binary  trees  with  values  of  a
  85. particular type at their leaves:
  86.  
  87.     data Tree a = Lf a | Tree a :^: Tree a
  88.  
  89. For example, (Lf 12 :^: (Lf 23 :^: Lf 13)) :^: Lf 10 has type Tree  Int
  90. and represents the binary tree:
  91.  
  92.                               ,--- 12
  93.                            ,--| 
  94.                            |  |  ,--- 23
  95.                            |  `--| 
  96.                            |     `--- 13
  97.                          --| 
  98.                            `--- 10
  99.  
  100. As an example of a function defined on trees, here are two  definitions
  101. using recursion and pattern matching on tree valued  expressions  which
  102. calculate the list of elements at the leaves of a tree  traversing  the
  103. branches of the tree from left to right.  The first definition  uses  a
  104. simple definition, whilst the second uses an  `accumulating  parameter'
  105. giving a more efficient algorithm:
  106.  
  107.     leaves, leaves'  :: Tree a -> [a]
  108.  
  109.     leaves (Lf l)  = [l]
  110.     leaves (l:^:r) = leaves l ++ leaves r
  111.  
  112.     leaves' t = leavesAcc t []
  113.                  where leavesAcc (Lf l)  = (l:)
  114.                        leavesAcc (l:^:r) = leavesAcc l . leavesAcc r
  115.  
  116. Using the binary tree above as an example:
  117.  
  118.     ? leaves ((Lf 12 :^: (Lf 23 :^: Lf 13)) :^: Lf 10)
  119.     [12, 23, 13, 10]
  120.     (24 reductions, 73 cells)
  121.     ? leaves' ((Lf 12 :^: (Lf 23 :^: Lf 13)) :^: Lf 10)
  122.     [12, 23, 13, 10]
  123.     (20 reductions, 58 cells)
  124.     ?
  125.  
  126.  
  127.  
  128.  
  129.  
  130.                                       47
  131.  
  132.  
  133.  
  134.  
  135. Introduction to Gofer         11.2 Type synonyms                                
  136.  
  137.  
  138. 11.2 Type synonyms
  139. ------------------
  140. Type synonyms are used to provide  convenient  abbreviations  for  type
  141. expressions.  A type synonym is introduced  by  a  declaration  of  the
  142. form:
  143.  
  144.      type Name a1 ... an = expansion
  145.  
  146. where Name is the name of a new type constructor  of  arity  n>=0,  a1,
  147. ..., an are distinct type variables representing the arguments of  Name
  148. and expansion is a type expression.  Note that the only type  variables
  149. permitted in the expansion type are those on the left hand side of  the
  150. synonym definition.  Using this declaration any type expression of  the
  151. form:
  152.  
  153.                   Name type1 ... typen 
  154.  
  155. is treated as an abbreviation of  the  type  expression  obtained  from
  156. expansion by replacing each of the type variables a1, ..., an with  the
  157. corresponding type type1, ..., typen.
  158.  
  159. The most frequently used type synonym is almost  certainly  the  String
  160. type which is a synonym for [Char]:
  161.  
  162.     type String = [Char]
  163.  
  164. [ASIDE: This definition is actually built in to the Gofer  system,  but
  165. the effect is the same as if this  declaration  were  included  in  the
  166. standard prelude.]
  167.  
  168. Note that the types of expressions inferred by Gofer will  not  usually
  169. contain any type synonyms unless an explicit type signature  is  given,
  170. either using an explicitly typed expression (section 10.6)  or  a  type
  171. declaration (section 9.12):
  172.  
  173.     ? :t ['c']
  174.     ['c'] :: [Char]
  175.     ? :t ['c'] :: String
  176.     ['c'] :: String
  177.     ?
  178.  
  179. Unlike the datatype declarations described  in  the  previous  section,
  180. recursive  (and  mutually  recursive)  synonym  declarations  are   not
  181. permitted.  This rules out examples such as:
  182.  
  183.     type BadSynonym = [BadSynonym]
  184.  
  185. And ensures that the process of expanding all of the type synonyms used
  186. in any particular type expression  will  always  terminate.   The  same
  187. property does not hold for the illegal definition above, in  which  any
  188. attempt to expand the type BadSynonym would lead to the non-terminating
  189. sequence:
  190.  
  191.     BadSynonym ==> [BadSynonym] ==> [[BadSynonym]] ==> ....
  192.  
  193.  
  194.  
  195.  
  196.                                       48
  197.  
  198.  
  199.