# SML, Some Basic Examples

## Simple arithmetic expressions and format

The amount of white space between tokens does not matter. Expressions can be entered on multiple lines;
```- 2+3;
val it = 5 : int

- 7-4;
val it = 3 : int
```
```- 5 *                          3                 ;
val it = 15 : int

- 5 * 3 ;
val it = 15 : int

- 5*3;
val it = 15 : int
```
```- 6
= -1
= ;
val it = 5 : int
```

Canonical values evaluate to themselves.

```- 6;
val it = 6 : int

- 11;
val it = 11 : int
```

## Examples of the simple data types

ML has a rich collection of data types. We can divide the collection of data types into three categories.
• basic data types; ML has six basic data types: integer, string, character, boolean, real, and unit.
• structured data types; Type operators combine types to form structured, or compound, types. We talk about three built-in type operators: tuples, records, and lists. There is another built-in type operator for functions.
• user-defined types; The user-defined data types are reminiscent of variant record types found in other programming languages. Typically variant records are not used much in other programming languages, but user-defined types are quite important to programming in ML. They are quite general and encompass enumerated types as well.

### Integer, String, Character, Boolean, Real, Unit

```- 2+3; 4-5; 6*7;
val it = 5 : int
val it = ~1 : int
val it = 42 : int

- ~5;            (* unary negation *)
val it = ~5 : int

- 37 div 5; 37 mod 5;
val it = 7 : int
val it = 2 : int

- (3+4)*2;
val it = 14 : int

- Int.min (2+3, 2-3);  (* "min" is an operation from the "Int" module *)
val it = ~1 : int

- "this is a string";
val it = "this is a string" : string

- size "string";
val it = 6 : int

- size "";
val it = 0 : int

- "abc" ^ "defg";
val it = "abcdefg" : string

- #"A"; #"B";
val it = #"A" : char
val it = #"B" : char

- true; false;
val it = true : bool
val it = false : bool

- not true;       (* boolean negation *)
val it = false : bool

- not false;
val it = true : bool

- if true then "then" else "else";
val it = "then" : string

- if false then if true then 1 else 2 else if false then 3 else 4;
val it = 4 : int

- if true then 2 else 37 div 0;
val it = 2 : int

- if false then 37 div 0 else 3;
val it = 3 : int

- 2=2 orelse 37 div 0 = 5;
val it = true : bool

- 2=0 andalso 37 div 0 = 5;
val it = false : bool

- 1=1;
val it = true : bool

- 2=4;
val it = false : bool

- "string" = "string";
val it = true : bool

- if 1=2 then 3 else 4;
val it = 4 : int

- 3.14159;        (* an approximation of pi *)
val it = 3.14159 : real

- 123.456E7;
val it = 1234560000.0 : real

- 1.2 + 3.4;      (* '+' overloaded: int and real *)
val it = 4.6 : real

- 1.2 - 3.4;
val it = ~2.2 : real

- 1.2 * 3.4;
val it = 4.08 : real

- 7.2 / 4.8;
val it = 1.5 : real

- 3.1415926535;      (* an approximation of pi *)
val it = 3.1415926535 : real

- 2.7182818284;
val it = 2.7182818284 : real

- Math.e;
val it = 2.71828182846 : real

- Math.cos (Math.pi/2.0);
val it = 0.0 : real

- Math.sqrt (49.01);
val it = 7.00071424927 : real

- Int.min (ceil 3.4, floor 3.4);
val it = 3 : int

- ();
val it = () : unit
```

### Tuples, Records, Lists

#### Tuples

Tuples are structured data types of heterogeneous elements listed in order.
```- (true, (), 1);
val it = (true,(),1) : bool * unit * int

- (2, "ab", 2*2, 5.0);
val it = (2,"ab",4,5.0) : int * string * int * real

- ( 2 );    (* No such thing as a one-tuple *)
val it = 2 : int

- ((()));
val it = () : unit

- ((2,3,4), (true,3.3));
val it = ((2,3,4),(true,3.3)) : (int * int * int) * (bool * real)

- #2 ("one", 2, "three");  (* projection *)
val it = 2 : int
```

#### Records

Records are structrured data types of heterogeneous elements that are labeled. The labels allow elements to be written in any order.
```- {abscissa=1.2, ordinate=3.2};
val it = {abscissa=1.2,ordinate=3.2} : {abscissa:real, ordinate:real}

- {make="Toyota", model="Corolla", year=1986, color="silver"};
val it = {color="silver",make="Toyota",model="Corolla",year=1986}
: {color:string, make:string, model:string, year:int}

- {x_dim=2, y_dim=3} = {y_dim=3, x_dim=2}; (* order irrelevant *)
val it = true : bool

- {a = (), b = 2, c = ("s",2), d = 1};
val it = {a=(),b=2,c=("s",2),d=1} : {a:unit, b:int, c:string * int, d:int}

- {a = 2.3, b = {a="s",c=45}};
val it = {a=2.3,b={a="s",c=45}} : {a:real, b:{a:string, c:int}}

- {one = (2.3, "string")};
val it = {one=(2.3,"string")} : {one:real * string}

- {1=(), 2=true, 3=1};   (* n-tuples are records *)
val it = ((),true,1) : unit * bool * int

- {1=(), 3=1, 2=true};
val it = ((),true,1) : unit * bool * int

- {1=(), 3=1};
val it = {1=(),3=1} : {1:unit, 3:int}

- {34564=1, b=2, b3=3, <*> =4};
val it = {34564=1,<*>=4,b=2,b3=3} : {34564:int, <*>:int, b:int, b3:int}

- {1=1, 01=01, 001=001}            (* Error! *)
stdIn:23.5-23.10 Error: syntax error: deleting  COMMA INT0 EQUALOP

- #a {a=3};                  (* field selection *)
val it = 3 : int

- # a{z=1.2, a=3, b=true, 4=()};
val it = 3 : int

- #a (#b {b={a=3}});
val it = 3 : int

- let val r = {r=3} in # r r end;
val it = 3 : int

- let val ### = 3 in # ## {## = ###} end;
val it = 3 : int
```
Numbers are allowed as labels in ML records. And these make it possible to treat tuples as as special case of records. The case where the labels are implicit with numbers in order.

#### Lists

All elements of a list have the same type.
```- [1,2,3,4];
val it = [1,2,3,4] : int list

- [true,false,false];
val it = [true,false,false] : bool list

- ["a","bc","def","ghij"];
val it = ["a","bc","def","ghij"] : string list

- [(8,true),(5,false)];
val it = [(8,true),(5,false)] : (int * bool) list

- [1,2,3.14159,4];   (* Error! *)
stdIn:17.1-17.16 Error: operator and operand don't agree [literal]
operator domain: real * real list
operand:         real * int list
in expression:
3.14159 :: 4 :: nil

- 1 :: [2,3,4]; 1 :: 2 :: [3,4];  (* binary, infix "cons" op *)
val it = [1,2,3,4] : int list
val it = [1,2,3,4] : int list

- [1,2,3] @ [4,5];                (* binary, infix append op *)
val it = [1,2,3,4,5] : int list

- [("abcd", 4), ("xyz", 3)];
val it = [("abcd",4),("xyz",3)] : (string * int) list

- (["abcd", "xyz"], [4, 3,2,1]);
val it = (["abcd","xyz"],[4,3,2,1]) : string list * int list

- [[2,4,6], [2,3,5,7], [2,4,8,16,32]];
val it = [[2,4,6],[2,3,5,7],[2,4,8,16,32]] : int list list
```
The notation with the square brackets is just a special syntax of building up lists using the constructors `::` and `nil`.
```- 1::2::3::4::nil;
val it = [1,2,3,4] : int list

- true::false::false::nil;
val it = [true,false,false] : bool list

- "a"::"bc"::"def"::"ghij"::nil;
val it = ["a","bc","def","ghij"] : string list

- (8,true)::(5,false)::nil;
val it = [(8,true),(5,false)] : (int * bool) list

- (2::4::6::nil) :: (2::3::5::7::nil) :: (2::4::8::16::32::nil) :: nil;
val it = [[2,4,6],[2,3,5,7],[2,4,8,16,32]] : int list list
```
It is important in SML to distinguish constructors from ordinary functions. Constructors are the primitive functions that create new values of a data. For example, the constructors for lists are `::` and `nil`. The append function `@` is not a constructor (it can be defined using `::` and `nil`).

## Bindings

Values can be bound to names using value declarations. Value declarations are introduced by the keyword val.
```- val a = 2;            (* Bind the value 2 to a.               *)
val a = 2 : int

- a;                    (* Respond with the value of a.         *)
val it = 2 : int

- 3*a + 4*a*a;          (* Use the value of a in an expression. *)
val it = 22 : int

- val b = 3 * 4 + 5;
val b = 17 : int

- val c = 2 * b;        (* Use value of b in binding of c.      *)
val c = 34 : int

- val a = 3;          (* This binding hides previous bindings.  *)
val a = 3 : int

- a;                  (* Respond with value of visible binding. *)
val it = 3 : int

- val <=> = (~1,0,1);              (* A symbolic identifier <=> *)
val <=> = (~1,0,1) : int * int * int

- 6*5*4;            (* Expressions are really bindings to "it". *)
val it = 120 : int

- val c = it div (3*2);
val c = 20 : int

- it;
val it = 120 : int

- val a = 4;                         (* Global binding to a.    *)
val a = 4 : int

- let val a = 5 in a+6 end;          (* Local binding to a.     *)
val it = 11 : int

- a;                                 (* No change in a.         *)
val it = 4 : int

- let val p = 87187 * 3797 in (p, p+2, p+4) end;
val it = (331049039,331049041,331049043) : int * int * int

- val pi2 = let val pi = 3.14 in 2.0 * pi end;
val pi2 = 6.28 : real
```
```- local
=   val pi = 3.14
= in
=   val pi2 = 2.0 * pi
= end;
val pi2 = 6.28 : real

- val a = 0 and b = 1 and c = 7.8;
val a = 0 : int
val b = 1 : int
val c = 7.8 : real

- let
=   val c = 3 and d = 4    (* Two local, independent bindings.  *)
= in
=   (c * d) div 3
= end;
val it = 4 : int

- let val e = 5 and f = e+1 in e+f end;  (* Error! *)
stdIn:24.23 Error: unbound variable or constructor: e

- let
=   val c = 3; val d = c+1;     (* These bindings are dependent *)
= in
=   (c * d) div 3
= end;
val it = 4 : int

- let
=   val c = 3
= in
=   let val d = c+1 in (c * d) div 3 end
= end;
val it = 4 : int
```

## Patterns

An unsual feature of SML is that declarations are not simply bindings to identifiers, but bindings to all the identifiers in a pattern. This permits data strucutures to be picked apart and is especially useful in defining functions (as seen later).
```- val (fst, snd) = (4, 4.45);
val fst = 4 : int
val snd = 4.45 : real

- val (a,b,c) = (1,3,6);  (* Matching in declaration *)
val a = 1 : int
val b = 3 : int
val c = 6 : int

- val {1=a, 2=b, 3=c} = {1=1,2=3,3=6};
val a = 1 : int
val b = 3 : int
val c = 6 : int

- val {abscissa=x, ordinate=y} = {abscissa=1.2, ordinate=3.2};
val x = 1.2 : real
val y = 3.2 : real

- val {abscissa=x, ordinate=y} = {ordinate=3.2, abscissa=1.2};
val x = 1.2 : real
val y = 3.2 : real

- val {b=x, ...} = {a=2, b="s", c=3.4, d=[1,2]};
val x = "s" : string

- val {2=x, ...} = (1,2,3);
val x = 2 : int

- val {frac=x, ...} = Real.split 37.4321;
val x = 0.4321 : real

- val x = 3;
val x = 3 : int

- val (x,x) = (2,3);                     (* Error! *)
stdIn:22.1-22.18 Error: duplicate variable in pattern(s): x

- val (head::rest) = 3*4;                (* Error! *)
stdIn:1.1-2.18 Error: pattern and expression in val dec don't agree [literal]
pattern:    'Z list
expression:    int
in declaration:
(case (3 * 4)

- val (head::rest) = [1,2,3] @ [4,5,6];
stdIn:1.1-2.32 Warning: binding not exhaustive
val head = 1 : int
val rest = [2,3,4,5,6] : int list

- val (head::rest) = [] @ (tl [1]);      (* Runtime error!   *)
stdIn:23.1-23.33 Warning: binding not exhaustive

uncaught exception nonexhaustive binding failure
raised at: stdIn:23.1-23.33

- val (x,_,y) = (1,2,3);                 (* wildcard pattern *)
val x = 1 : int
val y = 3 : int

- val (x,_,y,_) = (1,2,3,4);
val x = 1 : int
val y = 3 : int

- val head :: _ = [1, 2, 3];
stdIn:25.1-25.26 Warning: binding not exhaustive
val head = 1 : int

- val x as (fst,snd) = (2, true);        (* layered pattern   *)
val x = (2,true) : int * bool
val fst = 2 : int
val snd = true : bool

- val list as head :: tail = [1, 2, 3];
stdIn:27.1-27.37 Warning: binding not exhaustive
list as head :: tail = ...
val list = [1,2,3] : int list
val head = 1 : int
val tail = [2,3] : int list

- val (x,1) = (7,1);
stdIn:28.1-28.18 Warning: binding not exhaustive
(x,1) = ...
val x = 7 : int

- val 1 = 1;
stdIn:29.1-29.10 Warning: binding not exhaustive
1 = ...

- val 1 = 2;                (* Runtime error! *)
stdIn:30.1-30.10 Warning: binding not exhaustive
1 = ...

uncaught exception nonexhaustive binding failure
raised at: stdIn:30.1-30.10

- val (x,y,_)::_ = [(2,3,4),(5,6,7)];
stdIn:1.1-2.30 Warning: binding not exhaustive
(x,y,_) :: _ = ...
val x = 2 : int
val y = 3 : int
```
Only certain functions, constructors, can be used in patterns. `::` is a constructor, hence it can be use in a pattern. `@` is not. Neither is `+`.

## Functions

```- (fn x => x+1);       (* A function object: successor function *)
val it = fn : int -> int

- val f = (fn x => x+1);  (* Bind f to the successor function   *)
val f = fn : int -> int

- f;
val it = fn : int -> int

- f (2);                 (* Function application               *)
val it = 3 : int

- f 2;                   (* Parens not needed, if arg a token. *)
val it = 3 : int

- 3 2;                   (* Type error!  *)
stdIn:18.1-18.4 Error: operator is not a function [literal]
operator: int
in expression:
3 2

- f (true);              (* Type error!  *)
stdIn:1.1-2.4 Error: operator and operand don't agree [tycon mismatch]
operator domain: int
operand:         bool
in expression:
f true

- f 2 * 4;               (* Application binds tightest.        *)
val it = 12 : int

- (fn x => x+1) 8;       (* Name not needed to apply to arg    *)
val it = 9 : int

- val f = (fn n => n+1); (* Definition of the function f.      *)
val f = fn : int -> int

- fun f (n) = n+1;       (* Same function, alternative syntax. *)
val f = fn : int -> int

- fun sq (x:real) = x*x;
val sq = fn : real -> real

- fun abs n = if n<0 then ~n else n;
val abs = fn : int -> int

- [fn n=>n+1, fn m=>2*m, fn n=>n div 2];
val it = [fn,fn,fn] : (int -> int) list

- (fn n=>2*n,fn r=>ceil r);
val it = (fn,fn) : (int -> int) * (real -> int)

- ((fn x=>x+2) 4, (fn x=>x*3) 7);
val it = (6,21) : int * int

- fun f(x) = x+2; fun g(x) = x*3;  (* h, j use these functions. *)
val f = fn : int -> int
val g = fn : int -> int

- (f(4), g(7));
val it = (6,21) : int * int

- fun h (x) = (f x, g x);  h (4);  h (7);   (* functions and tuples. *)
val h = fn : int -> int * int
val it = (6,12) : int * int
val it = (9,21) : int * int

- fun j (x) = [f x, g x];  j (4);  j (7);   (* functions and lists.  *)
val j = fn : int -> int list
val it = [6,12] : int list
val it = [9,21] : int list

- #1 (fn x => x+1, fn y => y-1) 8;
val it = 9 : int

- val a = 1;             (* SML uses static binding     *)
val a = 1 : int

- fun f(x) = x+a;  f(4);
val f = fn : int -> int
val it = 5 : int

- val a = 3;
val a = 3 : int

- f(4);                  (* f(4) still has the value 5. *)
val it = 5 : int

- let val a = 1 in
=   let fun f(x) = x+a in
=     let val a = 3 in
=       f(4)
=     end
=   end
= end;
val it = 5 : int
```

### Recursive Functions

```- fun fact (n) = if n=0 then 1 else n*fact(n-1);
val fact = fn : int -> int

- fact (8);
val it = 40320 : int

- val fact' = (fn n => if n=0 then 1 else n*fact'(n-1));  (* Error! *)
stdIn:15.43-15.48 Error: unbound variable or constructor: fact'

- val rec fact = (fn n => if n=0 then 1 else n*fact(n-1));
val fact = fn : int -> int

- fun gcd (n,m) = if m=0 then n else gcd (m,n mod m);
val gcd = fn : int * int -> int

- fun exp (b,n) = if n=0 then 1.0 else b * exp (b,n-1);
val exp = fn : real * int -> real

- fun mc91 (n) = if n>100 then n-10 else mc91 (mc91 (n+11));  (* McCarthy's 91 fun *)
val mc91 = fn : int -> int

- map mc91 [103, 102, 101, 100, 99, 98, 97, 96];
val it = [93,92,91,91,91,91,91,91] : int list

- fun alt n = if n>100 then n-10 else 91;
val alt = fn : int -> int

- mc91(95)=alt(95); mc91(90)=alt(90); mc91(20)=alt(20);
val it = true : bool
val it = true : bool
val it = true : bool

- fun                        (* mutually recursive function definitions *)
=   odd (n) = if n=0 then false else even (n-1)
= and
=   even (n) = if n=0 then true else odd (n-1);
val odd = fn : int -> bool
val even = fn : int -> bool

- fun                        (* mutually recursive function definitions *)
=   take nil = nil | take (x::xs) = x::(skip xs)
= and
=   skip nil = nil | skip (x::xs) = take xs;
val take = fn : 'a list -> 'a list
val skip = fn : 'a list -> 'a list

- take [1,2,3];  skip [1,2,3,4];
val it = [1,3] : int list
val it = [2,4] : int list
```

### Functions and Patterns

```- fun f (x:int*int) = (#1 x) div (#2 x);
val f = fn : int * int -> int

- f (12,3);         (* function f applied to pair (12,3)  *)
val it = 4 : int

- val p = (12,3);   (* define a pair p                    *)
val p = (12,3) : int * int

- f p;              (* function f applied to pair p       *)
val it = 4 : int

- fun f (x,y) = x div y;
val f = fn : int * int -> int

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

- fun h (x,y) = (x div y, x mod y);
val h = fn : int * int -> int * int

- fun roots (a,b,c) =
=   let
=     val d = Math.sqrt (b*b - 4.0*a*c)
=   in
=     ((~b + d) / (2.0*a), (~b - d) / (2.0*a))
=   end;
val roots = fn : real * real * real -> real * real

- roots(1.0,2.0,~1.2);
val it = (0.483239697419,~2.48323969742) : real * real

- let val t =(1.0,2.0,~1.2) in roots t end;
val it = (0.483239697419,~2.48323969742) : real * real

- Real.fmt (StringCvt.FIX(SOME 3)) (#1 let val t =(1.0,2.0,~1.2) in roots t end);
val it = "0.483" : string

- fun l (x as (fst,snd)) = (x,fst div snd);     (* layered patterns    *)
val l = fn : int * int -> (int * int) * int

- fun j ((x,y), (a,b,c)) = f(x,y) - g(a,b,c);   (* tuples of tuples    *)
val j = fn : (int * int) * (int * int * int) -> int

- fun j (p,t) = f(p) - g(t);                    (* simpler alternative *)
val j = fn : (int * int) * (int * int * int) -> int

- fun
=   tuition {name=_, id=_, courses=nil} = 1000 |
=   tuition {courses=[_], ...}          = 2000 |
=   tuition {id,...}                    = if id>500000 then 5000 else 4000;
val tuition = fn : {courses:'a list, id:int, name:'b} -> int

- val Norm's_Record = {id=123456, name="Norm dePlume", courses=["cse1001", "mth1001"]};
val Norm's_Record =
{courses=["cse1001","mth1001"],id=123456,name="Norm dePlume"}
: {courses:string list, id:int, name:string}

- tuition Norm's_Record;
val it = 4000 : int

val sum = fn : int list -> int

- fun                          (* Error! *)
=  f (x,y)   = x+y+1   |
=  f (x,y,z) = x+y+z+2 |
=  f  _      = 3       ;
stdIn:39.1-42.15 Error: parameter or result constraints of clauses don't agree [tycon mismatch]
this clause:      'Z * 'Y * 'X -> 'W
previous clauses:      'V * 'U -> 'W
in declaration:
f =
(fn (x,y) => <exp> + <exp> + 1
| (x,y,z) => <exp> + <exp> + 2
| _ => 3)

- fun f(0) = "zero" | f(_) = "nonzero";
val f = fn : int -> string

- fun f(_) = "nonzero" | f(0) = "zero";   (* Error! *)
stdIn:43.1-43.37 Error: match redundant
_ => ...
-->   0 => ...

stdIn:1.1-2.23 Warning: match nonexhaustive

val h = fn : int list -> int

- h [3,17,435];
val it = 4 : int

- h (nil);          (* We were warned a runtime error possible! *)

uncaught exception nonexhaustive match failure
raised at: stdIn:2.17

- fun f (x,y,2) = x+y+2;
stdIn:1.1-2.17 Warning: match nonexhaustive
(x,y,2) => ...

val f = fn : int * int * int -> int

- f (3,17,2);
val it = 22 : int

- f (1,2,3);    (* Error! *)

uncaught exception nonexhaustive match failure
raised at: stdIn:2.12

- fun f[x,y,z] = (x,x+y+1,x+y+z+2);
stdIn:1.1-46.10 Warning: match nonexhaustive
x :: y :: z :: nil => ...

val f = fn : int list -> int * int * int

- f [1,2,3];
val it = (1,4,8) : int * int * int

- f [1,2];     (* Error! *)

uncaught exception nonexhaustive match failure
raised at: stdIn:2.11

- let val x=0 in if x=0 then 0 else 100 div x end;
val it = 0 : int

- fun If (x,y,z) =  if x then y else z;
val If = fn : bool * 'a * 'a -> 'a

- let val x=0 in If (x=0, 0, 100 div x) end;

uncaught exception divide by zero
raised at: <unknown file>

- infix 6 or;
infix 6 or

- fun x or y = x orelse y;
val or = fn : bool * bool -> bool

- infix 7 &;
infix 7 &

- fun x & y = x andalso y;   (*  & is a symbolic identifier  *)
val & = fn : bool * bool -> bool
```

### Polymorphic functions

```- fun id x = x;
val id = fn : 'a -> 'a

- (id 1, id "two");
val it = (1,"two") : int * string

- fun fst (x,y) = x;
val fst = fn : 'a * 'b -> 'a

- fun snd (x,y) = y;
val snd = fn : 'a * 'b -> 'b

- fst (1,"two");
val it = 1 : int

- fst ([true, false], 3.14159);
val it = [true,false] : bool list

- fst (1,"two") + snd ((1,2), hd [1,2,3]);
val it = 2 : int

- nil;
val it = [] : 'a list

- null;
val it = fn : 'a list -> bool

- hd;
val it = fn : 'a list -> 'a

- tl;
val it = fn : 'a list -> 'a list

- fun switch (x,y) = (y,x);
val switch = fn : 'a * 'b -> 'b * 'a

- switch (2, "abc");
val it = ("abc",2) : string * int

- switch (2,3.14159);
val it = (3.14159,2) : real * int

- #2 (switch ([6,9], (fn x =>x)));
val it = [6,9] : int list

- fun null (nil) = true | null (_::_) = false;
val null = fn : 'a list -> bool

- fun length (x) =
=   if null x then 0 else length (tl x) + 1;
val length = fn : 'a list -> int
```

### More lists

Lists are an important data structure in SML; and there are many useful predefined functions for lists.
```- fun member (x, nil) = false | member (x, y::ys) = x=y orelse member (x,ys);
val member = fn : ''a * ''a list -> bool

- member ("me", ["you", "them", "me", "us"]);
val it = true : bool

- member ("me", ["you", "them", "us"]);
val it = false : bool

- fun insert (x, nil) = [x]
=   | insert (x,y::ys) = if x<y then x::y::ys else y :: insert (x,ys);
val insert = fn : int * int list -> int list

- insert (5, [1,2,3,4,6,7,8,9]);
val it = [1,2,3,4,5,6,7,8,9] : int list

- fun merge (xs,nil) = xs
=  |  merge (nil,ys) = ys
=  |  merge (x::xs,y::ys) = if x<y then x :: merge(xs,y::ys) else y :: merge(x::xs,ys);
val merge = fn : int list * int list -> int list

- merge ([1,2,3,4,5,100,102,104,106], [~1,4,10, 20,21,22,105,200]);
val it = [~1,1,2,3,4,4,5,10,20,21,22,100,...] : int list
```
```- local
=    fun rotate nil = nil | rotate (x::xs) = xs@[x]
= in
=    fun boundaries l = ListPair.zip (l, rotate l)
= end;
val boundaries = fn : 'a list -> ('a * 'a) list

- boundaries nil;
stdIn:18.1-18.15 Warning: type vars not generalized because of
value restriction are instantiated to dummy types (X1,X2,...)
val it = [] : (?.X1 * ?.X1) list

- boundaries [1];
val it = [(1,1)] : (int * int) list

- boundaries [1,2,3,4,3,2,1];
val it = [(1,2),(2,3),(3,4),(4,3),(3,2),(2,1),(1,1)] : (int * int) list
```

### Higher-order functions

#### Functions as arguments

```- fun apply3 (f) = f(3);
val apply3 = fn : (int -> 'a) -> 'a

- fun fact (n) = if n=0 then 1 else n*fact(n-1);
val fact = fn : int -> int

- apply3 (fact);
val it = 6 : int

- apply3 (fn x => x+16);
val it = 19 : int

- apply3 (fn x => ({a=x},  true));
val it = ({a=3},true) : {a:int} * bool

- fun min_2 (f,g,x) = Int.min (f x, g x);
val min_2 = fn : ('a -> int) * ('a -> int) * 'a -> int

- fun com_2 (h,f,g,x) = h (f x, g x);
val com_2 = fn : ('a * 'b -> 'c) * ('d -> 'a) * ('d -> 'b) * 'd -> 'c

- fun min_2 (f,g,x) = com_2 (Int.min, f, g, x);
val min_2 = fn : ('a -> int) * ('a -> int) * 'a -> int
```

The key to functional programming is combining functions with other functions. What are the correct building blocks? Look for what is important---reoccuring patterns.

```- fun
=   incr (nil)  = nil |
=   incr (h::t) = (h+1) :: incr (t);
val incr = fn : int list -> int list

- fun
=   half (nil)  = nil |
=   half (h::t) = (h/2.0) :: half (t);
val half = fn : real list -> real list

- val f = (fn x=>x+1);
val f = fn : int -> int

- fun
=   incr (f,nil) = nil |
=   incr (f,h::t)  = f(h) :: incr (f,t);
val incr = fn : ('a -> 'b) * 'a list -> 'b list

- fun
=  map (f,nil)  = nil |
=  map (f,h::t) = f(h) :: map (f,t);
val map = fn : ('a -> 'b) * 'a list -> 'b list

- map (fn x=>x+1, [1,2,3,4,5]);  (* "map" sucessor func to list *)
val it = [2,3,4,5,6] : int list

- fun incr (list) = map (fn x=>x+1, list);
val incr = fn : int list -> int list

- incr [1,2,3,4,5];               (* new incr behaves as before *)
val it = [2,3,4,5,6] : int list

- map (fn x=>x/2.0, [2.0, 3.0, 4.0]);
val it = [1.0,1.5,2.0] : real list

- fun half (list) = map (fn x=>x/2.0, list);
val half = fn : real list -> real list

- half [2.0, 3.0, 4.0];
val it = [1.0,1.5,2.0] : real list

- fun
=   gt0 (nil)  = nil |
=   gt0 (h::t) = if h>0 then h::gt0(t) else gt0(t);
val gt0 = fn : int list -> int list

- fun
=   eqsq (nil)  = nil |
=   eqsq (h::t) = if h*h=h then h::eqsq(t) else eqsq(t);
val eqsq = fn : int list -> int list

- fun filter (f,l) =
=   if null l
=     then []
=     else if f(hd l)
=       then (hd l)::(filter (f, tl l))
=       else filter (f, tl l);
val filter = fn : ('a -> bool) * 'a list -> 'a list

- fun
=   filter (f,nil) = nil  |
=       else filter (f, tail);
val filter = fn : ('a -> bool) * 'a list -> 'a list

- filter ((fn x => x>0), [~1,0,1]);
val it = [1] : int list

- filter ((fn x => x*x=x), [~1,0,1]);
val it = [0,1] : int list
```
##### Numeric integeration
```- fun table (a, n, dx, F:real->real) =
=   if n<0 then nil else (a, F a) :: table (a+dx, n-1, dx, F);
val table = fn : real * int * real * (real -> real) -> (real * real) list

- table (0.0, 4, Math.pi/4.0, Math.sin);
val it =
[(0.0,0.0),(0.785398163397,0.707106781187),(1.57079632679,1.0),
(2.35619449019,0.707106781187),(3.14159265359,0.0)] : (real * real) list

- fun trapezoid (a, n, dx, F) =
=   if n<=0 then 0.0 else dx*(F(a)+F(a+dx))/2.0 + trapezoid (a+dx, n-1, dx, F);
val trapezoid = fn : real * int * real * (real -> real) -> real

- trapezoid (0.0, 4, Math.pi/4.0, Math.sin);
val it = 1.89611889794 : real

- trapezoid (0.0, 400, Math.pi/400.0, Math.sin);
val it = 1.99998971915 : real

- ~(Math.cos (Math.pi)) - ~(Math.cos (0.0));  (* integral of sin is -cos *)
val it = 2.0 : real
```

#### Returning functions

```- Int.fmt StringCvt.HEX 1200;    (* format an integer               *)
val it = "4b0" : string

- (Int.fmt StringCvt.HEX) 1200;  (* application is left associative *)
val it = "4b0" : string

- Int.fmt StringCvt.HEX;         (* function to format an integer *)
val it = fn : int -> string

- Int.fmt;                       (* notice that "->" is right associative *)
val it = fn : StringCvt.radix -> int -> string

- StringCvt.padLeft #" " 8 (Int.fmt StringCvt.HEX 1200);
val it = "     4b0" : string

val it = fn : string -> string

val it = fn : int -> string -> string

val it = fn : char -> int -> string -> string

- val min = (fn x => fn y => Int.min (x,y));
val min = fn : int -> int -> int

- fun min x = (fn y => Int.min (x,y));
val min = fn : int -> int -> int

- fun min x y = Int.min (x,y);
val min = fn : int -> int -> int
```
"blob" "blob" is now easy to understand -- function, argument, function application. Now we have "blob" "blob" "blob" and this looks odd at first. Of course, it is really ("blob" "blob") "blob" which is clearly two function applications. But we have something completely different from ordinary imperative langauges here: ("blob" "blob") is an expressions that must evaluate to a function. In order for it to be applied to an argument it must be a function. Happily, the basic rewriting rules (replacing equals by equals) still holds. We will be able to define functions fun f pat pat = splat , and then f blob blob can be replaced by splat.

(Unfortunately value polymorphism gets in the way of the main point that fun and val are all the same. See Types and Type Checking by McQueen.)

```- val const7 = (fn x => fn y => 7);  (* Several ways to define the same thing ... *)
val const7 = fn : 'a -> 'b -> int

- fun const7 x = (fn y => 7);
val const7 = fn : 'a -> 'b -> int

- fun const7 x y = 7;
val const7 = fn : 'a -> 'b -> int

- fun const7 _ _ = 7;
val const7 = fn : 'a -> 'b -> int

- Compiler.Control.valueRestrictionTopWarn := false;
val it = () : unit

- const7 ();  const7 nil;  const7 3;  const7 "a"; (*  Think of these as functions: 'a->int  *)
val it = fn : ?.X1 -> int
val it = fn : ?.X1 -> int
val it = fn : ?.X1 -> int
val it = fn : ?.X1 -> int

- const7 nil "abc";
val it = 7 : int

- const7 nil 3.4;
val it = 7 : int

- const7 () "abc";
val it = 7 : int

- const7 () 3.4;
val it = 7 : int

- const7 "xyz" [1,2];
val it = 7 : int

- fun const x = (fn _ => x);
val const = fn : 'a -> 'b -> 'a

- fun const x _ = x;
val const = fn : 'a -> 'b -> 'a

- const nil "abc";
val it = [] : ?.X1 list

- const nil 3.4;
val it = [] : ?.X1 list

- const () "abc";
val it = () : unit

- const () 3.4;
val it = () : unit

- const "xyz" [1,2];
val it = "xyz" : string
```
```- fun f (x) = (fn (y,z) => if x=0 then y+z else x*(y+z));
val f = fn : int -> int * int -> int

- f (2);
val it = fn : int * int -> int

- f (2) (5,8);
val it = 26 : int

- f (0) (5,8);
val it = 13 : int

- fun f (x) (y,z) = if x=0 then y+z else x*(y+z);
val f = fn : int -> int * int -> int
```

Here is a function to determine arithmetic sequences from geometric sequences. It returns the sequence, ie., the function from natural numbers to integers that generates each element of the sequence.

```- fun sequence (x as a::b::c::_) =
= let
=   val ab = b-a and bc = c-b
=   val r1 = b div a and r2 = c div b;
=   fun guess n = List.nth (x, n)
=   fun arith 0 = a | arith n = arith (n-1) + ab;
=   fun geom  0 = a | geom  n = geom (n-1) * r1;
= in
=   if ab=bc then arith else if r1=r2 then geom else guess
= end;
stdIn:13.1-22.4 Warning: match nonexhaustive
x as a :: b :: c :: _ => ...

val sequence = fn : int list -> int -> int

- val f = sequence [4,5,6,7,8,9];
val f = fn : int -> int

- f 3; f 4; f 5; f 6;
val it = 7 : int
val it = 8 : int
val it = 9 : int
val it = 10 : int

- val f = sequence [1,2,4,8,16];
val f = fn : int -> int

- f 3; f 4; f 5; f 6;
val it = 8 : int
val it = 16 : int
val it = 32 : int
val it = 64 : int
```

Higher-order functions, polymorphism and lists go together well.

```- fun map f nil = nil | map f (x::xs) = (f x)::(map f xs);
val map = fn : ('a -> 'b) -> 'a list -> 'b list

- fun filter p nil = nil | filter p (x::xs) = if p x then x::(filter p xs) else filter p xs;
val filter = fn : ('a -> bool) -> 'a list -> 'a list

- fun exists p nil = false | exists p (x::xs) = (p x) orelse (exists p xs);
val exists = fn : ('a -> bool) -> 'a list -> bool

- fun all p nil = true | all p (x::xs) = (p x) andalso (all p xs);
val all = fn : ('a -> bool) -> 'a list -> bool

- fun all p xs = not (exists (not o p) xs);
val all = fn : ('a -> bool) -> 'a list -> bool

- fun fold f ie nil = ie
=   | fold f ie (x::xs) = f (x, fold f ie xs);
val fold = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

- fold (op +) 0  [1,2,3,4,5,6,7,8,9];
val it = 45 : int

- fold (op ^) "" ["a","bc","def","","ghij"];
val it = "abcdefghij" : string

- foldr (op @) nil [[1],[2,3],[4,5,6],[],[7,8,9,0]];  (* foldr predefined *)
val it = [1,2,3,4,5,6,7,8,9,0] : int list

- fun revf f ie l =
=   if null(l)
=     then ie
=     else revf f (tl l) (f (hd l, ie));
val revf = fn : ('a * 'a list -> 'a list) -> 'a list -> 'a list -> 'a list

- fun revf f ie nil = ie
=   | revf f ie (y::ys) = revf f (f (y,ie)) ys;
val revf = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

- revf (op +) 0 [1,2,3,4,5,6,7,8,9];
val it = 45 : int

- revf (op ^) "" ["a","bc","def","","ghij"];
val it = "ghijdefbca" : string

- foldl (op @) nil [[1],[2,3],[4,5,6],[],[7,8,9,0]];  (* foldl predefined *)
val it = [7,8,9,0,4,5,6,2,3,1] : int list
```
Composition is another example of a higher-order function.
```- fun comp (f,g) = (fn x => f (g (x)));
val comp = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

- fun comp (f,g) (x) = f(g(x));
val comp = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

- val f = comp (Math.sin, Math.cos);
val f = fn : real -> real

- val g = Math.sin o Math.cos;        (*  Composition "o" is predefined  *)
val g = fn : real -> real

- f(0.25);
val it = 0.824270418114 : real

- g(0.25);
val it = 0.824270418114 : real
```
The functions twin and fourtimes are defined using composition.
```- local
=   fun search (n,i) =  i*i<=n andalso (n mod i = 0 orelse search (n,i+1));
= in
=   fun composite n = search (n,2);   (* search for a divisor *)
=   fun prime n = not (composite n)
= end;
val composite = fn : int -> bool
val prime = fn : int -> bool

- prime 3797;
val it = true : bool

- prime 87187;
val it = true : bool

- prime (87187 * 3797);
val it = false : bool

- composite (87187 * 3797);
val it = true : bool

- prime 99989;
val it = true : bool

- prime 99991;
val it = true : bool

- local
=   fun pair p = (p, p+2);
=   fun both_prime (p,q) = prime p andalso prime q;
= in
=   val twin = both_prime o pair
= end;
val twin = fn : int -> bool

- twin 99719;
val it = true : bool

- twin 99989;
val it = true : bool

- val times = (fn x => (fn y => x * y));
val times = fn : int -> int -> int

- fun times x = (fn y => x * y);
val times = fn : int -> int -> int

- fun times x y = x*y;
val times = fn : int -> int -> int

- times 3 4;
val it = 12 : int

- times 2;                  (* Partial application              *)
val it = fn : int -> int

- val twice = times 2;      (* Func twice define w/o using vars *)
val twice = fn : int -> int

- twice 5;                  (* Example use of twice.            *)
val it = 10 : int

- val fourtimes = twice o twice;      (* Defined w/o vars *)
val fourtimes = fn : int -> int

- fourtimes 5;              (* Example use of fourtimes.        *)
val it = 20 : int

- times;
val it = fn : int -> int -> int

- op *;
val it = fn : int * int -> int

- val hex = Int.fmt StringCvt.HEX; (* Convert int to hex string *)
val hex = fn : int -> string

val pad8 = fn : string -> string

- fun format n = pad8 (hex n);
val format = fn : int -> string

- val format = pad8 o hex;  (* predefined, binary, infix "o"    *)
val format = fn : int -> string

- val curry = (fn f => (fn a => fn b => f(a,b)));
val curry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c

- fun curry (f) (a) (b) = f(a,b);
val curry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c

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

- val curryplus = curry plus;
val curryplus = fn : int -> int -> int

- val curryplus = curry (op +);  (*  "op" keyword turns off infix *)
val curryplus = fn : int -> int -> int

- val successor = curryplus 1;
val successor = fn : int -> int

- val succ = plus 1;        (* type error! *)
stdIn:54.1-54.18 Error: operator and operand don't agree [literal]
operator domain: int * int
operand:         int
in expression:
plus 1

- val succ = (fn x => plus (1,x));
val succ = fn : int -> int

- Compiler.Control.valueRestrictionTopWarn := false;
val it = () : unit

- val len = List.foldl (fn (_,n) => n+1) 0;
val len = fn : ?.X1 list -> int

- fun len l = List.foldl (fn (_,n) => n+1) 0;  (* eta expansion *)
val len = fn : 'a -> 'b list -> int

- fun uncurry f (a,b) = f a b;
val uncurry = fn : ('a -> 'b -> 'c) -> 'a * 'b -> 'c
```
Functions that return functions allow the programmer to combine functions to make new functions. Higher-order utility functions capture the common patterns and can be specialized to perform customized operations.
```- fun map f nil = nil
=  |  map f (x::xs) = (f x) :: map f xs;
val map = fn : ('a -> 'b) -> 'a list -> 'b list

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

- map real [1,2,3,4,5,6];
val it = [1.0,2.0,3.0,4.0,5.0,6.0] : real list

- fun f g (x,y) = (x,g(y));
val f = fn : ('a -> 'b) -> 'c * 'a -> 'c * 'b

- map (f (fn x=>x+1)) [("a",1),("b",2),("c",2)];
val it = [("a",2),("b",3),("c",3)] : (string * int) list

- fun
=   filter f (nil)        = nil  |
val filter = fn : ('a -> bool) -> 'a list -> 'a list

- filter (fn x => x>0 andalso x*x=x);
val it = fn : int list -> int list

- filter Real.>;
val it = fn : (real * real) list -> (real * real) list

- filter Real.> [(1.0,2.0),(2.0,1.0),(Math.pi,Math.e)];
val it = [(2.0,1.0),(3.14159265359,2.71828182846)] : (real * real) list

- filter Real.< [(1.0,2.0),(2.0,1.0),(Math.pi,Math.e)];
val it = [(1.0,2.0)] : (real * real) list

- fun merge p (xs,nil) = xs
=  |  merge p (nil,ys) = ys
=  |  merge p (x::xs,y::ys) =
=    if p(x,y) then x :: merge p (xs,y::ys) else y :: merge p (x::xs,ys);
val merge = fn : ('a * 'a -> bool) -> 'a list * 'a list -> 'a list

- merge Real.>;
val it = fn : real list * real list -> real list

- merge Int.<;
val it = fn : int list * int list -> int list

- merge Int.< ([1,2,3,99,100],[1,2,3,49,50]);
val it = [1,1,2,2,3,3,49,50,99,100] : int list

- merge Int.> (rev [1,2,3,99,100], rev [1,2,3,49,50]);
val it = [100,99,50,49,3,3,2,2,1,1] : int list
```

## User defined data types

```- datatype color = Red | Blue | Green;
datatype color = Blue | Green | Red

- Blue;  Red;  Green;
val it = Blue : color
val it = Red : color
val it = Green : color

- datatype bool = true | false;
datatype bool = false | true

- fun not (true) = false | not (false) = true;
val not = fn : bool -> bool

- datatype numbs = i of int | r of real;
datatype numbs = i of int | r of real

- [i 3, r 3.4, i 5, i 9, r 5.4];
val it = [i 3,r 3.4,i 5,i 9,r 5.4] : numbs list

- fun isum nil = 0
=   | isum ((i n)::rest) = n+(isum rest) | isum (_::rest) = isum (rest);
val isum = fn : numbs list -> int

- datatype shape = Rectangle of real*real | Circle of real | Line of (real*real)list
=    | Spline of (real*real)list;
datatype shape
= Circle of real
| Line of (real * real) list
| Rectangle of real * real
| Spline of (real * real) list

- Circle (1.2);  Circle (3.4);
val it = Circle 1.2 : shape
val it = Circle 3.4 : shape

- Rectangle (4.3, 1.9);  Rectangle (40.3, ~8.345);
val it = Rectangle (4.3,1.9) : shape
val it = Rectangle (40.3,~8.345) : shape

- Line [(1.1, 2.2)];  Line [];
val it = Line [(1.1,2.2)] : shape
val it = Line [] : shape

- datatype ilist = inil | cons of int * ilist;
datatype ilist = cons of int * ilist | inil

- datatype itree = empty | node of int * itree * itree;
datatype itree = empty | node of int * itree * itree

- datatype
=    stmt = Assign | Block of block
= and
=    block = Begin of stmt list;
datatype stmt = Assign | Block of block
datatype block = Begin of stmt list

- Assign;
val it = Assign : stmt

- Block (Begin [Assign]);  Block (Begin [Assign, Assign]);
val it = Block (Begin [Assign]) : stmt
val it = Block (Begin [Assign,Assign]) : stmt

- datatype 'a option = NONE | SOME of 'a;  (* predefined in structure Option *)
datatype 'a option = NONE | SOME of 'a

- datatype 'a glist = gnil | cons of 'a * 'a glist;
datatype 'a glist = cons of 'a * 'a glist | gnil

- datatype 'a binary_tree = empty | node of 'a * 'a binary_tree * 'a binary_tree;
datatype 'a binary_tree = empty | node of 'a * 'a binary_tree * 'a binary_tree

- datatype ('a,'b) union =InLeft of 'a | InRight of 'b;
datatype ('a,'b) union = InLeft of 'a | InRight of 'b

- InLeft(3); InRight (true); InLeft("s");
val it = InLeft 3 : (int,'a) union
val it = InRight true : ('a,bool) union
val it = InLeft "s" : (string,'a) union

- [InLeft(3), InRight (true)];
val it = [InLeft 3,InRight true] : (int,bool) union list

- [InLeft(3), InRight (true), InLeft("s")];  (* type error *)
stdIn:40.1-40.41 Error: operator and operand don't agree [literal]
operator domain: (int,'Z) union * (int,'Z) union list
operand:         (int,'Z) union * (string,bool) union list
in expression:
InLeft 3 :: InRight true :: InLeft "s" :: nil
```