ML: Basic Data Types and Function Declarations

remote login to classroom.cs.unc.edu   
   (use ssh, get it from software.unc.edu)

type /usr/bin/sml

  in your shell
  or alter your path to look in /usr/bin 

type sml

• run "sml" and type in expressions for immediate evaluation
• sml < sourceProg (where the source program is in a file "sourceProg")
• use("sourceProg") typed at the interpreter prompt

basic types:  int, real, string, char, boolean

type constructors: list, tuple, function
                   list    *      ->           (syntax in type expressions)

logical ops: orelse, andalso, not
numeric negation in ~  (not - as in most languages)

orthogonality... all types in ML are first class 

tuples: like records, heterogeneous element types
        finite, fixed length
  #2(10,11,12)             gives 11
  #3(#"a","xyz",25.3)      gives 25.3

     #"a"  is the syntax for the single char "a" as opposed to a string
           in newer versions of SML (PC version)

lists
  [1,2,3]  sortof like a tuple, but homogeneous (all elements of the same type)
           length can change as you add elements
  ::   cons operator... combine element and list 1::[2,3]
  @    concat operator... combine two lists [1,2]@[3,4,5]
  hd, tl   head, tail for lists (old LISP "car", "cdr")

explode("abcde") --> ["a", "b", "c", "d", "e"]
implode(["1", "2", "3"]) --> "123"

Typing

ML is strongly typed... no type conversions or coercions done for you

ML does type inference... programmer rarely has to give type information
   or type declarations

identifiers are not bound to specific types... you are free to
  rebind identifiers to values that have different types

scope...
  there is a top level environment containing the types, functions, etc.
  of the "standard basis"

  environment is a set of bindings... name bound to value
     you can think of this as a Perl hash, or a Python dictionary
     however, order of binding creations is important
     a new binding to a name hides older ones to the same name
        but it does not destroy them

  bindings are added to the environment as computations progresses

  computation is nothing more than evaluating expressions
     some expressions produce functions as their values 
        (i.e., function definition, or declaration)
     some expressions have side effects that we really want and
        we don't care about the value produced by evlauation
        (i.e., print, output)

fun sq(x) = x*x ;  <-- error... type system cannot tell if * is int or real

fun sq1(x:real) = x*x ;

fun sq2(x) = (x:real)*x ;

- sq1 = sq2 ;
!!!

try this

   val x = 5;
   fun wow z = z + x;
   wow 9;
   val x = 10;
   wow 9;

this shows something of how bindings work...

fun rev L = 
  (* note use of list operators *)
  (* note comments in ML *)
  if L = nil then nil
  else rev( tl(L)) @ [hd(L)] ;
    >> val rev = fn : ''a list -> ''a list

this introduces equality types
some ML types can be compared for equality, some cannot
full "polymorphism" is a function that allows ANY type as argument

    >> val rev = fn : ''a list -> ''a list

    here the ''a  is a type variable, but the '' means it is 
    restricted to being an equality type

functions, for example, are not equality types... try  
- rev = rev ;
!!!

reals are not equality types in the new versions of SML
  (but this works... 2.3 <= 2.3 andalso 2.3 >= 2.3
       this works...   x <= y   andalso   y <= x   )

int, string, boolean are equality types
list, tuple are equality types if their elements are equality types

   try  (2,14) = (2,14)
   try  (2,14.3) = (2,14.3)

   try  [2.4, 4.5, 6.0] = [2.4, 4.5, 6.0]
   try  [2.4, 4.5, 6.0] = [2.4, 4.5, 6.1]

fun rev L = 
  (* note use of list operators *)
  (* note comments in ML *)
  if null(L) then nil
  else rev( tl(L)) @ [hd(L)] ;
    >> val rev = fn : 'a list -> 'a list


and there is still another way... with patterns... to follow

By the way... let's look at this if/then/else expression

all expressions have types... the type of the value produced when
the expression is evaluated

    if (someBool) then 5 else 14.7

what is the type?  What is the type of the value produced?

In ML the "then" expression and the "else" expression must
have the same type, and the type of the entire "if" is that type.

There must always be an "else"

    if (someBool) then 5 ;

What type would this produce?  Not legal...

mutual recursion (forward declarations)
  
  fun take(L) = 
     (* picks off every other list elt, starting with first *)
     if L=nil then nil else hd(L)::skip(tl(L))
  and skip(L) = 
     (* picks off every other list elt, skips first *)
     if L=nil then nil else take(tl(L)) ;

pattern matching
  an alternative to the "if...then...else" style of fun def 
  we have seen so far

  we can define a function based on patterns its parameters might have
  this is essentially defining a function as a 
     sequence of partial functions

  x::xs is common pattern... matches any non-empty list (has a hd)

  cannot use one var twice in one pattern:
     x::x::xs  to say first two elts are the same... NO
     x::y::zs  must be used and x=y enforced in code

  fun rev(nil) = nil
    | rev(x::xs) = rev(xs) @ [x] ;
    >> val rev = fn : 'a list -> 'a list

    here, the alternatives ("|") are checked in order defined
    until one is found where the parameter pattern matches the
    arguments during evaluation

    Note this form of definition does not require equality types!!
    since there is no "L = nil" comparison in the code.
    Note the types... earlier form is

       >> val rev = fn : ''a list -> ''a list

    whereas this form with patterns in the definition is

       >> val rev = fn : 'a list -> 'a list   
 
    Try creating a list containing functions (not an eq type)
    and then apply each form of fun "rev" to the list... one
    works, one doesn't.  

Pattern example
polynomial arithmetic

   (* add poly P to poly Q *) 
   fun pa (P,nil) = P
    |  pa (nil,Q) = Q
    |  pa ((p:real)::ps, q::qs) = (p+q)::pa(ps,qs);

   (* mult poly P by scalar q *) 
   fun sm (nil,q) = nil
    |  sm ((p:real)::ps,q) = (p*q)::sm(ps,q);

   (* mult poly P by poly Q *)
   fun pm (P,nil) = nil
    |  pm (P,q::qs) = pa(sm(P,q), 0.0::pm(P,qs));

Here the input data format is this:

  x^2 + 5x - 7.2   -->  [~7.2, 5.0, 1.0]

"as" giving names to patterns

  (* merges two sorted lists, sorted smallest first *)
  fun merge(nil,M) = M
   |  merge(L,nil) = L
   |  merge(L as x::xs, M as y::ys) =
        if (x:int) < y then x::merge(xs,M)
        else y::merge(L,ys) ;

Use of "_" as don't-care wildcard
Each occurrance means a different variable

   consider computing "n choose m"

   fun comb(_,0) = 1
    |  comb(n,m) = 
         if m=n then 1
         else comb(n-1,m) + comb(n-1,m-1);

What can be a pattern?
  x::xs
  tuples and lists also

  (* sums all integers found in list of pairs *)
  fun sumPairs (nil) = 0
   |  sumPairs ((x,y)::zs) = x + y + sumPairs(zs) ;


  (* takes list of int lists, sums all integers *)
  fun sumLists (nil) = 0
   |  sumLists (nil::YS) = sumLists(YS)
   |  sumLists ((x::xs)::YS) = x + sumLists(xs::YS) ;

Subtle pattern bug

fun reverse(niil) = nil
 |  reverse(x::xs) = reverse(xs) @ [x] ;

Here, the misspelling leads to a pattern that matches anything...
this is ok, you get overlapping patterns... ML trys to match
arguments to patterns in the order they are declared.

SURPRISE ... 
up to now we have only seen function definitions with ONE parameter.

   fun rev (L) = 
     if L = nil then nil
     else rev( tl(L)) @ [hd(L)] ;

     >> here, the ONE parameter is a tuple with one elt, the list L

   fun plus (a:int, b) = a + b ;

     >> here, the ONE argument is a tuple (a,b) and you are using
        patterns to locally bind names to parts of the pattern

   try this for clarity:
     fun plus (T as (a:int,b)) = #1 T + #2 T ;
       or
     fun plus (T as (_:int,_)) = #1 T + #2 T ;

Curried functions

  fun add(x,y) = x+y : int;
  >> val add = fn : int * int -> int

  see, the domain of the ONE argument is int * int, a tuple

  fun add x y = x + y : int ;
  >> val add = fn : int -> int -> int
     think fn: int -> (int -> int)

  here, it says add is a "partial function" of one argument,
  that produces another function of one argument.

  add 2 3;
  >> val it = 5 : int

  add 2;
  >> val it = fn : int -> int
  it 3;
  >> val it = 5 : int