(* Section 3!
brought to you by Emily
CSE 341 Sp11
*)
(* review *)
(* How does ML decide what type this function is? (below) *)
datatype random =
One
| Two
| Three
fun processRandomList (lst) =
case lst of
[] => []
| (One)::tail => 1::processRandomList(tail)
| (Two)::tail => 2::processRandomList(tail)
| (Three)::tail => 3::processRandomList(tail)
fun processListOfRecord (lst) =
case lst of
[] => 0
| head::tail =>
let val {bacon=b, eggs=e} = head
in
b + e + processListOfRecord(tail)
end
(* this is a nicer way of writing it (recommended) *)
fun processListOfRecord (lst) =
case lst of
[] => 0
| {bacon=b, eggs=e}::tail => b + e + processListOfRecord(tail)
(* this also works: (also good) *)
fun processListOfRecord (lst) =
case lst of
[] => 0
| {bacon, eggs}::tail => bacon + eggs + processListOfRecord(tail)
(* and if you don't care about the other record values: *)
fun processListOfRecord (lst) =
case lst of
[] => 0
| {bacon=b, eggs=_}::tail => b + processListOfRecord(tail)
(* pattern matching is EVERYWHERE in ML! *)
val (a, b, c) = (1, 2, 3)
val (x, _, ((3,a), b)) = ({i=10,j=20}, (3,4,5), ((3,true), false))
(* You can pattern match with as many or as few variables as you want. *)
fun many (a, b, c) =
case (a, b) of
(1, 2) => 1
| (_,_) => 4
(* if n > 5 return NONE, else return SOME and the nth element (also return NONE if n > size of lst) *)
fun return_nth_if_less_than5(lst, n) =
if n > 5 then NONE
else case (n, lst) of
(0, head::tail) => SOME(head)
| (n, head::tail) =>
return_nth_if_less_than5(tail, n-1)
| (_, []) => NONE
(* types are super handy --
use them to remind you what to return if you get lost in your function...*)
datatype pet_type = Cat | Dog
datatype pet_owner =
Catlover of int option (* if it's Cats(NONE), then the person likes cats, but doesn't have any *)
| Doglover of int (* just int here to make things interesting *)
val pet_directory = {campusPkwy=Catlover(SOME(5)), theAve=Doglover(19), wallingford=Doglover(0)}
(* CONTEST: write this function most elegantly! *)
(* go through the directory to find which streets can accept a new pet of a certain type. A street can accept a pet of that type if it has lovers of that type of pet, and the number of pets it currently has is less than 10. This function returns true if all of the streets can take the pet, false otherwise. *)
fun allStreetsCanTakePet (pet, pet_dir) =
let val {campusPkwy=cOwners, theAve=aOwners, wallingford=wOwners} = pet_dir
fun canTakePet (owners) =
case (pet, owners) of (* note don't have to use all the parameters here. can use as many or as few as you want.*)
(Cat, Catlover(SOME(cats))) => cats < 10
| (Cat, Catlover(NONE)) => true
| (Dog, Doglover(dogs)) => dogs < 10
| (_, _) => false
in
(canTakePet cOwners) andalso (canTakePet aOwners) andalso (canTakePet wOwners)
end
(* =============== newer stuff ================= *)
(* Map: You've seen this. *)
fun map (f, l) =
case l of
[] => []
| head::tail => (f head)::(map (f, tail))
(* Similar things over trees *)
datatype intTree = Leaf | Node of int * intTree * intTree
fun treeMap (f, t) =
case t of
Leaf => Leaf
| Node (i,l,r) =>
Node (f i, treeMap (f, l), treeMap (f, r))
(* or, better yet, why keep writing f everywhere if it stays the same? *)
fun treeMap2 (f, t) =
let
fun recur t = treeMap2 (f,t)
in
case t of
Leaf => Leaf
| Node (i,l,r) =>
Node (f i, recur l, recur r)
end
(* What else can we do with first class functions? *)
(* review: general function syntax *)
val nonRecursiveFunction = fn x => x
(* why can't you write a recursive function using this specific syntax? *)
(* this function takes in a list, and returns a function that uses that list! *)
fun mapList l =
fn f => map (f, l)
fun mapFun f =
fn l => map (f, l)
fun inc x = x + 1
val lst = [1,2,3,4]
val incList = mapFun inc
(* The type inference is not quite clever enough to figure this out without some
* hint; hence fun rather than val. *)
fun apply_to_1234 f = mapList lst f
val l1 = incList lst
val l2 = apply_to_1234 inc
(* Map: You've seen this. *)
fun map (f, l) =
case l of
[] => []
| head::tail => (f head)::(map (f, tail))
(* map examples practice *)
(* write convertFC, which converts a list of Fahrenheit measurements to a list of Celsius measurements (9/5) *)
fun convertFC lst =
map(fn x => (x-32.0) * (5.0/9.0), lst);
(* write convert-euro, which converts a list of U.S. dollar amounts into a list of euro amounts based on an exchange rate of 1.22 euro for each dollar *)
fun convert-euro lst =
map((fn x => x*1.22) , lst)
(* ----------- Fold ------------ *)
(* These all look the same...*)
fun add_list l =
case l of
[] => 0
| head::tail => head + (add_list tail)
fun mult_list l =
case l of
[] => 1
| head::tail => head * (mult_list tail)
fun concat_list l =
case l of
[] => ""
| head::tail => head ^ (concat_list tail)
(* introducing Fold! *)
fun fold (func, init, lst) =
case lst of
[] => init
| head::tail => func (head, fold (func, init, tail))
fun add_list_fold l = fold ((fn (x,y) => x+y), 0, l)
fun mult_list_fold l = fold ((fn (x,y) => x*y), 1, l)
fun concat_list_fold l = fold ((fn (x,y) => x^y), "", l)
(* This is actually the right fold (goes right to left). ML calls this foldr *)
(* Left fold (foldl) goes left to right and is tail-recursive *)
fun otherfold func acc lst =
case lst of
[] => acc
| head::tail => otherfold func (func (head,acc)) tail
(* so, fold right is: a_0 op (a_1 op (a_2 op ... (a_{n-1} op a_{n}) ...)))
and fold left is: (...(((a_0 op a_1) op a_2) op a_3) ... ) op a_n
*)
fun map (f, l) =
case l of
[] => []
| head::tail => (f head)::(map (f, tail))
fun fold (func, init, lst) =
case lst of
[] => init
| head::tail => func (head, fold (func, init, tail))
(* Practice: use fold to define append, which juxtaposes the items of two lists or, equivalently, replaces [] at the end of the first list with the second list *)
fun append (lst1, lst2) =
fold((fn (x, y) => x::y), lst2, lst1);
(* define map using fold. *)
(*the compact way: *)
fun map (func, lst) =
fold((fn (x, y) => (func x)::y), [], lst);
(* the verbose way: *)
fun map (func, lst) =
let fun applyAndAssembleList (element, tail) =
(func element)::tail
in
fold (applyAndAssembleList, [], lst)
end
(* filter *)
fun filter (f, lst) =
case lst of
[] => []
| head::tail => if (f head) then
head::filter(f, tail)
else filter(f, tail)
(* write "selection", which consumes two lists of names and selects all those from the second one that are also on the first. *)
fun selection (lst1, lst2) =
let fun inLst (e, lst) =
case lst of
[] => false
| head::tail => if head = e then true else inLst(e, tail)
filter((fn x => inLst(x, lst1)), lst2);
(*write eliminate-exp, which consumes a number, ua, and a list of toy tuples (containing name and price) and produces a list of all those descriptions whose price is below ua *)