Fancier Types


1. algebraic datatypes

2. records

3. polymorphic types


Datatypes

   - discriminated unions  (sums)

   - recursive types

   - parameterized


A simple, nonrecursive datatype

   datatype intorbool = INT of int | BOOL of bool

   INT 3  : intorbool

   BOOL true  : intorbool

   fun foo (INT x) = x + 1
     | foo (BOOL y) = if y then 2 else 3

   foo : intorbool -> int

   fun isInt (INT _) = true
     | isInt _ = false

   ------
   Here are some standard ones:

   datatype bool = true | false
   datatype order = LT | EQ | GT    (* structure General, returned by compare functions *)
   datatype 'a option = NONE | SOME of 'a


Recursive datatype

   datatype stack = EMPTY | PUSH of int * stack

   val s = PUSH(1, PUSH(2, EMPTY))  :  stack

   exception EMPTYSTACK

   fun pop(PUSH(n,s)) = s
     | pop _ = raise EMPTYSTACK

   fun top(PUSH(n,_)) = n

   fun isEmpty EMPTY = true
     | isEmpty _ = false


Parameterized recursive datatype

   datatype 'a tree = Node of 'a * 'a tree * 'a tree
                    | Leaf

   val t1 = Node (3, Leaf, Leaf)  : int tree
   val t2 = Node ("a", Leaf, Leaf) : string tree
   val t3 = Node (true, t1, t2)  :  ?


Case expressions -- pattern matching over datatypes, tuples, etc.

   case t
     of EMPTY => 3
      | NODE(n,t1,t2) => n+1     (t : int tree)


   fun append (list1, list2) = 
       case (list1, list2)
         of (_, nil) => list1
          | (nil, _) => list2
          | (x::xs, ys) => x :: append(xs, ys)


------------------------------------------------------------
Records: like tuples, only components are labeled

    type date = int * int * int

     -- which is the day, which is the month, which is the year
        e.g. American style or European?

    Better to use a record type, which can be "self-documenting":

    type date = {day: int, month: int, year: int}

    val today = {day=5, month=4, year=2010}
    val today = {month=4, year=2010, day=5}


    fun getMonth (d: date) = #month d       -- label selector

    fun getMonth {day=d,month=m,year=y} = m

    fun getMonth {day,month,year} = month

    -- this kind of record pattern is just an abbreviation for

        fun getMonth {day=day,month=month,year=year} = month

       where each label is duplicated to produce a bound variable
       for the field with the same name as the label.


    fun getMonth ({month,...}: date) = month

    -- this kind of abbreviation allows a record pattern to just
       mention the field or fields that are relevant, representing
       the missing fields by "...".  This only works where the 
       exact record type is known, hence in this case we aupply
       the ": date" type annotation (aka a type "ascription").


We often use records in conjunction with datatypes, again because
it makes the types more self-documenting:

    datatype exp
      = APP of exp * exp
      | ABS of var * exp


    datatype exp
      = APP of {oper: exp, arg: exp}
      | ABS of {boundvar: var, body: exp}



------------------------------------------

Polymorphism

We start by describing the type "inferrence" algorithm used
in ML (& Haskell).  See the pdf for the typing slides.