(* Working with records:
defining them, constructing values, and pattern matching *)
(* definition *)
type fbb = { foo : int, bar : bool, baz : string }
(* values *)
val z : fbb = {foo = 5+1, bar = true, baz = "hi"}
(* using values *)
fun ifbarthenfooelsezero f =
(* each of these bindings matches an fbb record. The first two are identical;
the one in the code is the most explicit *)
(* let val {foo, bar, baz} = f in *)
(* let val {foo = foo, bar = bar, baz = baz} = f in *)
let val {foo = a, bar = b, baz = _} = f in
if b then a else 0
end
(* Working with ropes from last week (constructor names have been changed) *)
(* goal is to apply higher-order functions to simplify some of the work *)
(* definition *)
datatype 'elt rope =
Empty
| List of 'elt * 'elt rope
| Knot of 'elt rope * 'elt rope
(* values *)
val x = Empty
val y = List(5, Empty)
val y2 = Knot(Empty, List(5, Empty))
val fsse = Knot(List(5, List(6,Empty)), List(7, List(8, Empty)))
val fssent = Knot(fsse, List(9, List(10, Empty)))
(* using values *)
(* sumOfRope : int rope -> int *)
fun sumOfRope r =
case r of
Empty => 0
| List(x, xs) => x + sumOfRope(xs)
| Knot(xs, ys) => sumOfRope xs + sumOfRope ys
(* generalizing sumOfRope *)
(* stuffWithRope : ('a rope * ('a -> int)) -> int
r is a rope of alphas, and f can turn those alphas into integers
The idea is to capture the "way the recursion works" from sumOfRope,
but be able to do stuff to the elements of the rope before summing them *)
fun stuffWithRope (r, f) =
case r of
Empty => 0
| List(x, xs) => (f x) + stuffWithRope(xs, f)
| Knot(xs, ys) => stuffWithRope(xs, f) + stuffWithRope(ys, f)
(* same as above, but using the general function *)
fun sumOfRope2 r = stuffWithRope(r, (fn x => x))
(* same as above, but filtering only the even numbers *)
(* without stuffWithRope, you'd have to reimplement the whole case statement *)
fun evenSumOfRope r = stuffWithRope(r, (fn x => if x mod 2 = 0 then x else 0))
(* let's look at lists for a minute *)
(* map : ('a list * ('a -> 'b)) -> 'b list *)
fun map (l, f) =
case l of
[] => []
| x :: xs => (f x) :: (map (xs, f))
(* example : map ([1,2,3], (fn x => x * 2)) = [2,4,6] *)
(* example : map ([1,2,3], (fn x => x mod 2 == 0)) = [false, true, false] *)
(* generalizing the :: constructor and [] value... *)
(* mapThenG : ('a list * ('a -> 'b) * (('b * 'c) -> 'c) * 'c) -> 'c
mapThenG takes a list of alphas. It maps f over those alphas,
creating a lot of betas. But instead of just returning a list of betas,
it uses the function g to combine them into some new answer. Instead of
using the [] as the base case, it uses z (a "zero" element for whatever g
does *)
fun mapThenG (l, f, g, z) =
case l of
[] => z
| x :: xs => g((f x), (mapThenG (xs, f, g, z)))
(* same as map, but "using" the general version *)
(* (op::) is the name of the function that cons's lists together *)
fun map2 (l, f) = mapThenG(l, f, (op::), [])
(* adds all numbers in a list of numbers, but using the general function *)
fun sumOfList l = mapThenG(l, (fn x => x), (op+), 0)
(* prints a list of strings *)
fun printList l = mapThenG(l, (fn x => x), (fn (x, str) => x ^ ", " ^ str), "[]")
(* the real name for "thenG" is reduce; this function does a map
the list, and reduces it to a single answer, but does it "all at once" *)
(* let's try a similar example with arithmetic expressions *)
datatype expr =
EConst of int
| EBinOp of expr * (int * int -> int) * expr
(* a simple evaluator *)
fun eval exp =
case exp of
EConst x => x
| EBinOp (e1, f, e2) => f(eval e1, eval e2)
(* e = (4+5)*(3-2) *)
val e = EBinOp(EBinOp(EConst 4, (op+), EConst 5),
( op* ),
EBinOp(EConst 3, (op-), EConst 2))
(* instead of evaluating the arithmetic, get the rightmost constant *)
fun getRight exp =
case exp of
EConst x => x
| EBinOp (e1, f, e2) => getRight e2
(* how can we do that with the same evaluator? change the operators! *)
(* replaceOprs takes an expression and a function, and replaces all the
operators in the expression with f. *)
fun replaceOprs (exp, f) =
case exp of
EConst x => EConst x
| EBinOp (e1, opr, e2) => EBinOp (replaceOprs (e1, f),
f,
replaceOprs (e2, f))
(* let's see this in action. *)
fun snd (v1, v2) = v2
(* replaceOprs (e, snd) = EBinOp(EBinOp(EConst 4,
snd,
EConst 5),
snd,
EBinOp(EConst 3,
snd,
EConst 2)) *)
(* if we evaluate that... we'll get the rightmost constant, just as above *)
fun getRight2 exp = eval(replaceOprs(exp, snd))