PLP: Lecture 25
Let expressions
let val x = expr_1 in expr_2 end;
The value of the entire let
expression is the value of expr_2
. x
is a new variable that is binded to the result of expr_1
. The binding is local to the let expr.
Example:
fun rev x = let val(a,b) = rev2(x, []) in b end;
which is a val rev = fn : 'a list -> 'a list
. The result is accumulated in b
and returned in x
.
Logical conditionals in ML
orelse
isor
andalso
isand
Strange!
Infix operators
Can have any precedence in 0 to 9. Can be left associative, or right-associative if infixr
is used.
Example:
Function to indicate if item is in a list,
infix mem;
fun(x mem []) = false
| (x mem (y::ys)) = x=y orelse (x mem ys);
Note that mem
only works with types that have an equality test defined. Denoted as ''a
. This is called constrained polymorphism, since not any old type can be used! Built into the language.
Custom data types
keyword datatype
. Use pattern-matching to indicate valid constructors.
Example:
datatype Person = Queen
| Peer of string * string * int
| Peasent of string
| Knight of string
| ...
Functions over a user defined type can be defined using patterns over constructors. Note that concatenating strings is done with the ^
character, e.g., "Sir" ^ name
.
fun title Queen = "Her majesty the Queen"
| title (Peer (deg, terr,_)) = "The " ^ deg ^ " of " ^ terr
...
This is var title = fn: person -> string
.
Datatypes are the disjoint union
of their constructors- labeled disjoint types. They are polymorphic as well.
Example:
datatype ('a, 'b) union = ln1 of 'a | ln2 of 'b;
val v1 = [ln1 "hello", ln1 "bye", ln2 3, ln1 "adios"];
This is val v1 = [...] : (string, int) union list
. Type inference~
Example:
datatype bin_tree = leaf of int
| node of bin_tree * bin_tree;
Simple tree: node(leaf 1, node(leaf 2, leaf 3));
Binding functions with Let
Let expressions can also locally bind functions to names. Useful for helper functions.
fun ordered (leaf n) = true
| ordered (node(t1, t2)) = (max t1 <= min t2)
andalso (ordered t1)
andalso (ordered t2);
This is a val ordered = fn: bin_tree -> bool
. Note that max
and min
are also helper functions. Can define max
and min
within ordered
using let
.
What if we wanted to express binary trees as (5, (3, 2))
? Need to write a scanner and a parser for this grammar! Can do this in ML.
Case expressions
case E of P1 => E1 | ... | Pn => En
The value of E is matched against patterns P1, …, Pn. The value of the expression corresponding to the first pattern to match the value of E is the value of the expression.
Assume you have a list of scanned tokens from some inputs, ts
. Recall, a binary tree should be (binTree, binTree)
.
fun binTree ts =
case ts of
(numlit x)::tr => tr
| lparen::tr =>
let val ts1 = binTree tr
let val ts2 = case ts1 of
comma::tr2 => tr2
| _ => raise parseError
let val ts3 = binTree ts2
val ts4 = case ts3 of
rparen::tr4 => tr4
| _ => raise parseError
in ts4 (* return remainder of the list of tokens *)
end
| _ => raise parseError
Putting function binTree
together with our scanner scan
,
fun parse s =
let val result = binTree (scan s)
in result = []
end;
which, if result
is non-empty, means the parsing failed so the value returned is false.