﻿Programming Languages, Part A, HW3 - 凝神长老和他的朋友们

# Programming Languages, Part A, HW3

(* Coursera Programming Languages, Homework 3, Provided Code *)

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 *)
case lst of
| x::xs => case f(x) of
| SOME v => v;

(* 8 *)
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
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)

(* 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)  = SOME 

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 0 评论