本文写于 2020年11月18日,距今已超过 1 年,距 2020年11月18日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!
(* 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