2 SML Session September 25, 2007

2.1 List Functions

Constructors:

- 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:

- [];
val it = [] : 'a list
- op::;
val it = fn : 'a * 'a list
- 1::[2];
val it = [1,2] : int list
- "a"::["b"];
val it = ["a","b"] : string list
- 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 "string";
val it = [#"s",#"t",#"r",#"i",#"n",#"g"] : char list
- implode it;
val it = "string" : string

Higher order functions and lists:

- map ~ [1,~2,3,~4];
val it = [~1,2,~3,4] : int list
- map;
val it = fn : ('a -> 'b) -> ('a list -> 'b list)
- map ~;
val it = fn : int list -> int list
- (map ~) [1,~2,3,~4];
val it = [~1,2,~3,4] : int list

foldr & foldl

- foldr;
val it = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
- foldr op:: [4,5] [1,2,3];
val it = [1,2,3,4,5] : int list
- foldl op:: [] [1,2,3,4];
val it = [4,3,2,1] : int list
- 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:

- val (n,s) = (1,"string");
val n = 1 : int
val s = "string" : string
- 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
- 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

fn formal-param:type => body

fn parameter-pattern => body;

(fn parameter-pattern => body) argument

- (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

fn pat-1 => exp-1
 | ...
 | pat-n => exp-n
- 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

def factorial (n:int) {
r:=1;
while (n>1)
r=r*n;
n:=n-1;
end
return r;
}
- 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
factorial(3)
=> 3 * factorial(2)
=> 3 * 2 * factorial(1)
=> 3 * 2 * 1
=> 3 * 2
=> 6
- 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.

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
- 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
- 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