Introduction to ML

ML on ieng9

$ prep cs130w   // from the shell, include sml in your path
$ sml // command to start ML interpreter
Standard ML of New Jersey, Version 0.93, February 15, 1993
val it = () : unit
- 10;   // type "10" followed by a semicolon.
val it = 10 : int // ML returns 10 and also the type of 10: "int"
- 10.0;
val it = 10.0 : real // ML knows that 10.0 is "real"
- val x=10;
val x = 10 : int  // classic variable initialization?
- val x=10.0;     // classic variable update? NO!
val x = 10.0 : real
- ~10.0;  // for negative numbers, use ~ instead of -
val it = ~10.0 : real
- 

Values

Variables

- val a=10;
val a = 10 : int
- fun timesA(x) = a*x; // "a" is a "global" variable.
val timesA = fn : int -> int
- timesA(1);
val it = 10 : int
- val a=20.0;
val a = 20.0 : real
- timesA(1);  // old value of "a" is not forgotten, but just buried
val it = 10 : int
- 

Data types

Tuples

- val book=("Sethi", "PL", 24.99); // record initialization
val book = ("Sethi","PL",24.99) : string * string * real
- #1(book); // field access: functional notation
val it = "Sethi" : string

Lists

- val ilist=[1, 2, 3, 4]; // initialize
val ilist = [1,2,3,4] : int list
- val a::rest=ilist; // pattern matching!
val a = 1 : int
val rest = [2,3,4] : int list
- val a::b::list=ilist; // more pattern matching
val a = 1 : int
val b = 2 : int
val list = [3,4] : int list
- val jlist=[7, 8, 9];
val jlist = [7,8,9] : int list
- klist = ilist@jlist; // concatenation of lists, oops
std_in:21.1-21.5 Error: unbound variable or constructor: klist
- val klist=ilist@jlist; // make sure you use "val"
val klist = [1,2,3,4,7,8,9] : int list
- val llist=0::klist; // list constructor operator is ::
val llist = [0,1,2,3,4,7,8,9] : int list
- 

Enumerated

- datatype opr = SUM | DIFF | MUL | DIV | EXP;  // definition
datatype  opr   // ML returns a handful
  con DIFF : opr // alpabetic order
  con DIV : opr
  con EXP : opr
  con MUL : opr
  con SUM : opr
- val x=SUM;   // you can use them in (programming) assignment!
val x = SUM : opr
- 

Union

- datatype expr = One | N | Node of opr*expr*expr;
datatype  expr
  con N : expr    // note that the order of return is different
  con Node : opr * expr * expr -> expr
  con One : expr
- val e1=Node(SUM, One, N); // construction of a value
val e1 = Node (SUM,One,N) : expr
- val e2=Node(MUL, e1, N); // embedding or recursive construction
val e2 = Node (MUL,Node (SUM,One,N),N) : expr // ML expands it for you.
- 
Functions
 Function definitions and function applications.
- fun twice(x) = 2*x;    // function defintion
val twice = fn : int -> int // function type inferred
- twice(10); // function application
val it = 20 : int
- twice(10.0); // type mismatch
std_in:31.1-31.11 Error: operator and operand don't agree (tycon mismatch)
  operator domain: int
  operand:         real
  in expression:
    twice (10.0)
- 

 Recursive functions
- fun length(nil) = 0   // calculate the length of a list
=          | length(_::rest) = 1+length(rest);
val length = fn : 'a list -> int // what is the type of this function?
- length(nil); 
val it = 0 : int
- length([1,2,3]);
val it = 3 : int

Recursive evaluation of expr: see the example code
Higher-order functions
Functions as argument
- fun inc(x) = x+1; // increment function, nothing fancy
val inc = fn : int -> int
- fun dec(x) = x-1; // decrement function, nothing fancy yet
val dec = fn : int -> int
- fun funIn(f, x) = f(x);  // takes function "f" as argument
val funIn = fn : ('a -> 'b) * 'a -> 'b // NOTE the type
- funIn(inc, 10);
val it = 11 : int
- funIn(dec, 10);
val it = 9 : int
- 

Functions as result
- fun funOut(x) = if (x>0) then inc else dec; // returns a function as result
val funOut = fn : int -> int -> int // NOTE the type
- funOut(1); // returns a function, but how to use it?
val it = fn : int -> int
- val a=funOut(1); // you can assign the returned function
val a = fn : int -> int
- a(10); // and then use it
val it = 11 : int
- val b=funOut(~1);
val b = fn : int -> int
- b(10);
val it = 9 : int
- 

Function composition
- fun twice(x) = 2*x; // vanilla function defintion
val twice = fn : int -> int
- fun square(x) = x*x; // ML needs more info
std_in:50.18 Error: overloaded variable cannot be resolved: *
- fun square(x:int) = x*x;
val square = fn : int -> int // another vanilla
- val f1=twice o square; // compose functions using "o"
val f1 = fn : int -> int
- val f2=square o twice; // compose the other way
val f2 = fn : int -> int
- f1(3);
val it = 18 : int
- f2(3);
val it = 36 : int
// define funAdd which adds two input functions
- val f3=funAdd(square, twice); // can you write the defintion of funAdd?
val f3 = fn : int -> int
- f3(10);
val it = 120 : int

Summary

 functional language
 side-effect freedom
 higher-order functions
 polymorphism
 abstract data types
 recursion
 rule-based programming
 strong typing and type inferencing