"if" expression

fun sign x = if (x>0) then 1; // syntax error

fun sign x = if (x>0) then 1; // needs both "then" and "else"
        else ~1; 

fun sign x = case (x>0) of  // equivalent to "if" expression
        true => 1 |
        false => ~1;

fun sign x = case (x>0) of
        true => 1 ;
What does the interpreter say? 
Warning: match nonexhaustive
How does it behave? 
- sign(~10);

uncaught Match exception tests.ml:1.14-2.17

Type checking

fun sign x = case (x>0) of
        true => 1 |
        false => ~1.0;

tests.ml:1.14-3.21 Error: rules don't agree (tycon mismatch)
  expected: bool -> int
  found:    bool -> real
  rule:
    false => ~1.0

Pattern matching

The full syntax of pattern matching ("matches") in ML is as follows. 
 <pattern 1> => <expression 1> |
 <pattern 2> => <expression 2> |
          ....
 <pattern n> => <expression n>
All the expressions should be of the same type. Matches can appear in function expressions, case expressions, and exception handlers. If there exist values that do not match any of the patterns, ML gives a warning. There are some cases where pattern matching does not work as expected. Consider the defintion of the combinations function. The following definition leads to an error. 
fun comb(_,0) = 1
   | comb(n, n) = 1  // invalid pattern
   | comb(n, m) = comb(n-1, m-1) + comb(n-1, m);
Prolog, for example, accepts such a pattern.

Mutual recursion

Suppose you want to define two functions which are mutually recursive. The C approach is to use forward declaration which saves some effort for the compiler. In Java, the functions can be independently defined because the compiler does the job for the user. In ML we have a problem. Even though the compiler does the job for the user, each expression should be complete in itself so that the compiler can evaluate it and return a value. Mutually recursive functions are defined using the keyword and as shown below. 
fun odd n = if (n=0) then false
                  else even(n-1)
   and
even n = if (n=0) then true
              else odd(n-1);

Imperative constructs

let

Full functional evaluation can be sometimes inefficient and also lead to unreadable code. Consider the recursive calculation of integer powers. The pseudocode reads as below. 
   function power(m, n)
      if (0 == n mod 2) return power(m, n/2)*power(m, n/2);
      else return power(m, n/2)*power(m, n/2)*n;
Note that this is inefficient since the subexpression power(m, n/2) is calculated twice. The code becomes difficult to read if the subexpressions have a complicated structure. ML allows local environment using let expression. 
fun power(m, n) =
    if (n=0) then 1
    else if (m=0) then 0
    else
       let 
         val a = power(m, n div 2);
       in if (n mod 2 = 0) then a*a
          else a*a*m
       end;

Statement lists

Sometimes it is helpful to have a sequence of statements, especially when printing. Consider the follwing function. 
fun printList(nil) = print("\n")
   | printList(n::rest) = (
           print(n:int);
           print(" ");
           printList(rest));

Control structures

The only control structure in ML is recursion. Along with higher order functions, it provides many powerful control abstractions.

Mapping

Suppose we want to apply a function to all the members of a list and return a list of results. This is called mapping. As an example, suppose we want to square all the elements of a list. 
[1, 2, 3, 4] -> [1, 4, 9, 16]
The built-in function map does this. But we can write our own definition. 
fun myMap(F, nil) = nil
   | myMap(F, a::rest) = F(a)::myMap(F, rest);

fun square(x:int) = x*x;
myMap(square, [1, 2, 3, 4]);
// result is [1, 4, 9, 16]

Reduction

exception EmptyList;

fun myReduce(F, nil) = raise EmptyList
   | myReduce(F, [a]) = a
   | myReduce(F, a::rest) = F(a, myReduce(F, rest));

fun sum(x, y:int) = x+y;

myReduce(sum, [1, 2, 3, 4]);
// result is 10

Function filter

Suppose we want to collect all the odd members of a list. We have the predicate odd which does this. We need to apply this over the list as shown below. 
fun myFilter(P, nil) = nil
  | myFilter(P, a::rest)
      = if P(a) then a::myFilter(P, rest)
        else myFilter(P, rest);
- myFilter(odd, [1, 2, 3, 4]);
val it = [1,3] : int list

Curried forms

Consider the following function definitions. 
fun sum(x, y:int) = x+y;
fun sumc x y:int = x+y;
Both are valid function definitions. What does ML think of them? 
val sum = fn : int * int -> int
val sumc = fn : int -> int -> int
sum takes a tuple of type int*int as argument and returns int. But sumc is more interesting. It takes an int as argument and returns a function of type int -> int as result. 
- val sumc3 = sumc 3;
val sumc3 = fn : int -> int
- val sum3 = sum 3;
std_in:47.1-47.16 Error: operator and operand don't agree (tycon mismatch)
  operator domain: int * int
  operand:         int
  in expression:
    sum 3
- sumc3(0);
val it = 3 : int
-
This is called partial instantiation. Can we partially instantiate the right side arguments? Consider the examples. 
- fun sumc1 x = sumc x 1;
val sumc1 = fn : int -> int
- fun sum1 x = sum(x, 1);
val sum1 = fn : int -> int
- sumc1(2);
val it = 3 : int
- sum1(2);
val it = 3 : int
-

Other types

The following are the consequences of strong typing and evaluation.

unit

This is similar to void of C. This type has exactly one value. unit is the returned type of print and also the input type of zero argument functions.

option

Suppose we want to define type which can hold values of T but may not hold any value also. For example, when reading a file, we might get an integer or no data (end of file). ML has the datatype option. The type option T has values NONE or SOME t where t is a value of type T

Expression evaluation

An expression can contain variables. When an expression is evaluated, it returns a value. The values for the variables are taken from an environment which holds (, ) pairs. Ideally, the evaluation of an expression should not change the environment. This property is called referential transparency. The expressins also said to be side-effect free. The C expression a++ changes the value of the environment and hence is not referentially transparent.

ML has the facility for function creation. Such functions are associated with two environments: definition environment and activation environment. So a function should always carry its definition environment. The pair (function, defintion environment) is called a closure.

Expressions vs. statements

An expression is evaluated mainly for the value it returns.

A statement is evaluated mainly for the change of binding it effects. So a statement is evaluated for the side effect. Conside the assignment in ML. val x=10; Generally the value returned is not of interest. What is of interest is the binding created. ML minimizes the severity of side effects by making assignment non-destructive.