Programming Languages Part A HW2 Extra Practice Problems
这次回顾HW2 Extra Practice Problems，主要是Standard ML模式匹配的补充练习。
课程主页：
https://www.coursera.org/learn/programming-languages/home
B站搬运：
https://www.bilibili.com/video/BV1dL411j7L7
习题内容：
https://www.coursera.org/learn/programming-languages/supplement/JXL99/extra-practice-problems
代码
(* problem 0 *)
fun length_of_a_list(list) =
case list of
[] => 0
| a::b => 1 + length_of_a_list(b)
(* problem 1-4 *)
type student_id = int
type grade = int (* must be in 0 to 100 range *)
type final_grade = { id : student_id, grade : grade option }
datatype pass_fail = pass | fail
(* problem 1 *)
fun pass_or_fail(final_grade) =
let
fun helper(d) =
if d >= 75
then
pass
else
fail
in
case final_grade of
{grade = SOME a, id = b} => helper(a)
| _ => fail
end
(* problem 2 *)
fun has_passed(final_grade) =
if pass_or_fail(final_grade) = pass
then
true
else
false
(* problem 3 *)
fun number_passed(final_grade_list) =
let
fun helper(final_grade) =
if has_passed(final_grade) then 1 else 0
in
case final_grade_list of
[] => 0
| final_grade::final_grade_list_rst =>
helper(final_grade) + number_passed(final_grade_list_rst)
end
(* problem 4 *)
fun number_misgraded(arr) =
let
fun xor(a, b) =
(a orelse b) andalso not(a andalso b)
fun helper1(pass_fail) =
if pass_fail = pass
then
true
else
false
fun helper2(pass_fail, final_grade) =
if xor(helper1(pass_fail), has_passed(final_grade))
then 1
else 0
in
case arr of
[] => 0
| (pass_fail, final_grade)::arr_rst => helper2(pass_fail, final_grade) + number_misgraded(arr_rst)
end
(* problem 5-7 *)
datatype 'a tree = leaf
| node of { value : 'a, left : 'a tree, right : 'a tree }
datatype flag = leave_me_alone | prune_me
(* problem 5 *)
fun tree_height(tree) =
case tree of
leaf => 0
| node {value=_, left=left_tree, right=right_tree} => 1 + Int.max(tree_height(left_tree), tree_height(right_tree))
(* problem 6 *)
fun sum_tree(tree) =
case tree of
leaf => 0
| node {value=v, left=left_tree, right=right_tree} => v + sum_tree(left_tree) + sum_tree(right_tree)
(* problem 7 *)
fun gardener(tree) =
case tree of
leaf => leaf
| node {value=v, left=left_tree, right=right_tree} =>
if v = prune_me
then
leaf
else
node {value=v, left=gardener(left_tree), right=gardener(right_tree)}
(* problem 8 *)
(* https://smlfamily.github.io/Basis/list.html *)
fun last(arr) =
case arr of
[] => raise Empty
| a::[] => a
| a::arr_rst => last(arr_rst)
(* problem 9-16 *)
datatype nat = ZERO | SUCC of nat
(* problem 9 *)
fun is_positive(nat) =
case nat of
ZERO => false
| _ => true
(* problem 10 *)
exception Negative
fun pred(nat) =
case nat of
ZERO => raise Negative
| SUCC a => a
(* problem 11 *)
fun nat_to_int(nat) =
case nat of
ZERO => 0
| SUCC a => 1 + nat_to_int(a)
(* problem 12 *)
fun int_to_nat(int) =
if int = 0
then ZERO
else SUCC(int_to_nat(int - 1))
(* problem 13 *)
fun add(nat1, nat2) =
case nat1 of
ZERO => nat2
| SUCC a => add(a, SUCC nat2)
(* problem 14 *)
fun sub(nat1, nat2) =
case nat2 of
ZERO => nat1
| SUCC a => sub(pred(nat1), a)
(* problem 15 *)
fun mult(nat1, nat2) =
let
fun helper(nat1, nat2, res) =
case nat1 of
ZERO => res
| SUCC a => helper(pred(nat1), nat2, add(res, nat2))
in
helper(nat1, nat2, ZERO)
end
(* problem 16 *)
fun less_than(nat1, nat2) =
case nat1 of
ZERO =>
(case nat2 of
ZERO => false
| SUCC a => true)
| SUCC a =>
(case nat2 of
ZERO => false
| SUCC b => less_than(pred(nat1), pred(nat2)))
(* problem 17-19*)
datatype intSet =
Elems of int list (*list of integers, possibly with duplicates to be ignored*)
| Range of { from : int, to : int } (* integers from one number to another *)
| Union of intSet * intSet (* union of the two sets *)
| Intersection of intSet * intSet (* intersection of the two sets *)
(* problem 19 *)
fun contain(arr, element) =
case arr of
[] => false
| a::arr_rst => (a = element) orelse contain(arr_rst, element)
fun union_list(arr, rst) =
case arr of
[] => rst
| a::arr_rst =>
(
if contain(rst, a)
then
union_list(arr_rst, rst)
else
union_list(arr_rst, a::rst)
)
fun inter_list(arr1, arr2, rst) =
case arr1 of
[] => rst
| a::arr1_rst =>
(
if contain(arr2, a)
then
inter_list(arr1_rst, arr2, rst @ [a])
else
inter_list(arr1_rst, arr2, rst)
)
fun range2list(from, to, rst) =
if from > to
then
rst
else
range2list(from + 1, to, rst @ [from])
fun toList(set) =
case set of
Elems a => union_list(a, [])
| Range {from=start, to=stop} => range2list(start, stop, [])
| Union (set1, set2) => union_list(toList(set1), toList(set2))
| Intersection (set1, set2) => inter_list(toList(set1), toList(set2), [])
(* problem 17 *)
fun isEmpty(set) =
case set of
Elems a =>
(
case a of
[] => true
| _ => false
)
| Range {from=start, to=stop} => start > stop
| Union (set1, set2) => isEmpty(set1) andalso isEmpty(set2)
| Intersection (set1, set2) => (inter_list(toList(set1), toList(set2), []) = [])
(* problem 18 *)
fun list_contain(list, num) =
case list of
[] => false
| a::list_rst => (a = num) orelse (list_contain(list_rst, num))
fun contains(set, num) =
case set of
Elems a => list_contain(a, num)
| Range {from=start, to=stop} => (start <= num) andalso (num <= stop)
| Union (set1, set2) => contains(set1, num) orelse contains(set2, num)
| Intersection (set1, set2) => contains(set1, num) andalso contains(set2, num)测试
(* https://gist.github.com/gfizz/11ba5ee6e1534d9a5bb8d2e6f682b0e2 *)
use "hw2_extra.sml";
val tests = [
("test1", [
(* 1 *) pass_or_fail{id=1, grade=NONE} = fail,
(* 2 *) pass_or_fail{id=2, grade=SOME(0)} = fail,
(* 3 *) pass_or_fail{id=3, grade=SOME(74)} = fail,
(* 4 *) pass_or_fail{id=4, grade=SOME(75)} = pass,
(* 5 *) pass_or_fail{id=5, grade=SOME(100)} = pass
]),
("test2", [
(* 1 *) has_passed{id=1, grade=NONE} = false,
(* 2 *) has_passed{id=2, grade=SOME(0)} = false,
(* 3 *) has_passed{id=3, grade=SOME(74)} = false,
(* 4 *) has_passed{id=4, grade=SOME(75)} = true,
(* 5 *) has_passed{id=5, grade=SOME(100)} = true
]),
("test3", [
(* 1 *) number_passed[] = 0,
(* 2 *) number_passed[{id=2, grade=NONE}] = 0,
(* 3 *) number_passed[{id=3, grade=SOME(74)}] = 0,
(* 4 *) number_passed[{id=4, grade=SOME(75)}] = 1,
(* 5 *) number_passed[{id=5, grade=SOME(100)},
{id=6, grade=SOME(0)}] = 1,
(* 6 *) number_passed[{id=6, grade=SOME(75)},
{id=7, grade=SOME(75)}] = 2,
(* 7 *) number_passed[{id=7, grade=SOME(60)},
{id=8, grade=SOME(70)},
{id=9, grade=NONE}] = 0
]),
("test4", [
(* 1 *) number_misgraded[] = 0,
(* 2 *) number_misgraded[(pass, {id=2, grade=SOME(75)})] = 0,
(* 3 *) number_misgraded[(pass, {id=3, grade=SOME(74)})] = 1,
(* 4 *) number_misgraded[(pass, {id=4, grade=NONE})] = 1,
(* 5 *) number_misgraded[(fail, {id=5, grade=SOME(0)})] = 0,
(* 6 *) number_misgraded[(fail, {id=6, grade=SOME(100)})] = 1,
(* 7 *) number_misgraded[(pass, {id=7, grade=SOME(80)}),
(pass, {id=8, grade=SOME(90)})] = 0,
(* 8 *) number_misgraded[(pass, {id=8, grade=NONE}),
(fail, {id=9, grade=SOME(75)})] = 2,
(* 9 *) number_misgraded[(fail, {id=9, grade=NONE}),
(pass, {id=8, grade=SOME(70)}),
(fail, {id=7, grade=SOME(90)})] = 2
]),
("test5", [
(* 1 *) tree_height(leaf) = 0,
(* 2 *) tree_height(node{value=leave_me_alone, left=leaf, right=leaf}) = 1,
(* 3 *) tree_height(node{value="2",
left=node{value="3", left=leaf, right=leaf},
right=leaf}) = 2,
(* 4 *) tree_height(node{value=true,
left=leaf,
right=node{value=false, left=leaf, right=leaf}}) = 2,
(* 5 *) tree_height(node{value=5,
left=node{value=5,
left=leaf,
right=node{value=5,
left=node{value=5, left=leaf, right=leaf},
right=leaf}},
right=node{value=5, left=leaf, right=leaf}}) = 4
]),
("test6", [
(* 1 *) sum_tree(leaf) = 0,
(* 2 *) sum_tree(node{value=2, left=leaf, right=leaf}) = 2,
(* 3 *) sum_tree(node{value=(~3),
left=node{value=4, left=leaf, right=leaf},
right=leaf}) = 1,
(* 4 *) sum_tree(node{value=0,
left=leaf,
right=node{value=(~3), left=leaf, right=leaf}}) = ~3,
(* 5 *) sum_tree(node{value=1,
left=node{value=2,
left=leaf,
right=node{value=3,
left=node{value=4, left=leaf, right=leaf},
right=leaf}},
right=node{value=5, left=leaf, right=leaf}}) = 15
]),
("test7", [
(* 1 *) gardener(leaf) = leaf,
(* 2 *) gardener(node{value=leave_me_alone, left=leaf, right=leaf}) =
(node{value=leave_me_alone, left=leaf, right=leaf}),
(* 3 *) gardener(node{value=prune_me, left=leaf, right=leaf}) = leaf,
(* 4 *) gardener(node{value=leave_me_alone,
left=leaf,
right=node{value=prune_me,
left=node{value=leave_me_alone, left=leaf, right=leaf},
right=leaf}}) = node{value=leave_me_alone, left=leaf, right=leaf},
(* 5 *) gardener(node{value=leave_me_alone,
left=node{value=leave_me_alone,
left=node{value=prune_me, left=leaf, right=leaf},
right=node{value=leave_me_alone,
left=leaf,
right=node{value=prune_me,
left=leaf,
right=node{value=prune_me, left=leaf, right=leaf}}}},
right=node{value=prune_me,
left=leaf,
right=node{value=leave_me_alone, left=leaf, right=leaf}}}) =
node{value=leave_me_alone,
left=node{value=leave_me_alone,
left=leaf,
right=node{value=leave_me_alone, left=leaf, right=leaf}},
right=leaf}
]),
("test9", [
(* 1 *) is_positive(ZERO) = false,
(* 2 *) is_positive(SUCC(ZERO)) = true,
(* 3 *) is_positive(SUCC(SUCC(ZERO))) = true
]),
("test10", [
(* 1 *) pred(ZERO) = ZERO andalso false handle Negative => true | _ => false,
(* 2 *) pred(SUCC(ZERO)) = ZERO,
(* 2 *) pred(SUCC(SUCC(ZERO))) = SUCC(ZERO)
]),
("test11", [
(* 1 *) nat_to_int(ZERO) = 0,
(* 2 *) nat_to_int(SUCC(ZERO)) = 1,
(* 3 *) nat_to_int(SUCC(SUCC(ZERO))) = 2
]),
("test12", [
(* 1 *) int_to_nat(~1) = ZERO andalso false handle Negative => true | _ => false,
(* 2 *) int_to_nat(~999) = ZERO andalso false handle Negative => true | _ => false,
(* 3 *) int_to_nat(0) = ZERO,
(* 4 *) int_to_nat(1) = SUCC(ZERO),
(* 5 *) int_to_nat(2) = SUCC(SUCC(ZERO))
]),
("test13", [
(* 1 *) add(ZERO, ZERO) = ZERO,
(* 2 *) add(ZERO, SUCC(SUCC(ZERO))) = SUCC(SUCC(ZERO)),
(* 3 *) add(SUCC(ZERO), ZERO) = SUCC(ZERO),
(* 4 *) add(SUCC(SUCC(ZERO)), SUCC(ZERO)) = SUCC(SUCC(SUCC(ZERO))),
(* 5 *) add(SUCC(SUCC(ZERO)), SUCC(SUCC(SUCC(ZERO)))) = SUCC(SUCC(SUCC(SUCC(SUCC(ZERO)))))
]),
("test14", [
(* 1 *) sub(ZERO, ZERO) = ZERO,
(* 2 *) sub(ZERO, SUCC(SUCC(ZERO))) = ZERO andalso false handle Negative => true | _ => false,
(* 3 *) sub(SUCC(ZERO), ZERO) = SUCC(ZERO),
(* 4 *) sub(SUCC(SUCC(ZERO)), SUCC(SUCC(ZERO))) = ZERO,
(* 5 *) sub(SUCC(SUCC(ZERO)), SUCC(SUCC(SUCC(ZERO)))) =
ZERO andalso false handle Negative => true | _ => false,
(* 6 *) sub(SUCC(SUCC(SUCC(ZERO))), SUCC(ZERO)) = SUCC(SUCC(ZERO))
]),
("test15", [
(* 1 *) mult(ZERO, ZERO) = ZERO,
(* 2 *) mult(ZERO, SUCC(ZERO)) = ZERO,
(* 3 *) mult(SUCC(SUCC(ZERO)), ZERO) = ZERO,
(* 4 *) mult(SUCC(ZERO), SUCC(SUCC(ZERO))) = SUCC(SUCC(ZERO)),
(* 5 *) mult(SUCC(SUCC(ZERO)), SUCC(SUCC(SUCC(ZERO)))) = SUCC(SUCC(SUCC(SUCC(SUCC(SUCC(ZERO))))))
]),
("test16", [
(* 1 *) less_than(ZERO, ZERO) = false,
(* 2 *) less_than(ZERO, SUCC(ZERO)) = true,
(* 3 *) less_than(SUCC(ZERO), SUCC(ZERO)) = false,
(* 4 *) less_than(SUCC(ZERO), SUCC(SUCC(SUCC(ZERO)))) = true,
(* 5 *) less_than(SUCC(SUCC(SUCC(SUCC(ZERO)))), SUCC(SUCC(ZERO))) = false
]),
("test17", [
(* 1 *) isEmpty(Elems[]) = true,
(* 2 *) isEmpty(Elems[0]) = false,
(* 3 *) isEmpty(Range{from=3, to=2}) = true,
(* 4 *) isEmpty(Range{from=0, to=0}) = false,
(* 5 *) isEmpty(Range{from=(~5), to=(~4)}) = false,
(* 6 *) isEmpty(Union(Elems[], Range{from=9, to=6})) = true,
(* 7 *) isEmpty(Union(Union(Elems[], Range{from=6, to=9}), Elems[])) = false,
(* 8 *) isEmpty(Union(Union(Range{from=1, to=(~1)}, Elems[]), Union(Elems[], Elems[]))) = true,
(* 9 *) isEmpty(Intersection(Elems[], Elems[])) = true,
(*10 *) isEmpty(Intersection(Elems[1, 2], Elems[])) = true,
(*11 *) isEmpty(Intersection(Range{from=9, to=6}, Elems[42])) = true,
(*12 *) isEmpty(Intersection(Elems[0], Range{from=1, to=2})) = true,
(*13 *) isEmpty(Intersection(Union(Elems[], Elems[42]), Elems[42, 41])) = false,
(*14 *) isEmpty(Intersection(Elems[0], Union(Elems[], Union(Range{from=9, to=6}, Intersection(Elems[1], Elems[0])))))
= true,
(*15 *) isEmpty(Union(Intersection(Elems[], Elems[]), Intersection(Elems[2, 0], Elems[1]))) = true,
(*16 *) isEmpty(Intersection(Intersection(Elems[1, 3, 5], Elems[2, 3, 6]), Elems[1, 2, 4])) = true,
(*17 *) isEmpty(Intersection(Intersection(Elems[1, 3, 5], Elems[2, 3, 6]), Elems[1, 3, 4])) = false,
(*18 *) isEmpty(Intersection(Intersection(Elems[1, 2], Elems[2, 3]), Intersection(Elems[2, 3], Elems[3, 4])))
= true,
(*19 *) isEmpty(Intersection(Union(Elems[1], Elems[2]), Intersection(Elems[1], Elems[1]))) = false,
(*20 *) isEmpty(Intersection(Union(Elems[1], Elems[2]), Intersection(Elems[2], Elems[2]))) = false,
(*21 *) isEmpty(Intersection(Union(Elems[1], Elems[2]), Intersection(Elems[3], Elems[3]))) = true,
(*22 *) isEmpty(Intersection(Intersection(Elems[1], Elems[1]), Union(Elems[1], Elems[2]))) = false,
(*23 *) isEmpty(Intersection(Intersection(Elems[2], Elems[2]), Union(Elems[1], Elems[2]))) = false,
(*24 *) isEmpty(Intersection(Intersection(Elems[3], Elems[3]), Union(Elems[1], Elems[2]))) = true
]),
("test18", [
(* 1 *) contains(Elems[], 0) = false,
(* 2 *) contains(Elems[42], 42) = true,
(* 3 *) contains(Elems[1, 3, 5, 7, 9], 7) = true,
(* 4 *) contains(Elems[~1, 1], 0) = false,
(* 5 *) contains(Range{from=3, to=2}, 3) = false,
(* 6 *) contains(Range{from=(~5), to=(~5)}, (~5)) = true,
(* 7 *) contains(Range{from=1, to=6}, 0) = false,
(* 8 *) contains(Union(Elems[1], Range{from=2, to=8}), 9) = false,
(* 9 *) contains(Union(Elems[42], Elems[42, 33]), 33) = true,
(*10 *) contains(Union(Range{from=0, to=5}, Union(Elems[~3, ~1, 1], Elems[])), ~1) = true,
(*11 *) contains(Intersection(Elems[1, 2, 3], Elems[2, 3, 4]), 1) = false,
(*12 *) contains(Intersection(Elems[~1, ~2], Elems[0, ~2]), ~2) = true,
(*13 *) contains(Intersection(Elems[1, 2, 3], Intersection(Elems[0, 2, 1], Elems[3, 1, 5])), 1) = true,
(*14 *) contains(Intersection(Union(Elems[1], Elems[2, 3]), Elems[3, 0]), 2) = false,
(*15 *) contains(Union(Intersection(Elems[0, 2, 4], Range{from=0, to=2}), Intersection(Elems[0, 4], Elems[0, 2])), 4)
= false
]),
("test19",
let
fun insert(xs, x) =
case xs of
[] => [x]
| x'::xs' => if x <= x' then x::xs else x'::insert(xs', x)
fun sort(xs) =
case xs of
[] => []
| x::xs' => insert(sort(xs'), x)
in
[
(* 1 *) toList(Elems[]) = [],
(* 2 *) toList(Elems[0, 0, 0]) = [0],
(* 3 *) sort(toList(Elems[3, 1, 2])) = [1, 2, 3],
(* 4 *) sort(toList(Elems[0, 5, ~1, 4, 3, 3, 0, ~1, 5, 2, 1, 4])) = [~1, 0, 1, 2, 3, 4, 5],
(* 5 *) sort(toList(Range{from=1, to=0})) = [],
(* 6 *) sort(toList(Range{from=0, to=1})) = [0, 1],
(* 7 *) sort(toList(Range{from=42, to=42})) = [42],
(* 8 *) sort(toList(Range{from=(~2), to=2})) = [~2, ~1, 0, 1, 2],
(* 9 *) sort(toList(Union(Elems[], Range{from=1, to=0}))) =[],
(*10 *) sort(toList(Union(Elems[3, 3, 0, 2, 0], Range{from=3, to=5}))) = [0, 2, 3, 4, 5],
(*11 *) sort(toList(Union(Union(Elems[1, 2, 1], Elems[3, 2, 4]), Union(Range{from=7, to=7}, Range{from=6, to=5}))))
= [1, 2, 3, 4, 7],
(*12 *) sort(toList(Intersection(Range{from=1, to=0}, Elems[]))) = [],
(*13 *) sort(toList(Intersection(Elems[5, 3, 1, ~1], Elems[1, 2, 3, 2, 1]))) = [1, 3],
(*14 *) sort(toList(Union(Union(Elems[7], Elems[0]), Intersection(Range{from=5, to=9}, Union(Elems[6], Elems[])))))
= [0, 6, 7],
(*15 *) sort(toList(Intersection(Union(Intersection(Range{from=1, to=5}, Range{from=3, to=7}), Elems[6]), Elems[4, 2, 6])))
= [4, 6]
]
end
)
]
(* Summarize *)
fun list_fails(tests) =
case tests of
[] => []
| (name, passes)::tests' =>
let fun help(bools, i) =
case bools of
[] => []
| true::bools' => help(bools', i + 1)
| false::bools' => (name ^ "-" ^ Int.toString(i))::help(bools', i + 1)
in
help(passes, 1) @ list_fails(tests')
end
val FAIL_LIST = list_fails(tests)
val ALL_PASSED = null FAIL_LIST本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere