(* Annonymous Funcitons *)
fun apply_to_five f = f 5
(* Annonymous versions *)
val v1 = apply_to_five (fn x => x * 2) (* v1 = 10 *)
val v2 = apply_to_five (fn x => x * x * x) (* v2 = 125 *)
(* Named versions *)
fun double x = x * 2
fun cube x = x * x * x
(* Returning Functions *)
(* Disclaimer: Only these three becuase it is a small example and the character
sets are "similar enough" to ascii. *)
datatype Lang = Spanish | French | English
fun get_translator Spanish = (fn str => "Hola " ^ str)
| get_translator French = (fn str => "Bonjour " ^ str)
| get_translator English = (fn str => "Hello " ^ str)
val sp_trans = get_translator Spanish
val fr_trans = get_translator French
val en_trans = get_translator English
val str1 = sp_trans "World"
val str2 = fr_trans "Buddy"
val str3 = en_trans "Cello"
(* Map, Filter, and Fold *)
fun map (f, xs) =
case xs of
[] => []
| x::xs => f x :: map (f,xs)
fun filter (f, xs) =
case xs of
[] => []
| x::xs => if f x
then x::filter (f, xs)
else filter (f, xs)
(* Specifically fold-left *)
fun fold (f, acc, xs) =
case xs of
[] => acc
| x::xs' => fold (f, f(acc, x), xs')
fun f1 xs = fold ((fn (x, y) => x + y), 0, xs)
fun f2 xs = fold ((fn (x, y) => x andalso y >= 0), true, xs)
(* Generic Binary Tree Type *)
datatype 'a tree = Empty
| Node of 'a * 'a tree * 'a tree
val tree1 = Node (1,
Node (3, Empty, Empty), Node (2,
Empty, Node (5, Empty, Empty)))
val tree2 = Node (1, Node (5, Empty, Empty), Empty)
(* Returns a tree of the same structure but with `f` applied to each
element. *)
fun tree_map (_, Empty) = Empty
| tree_map (f, Node (el, left, right)) =
Node (f el, tree_map (f, left), tree_map (f, right))
(* Returns true iff true is the result of applied the given function
to every element in the given tree. *)
fun tree_all (_, Empty) = true
| tree_all (f, Node (el, left, right)) =
f el andalso tree_all (f, left) andalso tree_all (f, right)
(* Modified expression datatype from lecture 5. Now there are
variables. *)
datatype exp = Constant of int
| Negate of exp
| Add of exp * exp
| Multiply of exp * exp
| Var of string
(* Do a post-order traversal of the given exp. At each node, apply a
function f to it and replace the node with the result. *)
fun visit_post_order (f, ex) =
let fun binaryVisit (ctor, e1, e2) =
f (ctor (visit_post_order (f, e1),
visit_post_order (f, e2)))
in case ex of
Constant _ => f ex
| Negate e1 => f (Negate (visit_post_order (f, e1)))
| Add (e1, e2) => binaryVisit (Add, e1, e2)
| Multiply (e1, e2) => binaryVisit (Multiply, e1, e2)
| Var _ => f ex
end
(* Simplify the root of the expression if possible. *)
fun simplify_once ex =
case ex of
(* Basic constant folding. *)
Negate (Constant i) => Constant (~i)
| Add (Constant i, Constant j) => Constant (i+j)
| Multiply (Constant i, Constant j) => Constant (i*j)
(* Lets try to be smarter too! *)
| Add (Constant 0, e2) => e2
| Add (e1, Constant 0) => e1
| Multiply (Constant 0, e2) => Constant 0
| Multiply (e1, Constant 0) => Constant 0
| Multiply (Constant 1, e2) => e2
| Multiply (e1, Constant 1) => e1
(* Everything else we'll just leave the same. *)
| _ => ex
(* Almost the same as evaluate but leaves variables alone. *)
fun simplify ex = visit_post_order (simplify_once, ex)
val exp1 = Add (Constant 1, Constant 2)
val exp2 = Multiply (Constant 2, Add (Constant 5, Constant 2))
val exp3 = Add (Add (Constant 5, Constant 7), Var "x")
val exp4 = Multiply (Add (Constant ~5, Constant 5), Var "y")
(* More advanced. Just for completeness... *)
exception VariableNotBound of string
fun replace_variables (bindings, ex) =
let fun getVar varStr =
case List.find (fn (b, _) => b=varStr) bindings of
NONE => raise VariableNotBound varStr
| SOME (_, e) => e
fun replace (Var str) = getVar str
| replace ex = ex
in visit_post_order (replace, ex)
end
val someVariables = [("x", Constant 10), ("y", Constant 11)]
fun evaluate (bindings, ex) =
simplify (replace_variables (bindings, ex))