作业|学习

Programming Languages, Part A, HW3

凝神长老 · 11月18日 · 2020年 33次已读
(* 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

订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论