Visits: 102
(* Coursera Programming Languages, Homework 3, Provided Code *) exception NoAnswer datatype pattern = Wildcard | Variable of string | UnitP | ConstP of int | TupleP of pattern list | ConstructorP of string * pattern datatype valu = Const of int | Unit | Tuple of valu list | Constructor of string * valu fun g f1 f2 p = let val r = g f1 f2 in case p of Wildcard => f1 () | Variable x => f2 x | TupleP ps => List.foldl (fn (p,i) => (r p) + i) 0 ps | ConstructorP(_,p) => r p | _ => 0 end (**** for the challenge problem only ****) datatype typ = Anything | UnitT | IntT | TupleT of typ list | Datatype of string (**** you can put all your code here ****) (* 1 *) fun is_capital s = Char.isUpper(String.sub(s, 0)); (* List.filter takes 2 parameters, not a tuple *) fun only_capitals slist = List.filter is_capital slist; (* 2 *) (* helper function takes a tuple with 2 parameters *) fun keep_longer1 (x, y) = if String.size(x) > String.size(y) then x else y; (* List.foldl expects a 'a * 'b -> 'b function, not a triple *) fun longest_string1 slist = List.foldl keep_longer1 "" slist; (* 3 *) fun keep_longer2 (x, y) = if String.size(x) >= String.size(y) then x else y; fun longest_string2 slist = List.foldl keep_longer2 "" slist; (* 4 *) fun longest_string_helper f slist = let fun keep_longer (x, y) = if f(String.size(x), String.size(y)) then x else y; in List.foldl keep_longer "" slist end; (* defined with val-bindings and partial applications *) val longest_string3 = longest_string_helper (fn(x, y) => x > y); val longest_string4 = longest_string_helper (fn(x, y) => x >= y); (* 5 *) fun longest_capitalized slist = longest_string1(only_capitals(slist)); (* 6 *) (* use () to determine the priority, otherwise explode(s) will be done first *) fun rev_string s = (implode o rev o explode) s; (* or, define with val-binding: val rev_string = (implode o rev o explode) *) (* 7 *) fun first_answer f lst = case lst of [] => raise NoAnswer | x::xs => case f(x) of NONE => first_answer f xs | SOME v => v; (* 8 *) fun all_answers f lst = let fun helper(l, f, acc) = case l of [] => SOME acc | x::xs => case f(x) of NONE => NONE | SOME v => helper(xs, f, v @ acc) in helper(lst, f, []) end; (* 9 *) fun void _ = 0 val count_wildcards = g (fn _ => 1) void; val count_wild_and_variable_lengths = g (fn _ => 1) (fn x => String.size x); fun count_some_var (s, p) = g void (fn x => if x = s then 1 else 0) p; (* 10 *) fun check_pat p = let fun get_type pat = case pat of Variable x => [x] | TupleP ps => List.concat (List.map get_type ps) | ConstructorP(_,p) => get_type p | _ => []; fun find_duplicate lst = case lst of [] => false | x::xs => case List.exists (fn y => x = y) xs of true => true | false => find_duplicate xs in not (find_duplicate (get_type p)) end; (* 11 *) fun match vp = case vp of (_, Wildcard) => SOME [] | (v, Variable s) => SOME [(s, v)] | (Unit, UnitP) => SOME [] | (Const x, ConstP y) => if x = y then SOME [] else NONE | (Tuple vs, TupleP ps) => if List.length(vs) = List.length(ps) then all_answers match (ListPair.zip (vs, ps)) else NONE | (Constructor(s2, v), ConstructorP(s1, p)) => if s1 = s2 then match (v, p) else NONE | _ => NONE; (* 12 *) fun first_match v lst = SOME (first_answer (fn p => match(v, p)) lst) handle NoAnswer => NONE;
(* Homework3 Simple Test*) (* These are basic test cases. Passing these tests does not guarantee that your code will pass the actual homework grader *) (* To run the test, add a new line to the top of this file: use "homeworkname.sml"; *) (* All the tests should evaluate to true. For example, the REPL should say: val test1 = true : bool *) val test1 = only_capitals ["A","B","C"] = ["A","B","C"] val test2 = longest_string1 ["A","bc","C"] = "bc" val test3 = longest_string2 ["A","bc","C"] = "bc" val test4a = longest_string3 ["A","bc","C"] = "bc" val test4b = longest_string4 ["A","B","C"] = "C" val test5 = longest_capitalized ["A","bc","C"] = "A" val test5_1 = longest_capitalized ["A","bc","CA"] = "CA" val test6 = rev_string "abc" = "cba" val test7 = first_answer (fn x => if x > 3 then SOME x else NONE) [1,2,3,4,5] = 4 val test8 = all_answers (fn x => if x = 1 then SOME [x] else NONE) [2,3,4,5,6,7] = NONE val test8_1 = all_answers (fn x => if x > 1 then SOME [x] else NONE) [3] = SOME [3] val test8_2 = all_answers (fn x => if x > 1 then SOME [x] else NONE) [3,1] = NONE val test8_3 = all_answers (fn x => if x > 1 then SOME [x] else NONE) [2,3,4] = SOME [4,3,2] val test9a = count_wildcards Wildcard = 1 val test9a_1 = count_wildcards (Variable("a")) = 0 val test9b = count_wild_and_variable_lengths (Variable("a")) = 1 val test9b_1 = count_wild_and_variable_lengths (TupleP([Wildcard, Variable("abc")])) = 4 val test9c = count_some_var ("x", Variable("x")) = 1 val test9c_1 = count_some_var ("x", Variable("y")) = 0 val test9c_2 = count_some_var ("hello", TupleP([Variable("x"), Wildcard, Variable("hello"), Variable("hello")])) = 2 val test10 = check_pat (Variable("x")) = true val test10_1 = check_pat (TupleP([Variable("x"), Wildcard])) = true val test10_2 = check_pat (TupleP([Variable("x"), Wildcard, Variable("hello"), Variable("hello")])) = false val test11 = match (Const(1), UnitP) = NONE val test11_1 = match (Const(1), Wildcard) = SOME [] val test11_2 = match (Const(1), Variable("a")) = SOME [("a", Const(1))] val test11_3 = match (Unit, UnitP) = SOME [] val test11_4 = match (Tuple([Const(1)]), UnitP) = NONE val test11_5 = match (Const(1), ConstP(1)) = SOME [] val test11_6 = match (Const(1), ConstP(2)) = NONE val test11_7 = match (Tuple([Const(1), Const(2)]), TupleP([Wildcard, ConstP(2)])) = SOME [] val test11_8 = match (Tuple([Const(1)]), TupleP([Wildcard, ConstP(2)])) = NONE val test11_9 = match (Tuple([Const(1), Const(2)]), TupleP([ConstP(3), ConstP(2)])) = NONE val test11_10 = match (Tuple([Const(1)]), TupleP([Variable("a")])) = SOME [("a", Const(1))] val test11_11 = match (Tuple([Const(1), Const(2)]), TupleP([Variable("a"), ConstP(2)])) = SOME [("a", Const(1))] val test11_12 = match (Tuple([Const(1), Const(2)]), TupleP([Variable("a"), Variable("b")])) = SOME [("b", Const(2)), ("a", Const(1))] val test11_13 = match (Constructor("a", Const(1)), ConstructorP("b", ConstP(1))) = NONE val test11_14 = match (Constructor("a", Const(1)), ConstructorP("a", ConstP(1))) = SOME [] val test11_15 = match (Constructor("a", Const(1)), ConstructorP("a", ConstP(2))) = NONE val test12 = first_match Unit [UnitP] = SOME [] val test12_1 = first_match Unit [Variable("a"), UnitP] = SOME [("a", Unit)] val test12_2 = first_match (Const(1)) [(ConstP(2)), UnitP] = NONE