2 SML Session September 25, 2007

2.1 List Functions

Constructors:

• the empty list [] (or nil )
• the cons operator ::

- 1::[];
val it = [1] : int list
- 2::it;
val it = [2,1] : int list
- [2,1];
val it = [2,1] : int list

Side note type variables:

• SML supports polymorphic types ; i.e. types containing type variables . Types variables always begin with a prime, e.g.: 'a 'b
• nil and op:: have polymorphic types:

- [];
val it = [] : 'a list
- op::;
val it = fn : 'a * 'a list

• The type of op:: is a pair where the first component may have any type. But once you have chosen a type t then the second component must have as type t list .

- 1::[2];
val it = [1,2] : int list
- "a"::["b"];
val it = ["a","b"] : string list

• ...but:

- 1::["b"];
stdIn:22.1-22.9 Error: operator and operand don't agree [literal]
  operator domain: int * int list
  operand:         int * string list
  in expression:
    1 :: "b" :: nil

String to char list:

• explode converts from string to char list
• implode does the converse

- explode "string";
val it = [#"s",#"t",#"r",#"i",#"n",#"g"] : char list
- implode it;
val it = "string" : string

Higher order functions and lists:

• map applies a function to each element of a list:

- map ~ [1,~2,3,~4];
val it = [~1,2,~3,4] : int list

• Investigate map in more detail:
• map is a cascaded function

- map;
val it = fn : ('a -> 'b) -> ('a list -> 'b list)

• it takes a function of type ('a -> 'b) as argument and
  
  returns a function of type ('a list -> 'b list)

- map ~;
val it = fn : int list -> int list

• So (map ~) is a function that maps lists of integers to list of integers.
• Let's apply it to a list of integers:

- (map ~) [1,~2,3,~4];
val it = [~1,2,~3,4] : int list

foldr & foldl

• foldr evaluates this way:
  
  foldr f s [x1,x2,x3] => f(x1,f(x2,f(x3,s)))

- foldr;
val it = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

• Application example implementing the append function:

- foldr op:: [4,5] [1,2,3];
val it = [1,2,3,4,5] : int list

• foldl evaluates this way:
  
  foldl f s [x1,x2,x3] => f(x3,f(x2,f(x1,s)))

• Application example implementing the reverse function:

- foldl op:: [] [1,2,3,4];
val it = [4,3,2,1] : int list

• If the first argument (the function) of foldl is commutative then foldl and foldr yield the same result:

- foldr op+ 0 [1,2,3,4];
val it = 10 : int
- foldl op+ 0 [1,2,3,4];
val it = 10 : int

2.2 Patterns and Clausal Function Expressions

SML supports pattern matching of expression.

Declaration and pattern matching:

• We already saw pattern matching when we bound a pair of variables to a pair of values

- val (n,s) = (1,"string");
val n = 1 : int
val s = "string" : string

• the pattern is (n,s) is matched against the pair (1,"string") . Thereby n is bound to 1 and s to "string\" .

• example for failure of pattern matching:

- val (n,s) = (1,\"string\", 2);
stdIn:25.1-25.28 Error: pattern and expression in val dec don't agree [tycon mismatch]
  pattern:    'Z * 'Y
  expression:    int * string * int

• Example for a more complex pattern matching:

- val (_,v,l) = (op+,(1,2),[1,2,3]);
val v = (1,2) : int * int
val l = [1,2,3] : int list

Functions and pattern matching

• We introduced the following scheme for anonymous functions:

fn formal-param:type => body

• SML provides another, more general scheme for anonymous functions:

fn parameter-pattern => body;

• Application of such functions to arguments involve pattern matching; i.e. the function will be evaluated iff the argument can be matched against the parameter-pattern

(fn parameter-pattern => body) argument

• example for a successful and failing pattern matching:

- (fn 2::n => n) [2,3,4];
val it = [3,4] : int list
- (fn 2::n => n) [1,3,4];
uncaught exception nonexhaustive match failure
  raised at: stdIn:26.13

Clausal function expressions

• pattern matching becomes particularly interesting when the body of the function depends on the pattern of its argument.
• The general form looks like this

fn pat-1 => exp-1
 | ...
 | pat-n => exp-n

• Each pat-i is a pattern and each exp-i is an expression involving the variables of the pattern pat-i .
• Each component pat=>exp is called a clause , or a rule.
• The entire assembly of rules is called a match.
• Application of a clausal function to a value val proceeds by considering the clauses in the order written. if the pattern match succeeds, evaluation continues with the evaluation of expression exp-i , with the variables of pat-i replaced by their values as determined by pattern matching. Otherwise we proceed to stage i + 1.
• If no pattern matches (i.e., we reach stage n+1), then the application fails with an execution error called a match failure.
• Simple Example:

- val swap = fn [x,y] => [y,x] | x => x;
val swap = fn : 'a list -> 'a list
- swap [1,2];
val it = [2,1] : int list
- swap [1,2,3];
val it = [1,2,3] : int list

2.3 Recursive Functions

A recursive function is a function which calls itself.

factorial the standard example for recursive functions

• Mathematically n !:=1â‹…2â‹…"¦â‹… n
• factorial implemented in imperative programming style with side effects:

def factorial (n:int) {
 r:=1;
 while (n>1)
  r=r*n;
  n:=n-1;
 end
 return r;
}

• With recursive functions and if conditional you never need for, while and do iterations. And you don't have side effects!
• factorial implemented in functional programming style using recursion:

- fun factorial (n:int) = if n=1 then 1 else  n * factorial (n-1);
val factorial = fn : int -> int
- factorial (4);
val it = 24 : int

• Let's look inside the computation of factorial (3) :

factorial(3)
=> 3 * factorial(2)
=> 3 * 2 * factorial(1)
=> 3 * 2 * 1
=> 3 * 2
=> 6

• Redefinition of factorial with the clausal definition form:

- fun factorial 0 = 1 | factorial (n:int) = n * factorial (n-1);
val factorial = fn : int -> int
- factorial (4);
val it = 24 : int

More recursive functions involving lists and vectors.

• upto

fun upto (m,n) = if m>n then nil else m::upto(m+1,n);
- upto(3,6);
val it = [3,4,5,6] : int list

• mymap

- fun mymap (f, nil) = nil
    | mymap (f, h::t) = (f h) :: mymap (f,t);
val mymap = fn : ('a -> 'b) * 'a list -> 'b list
- mymap(~,[1,2,3]);
val it = [~1,~2,~3] : int list

• flatten

- fun flat [] = [] 
  | flat (l::ls) = l @ flat ls;
= val flat = fn : 'a list list -> 'a list
- flat [["When","shall"],["we","three"],["meet","again"]];
val it = ["When","shall","we","three","meet","again"] : string list