Programming Languages Part A HW1 Extra Practice Problems
这次回顾HW1 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/U9go7/extra-practice-problems
参考资料：
代码
(* helper function *)
fun append (xs : int list, ys : int list) =
if null xs
then ys
else hd (xs) :: append (tl(xs), ys)
(* problem 1 *)
fun alternate(arr: int list) =
let
fun helper(arr: int list, sign: int) =
if null arr
then 0
else
(hd arr) * sign + helper((tl arr), (~1) * sign)
in
helper(arr, 1)
end
(* problem 2 *)
fun min_max(arr: int list) =
let
fun max(a: int, b: int) =
if a >= b
then a
else b
fun min(a: int, b: int) =
if a >= b
then b
else a
fun helper(arr: int list, min_num: int, max_num: int) =
if null arr
then (min_num, max_num)
else helper((tl arr), min(min_num, (hd arr)), max(max_num, (hd arr)))
in
helper(arr, (hd arr), (hd arr))
end
(* problem 3 *)
fun cumsum(arr: int list) =
let
fun helper(arr: int list, par_sum: int) =
if null arr
then
[]
else
let
val a = par_sum + (hd arr)
in
a::helper((tl arr), a)
end
in
helper(arr, 0)
end
(* problem 4 *)
fun greeting(name: string option) =
if isSome name
then "Hello there, " ^ (valOf name) ^ "!"
else "Hello there, you!"
(* problem 5 *)
fun repeat(arr1: int list, arr2: int list) =
let
fun helper(a: int, n: int) =
if n = 0
then
[]
else
a::helper(a, n - 1)
in
if null arr1
then
[]
else
append(helper((hd arr1), (hd arr2)), repeat((tl arr1), (tl arr2)))
end
(* problem 6 *)
fun addOpt(a: int option, b: int option) =
if (isSome a) andalso (isSome b)
then
SOME ((valOf a) + (valOf b))
else
NONE
(* problem 7 *)
fun addAllOpt(arr: int option list) =
let
fun addOpt(a: int option, b: int option) =
if (isSome a) andalso (isSome b)
then
SOME ((valOf a) + (valOf b))
else
if (isSome a)
then
SOME (valOf a)
else
if (isSome b)
then
SOME (valOf b)
else
NONE
fun helper(arr: int option list, res: int option) =
if null arr
then res
else
helper((tl arr), addOpt(res, (hd arr)))
in
helper(arr, NONE)
end
(* problem 8 *)
fun any(arr: bool list) =
if null arr
then false
else
if (hd arr)
then true
else any((tl arr))
(* problem 9 *)
fun all(arr: bool list) =
if null arr
then true
else
if not (hd arr)
then false
else all((tl arr))
(* problem 10 *)
fun zip(arr1: int list, arr2: int list) =
let
fun helper(arr1: int list, arr2: int list) =
if (null arr1) orelse (null arr2)
then
[]
else
((hd arr1), (hd arr2))::helper((tl arr1), (tl arr2))
in
helper(arr1, arr2)
end
(* problem 11 *)
fun zipRecycle(arr1: int list, arr2: int list) =
let
fun len(arr: int list) =
if null arr
then 0
else 1 + len((tl arr))
fun get_i(arr: int list, i: int) =
let
val n = len(arr)
in
if i >= n
then get_i(arr, (i mod n))
else
if i = 0
then
(hd arr)
else
get_i((tl arr), i - 1)
end
fun max(a: int, b: int) =
if a > b
then a
else b
val len1 = len(arr1)
val len2 = len(arr2)
val len = max(len1, len2)
fun helper(arr1: int list, arr2: int list, i: int) =
if i = len
then
[]
else
(get_i(arr1, i), get_i(arr2, i))::helper(arr1, arr2, i + 1)
in
helper(arr1, arr2, 0)
end
(* problem 12 *)
fun zipOpt(arr1: int list, arr2: int list) =
let
fun len(arr: int list) =
if null arr
then 0
else 1 + len((tl arr))
fun helper(arr1: int list, arr2: int list) =
if (null arr1) orelse (null arr2)
then
[]
else
((hd arr1), (hd arr2))::helper((tl arr1), (tl arr2))
val l1 = len(arr1)
val l2 = len(arr2)
val flag = (l1 = l2)
in
if flag
then
SOME (zip(arr1, arr2))
else
NONE
end
(* problem 13 *)
fun lookup(table: (string * int) list, s: string) =
if null table
then
NONE
else
let
val pair = (hd table)
in
if (#1 pair) = s
then SOME (#2 pair)
else lookup((tl table), s)
end
(* problem 15 *)
fun splitAt(arr: int list, threshold: int) =
let
fun helper(arr: int list, small: int list, big: int list) =
if
null arr
then
(small, big)
else
if (hd arr) < threshold
then
helper((tl arr), append(small, [(hd arr)]), big)
else
helper((tl arr), small, append(big, [(hd arr)]))
in
helper(arr, [], [])
end
(* problem 14 *)
fun splitup(arr: int list) =
splitAt(arr, 0)
(* problem 16 *)
fun isSorted(arr: int list) =
if null arr
then
true
else
if null (tl arr)
then true
else
if (hd arr) > (hd (tl arr))
then false
else isSorted((tl arr))
(* problem 17 *)
fun isIncreasingSorted(arr: int list) =
isSorted(arr)
fun isDecreasingSorted(arr: int list) =
if null arr
then
true
else
if null (tl arr)
then true
else
if (hd arr) <= (hd (tl arr))
then false
else isDecreasingSorted((tl arr))
fun isAnySorted(arr: int list) =
isIncreasingSorted(arr) orelse isDecreasingSorted(arr)
(* problem 18 *)
fun sortedMerge(arr1: int list, arr2: int list) =
let
fun helper(arr1: int list, arr2: int list, res: int list) =
if null arr1
then
append(res, arr2)
else
if null arr2
then
append(res, arr1)
else
if (hd arr1) < (hd arr2)
then
helper((tl arr1), arr2, append(res, [(hd arr1)]))
else
helper(arr1, (tl arr2), append(res, [(hd arr2)]))
in
helper(arr1, arr2, [])
end
(* problem 19 *)
fun qsort(arr: int list) =
if null arr
then
[]
else
if null (tl arr)
then
arr
else
let
val a = (hd arr)
val p = splitAt(arr, a)
val sorted_small = qsort((#1 p))
val sorted_big = qsort((tl (#2 p)))
in
(* sortedMerge(sorted_small, sorted_big) *)
append(sorted_small, a::sorted_big)
end
(* problem 20 *)
fun divide(arr: int list) =
let
fun helper(arr: int list, r1: int list, r2: int list, flag: int) =
if null arr
then
(r1, r2)
else
if flag = 0
then
helper((tl arr), append(r1, [(hd arr)]), r2, 1 - flag)
else
helper((tl arr), r1, append(r2, [(hd arr)]), 1 - flag)
in
helper(arr, [], [], 0)
end
(* problem 21 *)
fun not_so_quick_sort(arr: int list) =
if null arr
then
[]
else
if null (tl arr)
then
arr
else
let
val p = divide(arr)
val arr1 = (#1 p)
val arr2 = (#2 p)
in
sortedMerge(not_so_quick_sort(arr1), not_so_quick_sort(arr2))
end
(* problem 22 *)
fun fullDivide(k: int, n: int) =
let
fun helper(n: int, d: int) =
if not ((n mod k) = 0)
then
(d, n)
else
helper(n div k, d + 1)
in
helper(n, 0)
end
(* problem 23 *)
fun factorize(n: int) =
let
fun append (xs : (int * int) list, ys : (int * int) list) =
if null xs
then ys
else hd (xs) :: append (tl(xs), ys)
fun helper(m: int, d: int, res: (int * int) list) =
if m = 1
then
res
else
let
val p = fullDivide(d, m)
val t = (#1 p)
in
if t = 0
then
helper((#2 p), d + 1, res)
else
helper((#2 p), d + 1, append(res, [(d, t)]))
end
in
helper(n, 2, [])
end
(* problem 24 *)
fun multiply(arr: (int * int) list) =
let
fun exp(k: int, n: int) =
if n = 0
then 1
else k * exp(k, n - 1)
fun helper(arr: (int * int) list, res: int) =
if null arr
then
res
else
helper((tl arr), exp((hd arr)) * res)
in
helper(arr, 1)
end
(* problem 25 *)
fun all_products(arr: (int * int) list) =
let
(* d ^ 0, ... , d ^ 1, 递增 *)
fun get_products(d: int, k: int, res: int) =
if k = 0
then
[res]
else
res::get_products(d, k - 1, res * d)
(* arr中每个元素乘以d, 保持递增 *)
fun prod_arr(d: int, arr: int list) =
let
fun helper(arr: int list, res: int list) =
if null arr
then
res
else
helper((tl arr), append(res, [d * (hd arr)]))
in
helper(arr, [])
end
(* for d in arr1, 计算prod_arr, 然后merge *)
fun prod_helper(arr1: int list, arr2: int list) =
if null arr1
then
[]
else
let
val r1 = prod_arr((hd arr1), arr2)
val r2 = prod_helper((tl arr1), arr2)
in
sortedMerge(r1, r2)
end
fun helper(arr: (int * int) list) =
if null arr
then
[]
else
if null (tl arr)
then
get_products((#1 (hd arr)), (#2 (hd arr)), 1)
else
let
val arr1 = get_products((#1 (hd arr)), (#2 (hd arr)), 1)
val arr2 = helper((tl arr))
in
prod_helper(arr1, arr2)
end
in
helper(arr)
end测试
use "hw1_extra.sml";
val test1_1 = alternate ([1, 2, 3, 4]) = ~2
val test1_2 = alternate ([1, 2, 4, 3]) = 0
val test2_1 = min_max ([1, 2, 3, 4]) = (1, 4)
val test2_2 = min_max ([9, 8, 3, 7]) = (3, 9)
val test3_1 = cumsum ([1, 2, 3, 4]) = [1, 3, 6, 10]
val test3_2 = cumsum ([9, 8, 3, 7]) = [9, 17, 20, 27]
val test4_1 = greeting (SOME "Tom") = "Hello there, Tom!"
val test4_2 = greeting (NONE) = "Hello there, you!"
val test5_1 = repeat ([1,2,3], [4,0,3]) = [1,1,1,1,3,3,3]
val test5_2 = repeat ([1,2], [5, 6]) = [1,1,1,1,1,2,2,2,2,2,2]
val test6_1 = addOpt (SOME 1, SOME 4) = SOME 5
val test6_2 = addOpt (SOME 1, NONE) = NONE
val test6_3 = addOpt (NONE, SOME 2) = NONE
val test6_4 = addOpt (NONE, NONE) = NONE
val test7_1 = addAllOpt ([SOME 1, NONE, SOME 3]) = SOME 4
val test7_2 = addAllOpt ([NONE, NONE, NONE]) = NONE
val test8_1 = any ([true, false, false]) = true
val test8_2 = any ([false, false, false]) = false
val test8_3 = any ([]) = false
val test9_1 = all ([true, false, false]) = false
val test9_2 = all ([false, false, false]) = false
val test9_3 = all ([]) = true
val test9_4 = all ([true, true]) = true
val test10_1 = zip ([1,2,3], [4, 6]) = [(1,4), (2,6)]
val test11_1 = zipRecycle ([1,2,3], [4, 6]) = [(1,4), (2,6), (3, 4)]
val test11_2 = zipRecycle ([1,2,3], [1, 2, 3, 4, 5, 6, 7]) = [(1,1), (2,2), (3, 3), (1,4), (2,5), (3,6), (1,7)]
val test12_1 = zipOpt ([1,2,3], [4, 6]) = NONE
val test12_2 = zipOpt ([1,2], [4, 6]) = SOME [(1, 4), (2, 6)]
val test13_1 = lookup([("abc", 1), ("tom", 2)], "abc") = SOME 1
val test13_2 = lookup([("abc", 1), ("tom", 2)], "def") = NONE
val test14_1 = splitup([1, 6, 5, 4, 2]) = ([], [1, 6, 5, 4, 2])
val test14_2 = splitup([~1, ~6, ~5, ~4, ~2]) = ([~1, ~6, ~5, ~4, ~2], [])
val test14_3 = splitup([3, ~6, 6, ~4, ~2]) = ([~6, ~4, ~2], [3, 6])
val test15_1 = splitAt([1, 6, 5, 4, 2], 3) = ([1, 2], [6, 5, 4])
val test15_2 = splitAt([1, 6, 5, 4, 2], 5) = ([1, 4, 2], [6, 5])
val test16_1 = isSorted([1, 2, 3]) = true
val test16_2 = isSorted([1, 5, 3]) = false
val test17_1 = isAnySorted([1, 2, 3]) = true
val test17_2 = isAnySorted([1, 5, 3]) = false
val test17_3 = isAnySorted([7, 5, 3]) = true
val test18_1 = sortedMerge ([1,4,7], [5,8,9]) = [1,4,5,7,8,9]
val test19_1 = qsort ([]) = []
val test19_2 = qsort ([1]) = [1]
val test19_3 = qsort ([2, 1]) = [1, 2]
val test19_4 = qsort ([2, 1, 3]) = [1, 2, 3]
val test19_5 = qsort ([6, 10, 5, 3, 2, 11, 12]) = [2, 3, 5, 6, 10, 11, 12]
val test20_1 = divide ([1,2,3,4,5,6,7]) = ([1,3,5,7], [2,4,6])
val test21_1 = not_so_quick_sort ([]) = []
val test21_2 = not_so_quick_sort ([1]) = [1]
val test21_3 = not_so_quick_sort ([2, 1]) = [1, 2]
val test21_4 = not_so_quick_sort ([2, 1, 3]) = [1, 2, 3]
val test21_5 = not_so_quick_sort ([6, 10, 5, 3, 2, 11, 12]) = [2, 3, 5, 6, 10, 11, 12]
val test22_1 = fullDivide (2, 40) = (3, 5)
val test22_2 = fullDivide((3,10)) = (0, 10)
val test23_1 = factorize(20) = [(2,2), (5,1)]
val test23_2 = factorize(36) = [(2,2), (3,2)]
val test23_3 = factorize(1) = []
val test24_1 = multiply([(2,2), (5,1)]) = 20
val test24_2 = multiply([(2,2), (3,2)]) = 36
val test25_1 = all_products([(2,2), (5,1)]) = [1,2,4,5,10,20]
val test25_2 = all_products([(2,2)]) = [1,2,4]
(* https://gist.github.com/gbaptista/c3e92d00b729515bd63865b299143e76#file-tests-sml *)
val test1 = alternate([1,2,3,4]) = ~2;
val test2 = min_max([5,1,3,8,4,2,3]) = (1, 8);
val test3 = cumsum([1,4,20,30]) = [1,5,25,55];
val test4 = greeting(NONE) = "Hello there, you!"
val test4b = greeting(SOME "gbaptista") = "Hello there, gbaptista!"
val test5 = repeat([1,2,3], [4,0,3]) = [1,1,1,1,3,3,3]
val test6 = addOpt(SOME 2, SOME 3) = SOME 5
val test6b = addOpt(SOME 2, NONE) = NONE
val test6c = addOpt(NONE, SOME 3) = NONE
val test6d = addOpt(NONE, NONE) = NONE
val test7 = addAllOpt ([SOME 1, NONE, SOME 3]) = SOME 4
val test8 = any([]) = false
val test8b = any([false, false, true, false]) = true
val test8c = any([false, false]) = false
val test9 = all([]) = true
val test9b = all([false, false, true, false]) = false
val test9c = all([false, false]) = false
val test9d = all([true, true, true]) = true
val test10 = zip ([1,2,3], [4,6]) = [(1,4), (2,6)]
val test11 = zipRecycle([1,2,3], [1,2,3,4,5,6,7]) = [(1,1), (2,2), (3,3),(1,4),(2,5),(3,6),(1,7)]
val test12 = zipOpt ([1,2,3], [4,6]) = NONE
val test12b = zipOpt ([1,2], [4,6]) = SOME [(1,4), (2,6)]
val test13 = lookup ([("test", 3), ("lorm", 7)], "a") = NONE
val test13b = lookup ([("test", 3), ("lorm", 7)], "test") = SOME 3
val test13c = lookup ([("test", 3), ("lorm", 7)], "lorm") = SOME 7
val test14 = splitup ([1,2,3,4,0,~4,~5,~1,2,~7]) = ([~4,~5,~1,~7],[1,2,3,4,0,2])
val test15 = splitAt ([8,4,1,0,2,9,3,7,1,4], 4) = ([1,0,2,3,1],[8,4,9,7,4])
val test16 = isSorted ([1,2,3]) = true
val test16b = isSorted ([1,2,3,0]) = false
val test16c = isSorted ([1,1]) = true
val test17 = isAnySorted([1,2,3]) = true
val test17b = isAnySorted([3,2,1]) = true
val test17c = isAnySorted([3,2,1,4]) = false
val test18 = sortedMerge([1,4,7],[5,8,9]) = [1,4,5,7,8,9]
val test18b = sortedMerge([1,4,7],[5,8,9,10,11,13]) = [1,4,5,7,8,9,10,11,13]
val test18c = sortedMerge([1,2,3,4],[5,8,9]) = [1,2,3,4,5,8,9]
val test18d = sortedMerge([1],[2]) = [1,2]
val test18e = sortedMerge([2],[1]) = [1,2]
val test18f = sortedMerge([2,3],[0]) = [0,2,3]
val test19 = qsort([11, 13,1,42,2,11,3,2,14,8,7]) = [1,2,2,3,7,8,11,11,13,14,42]
val test19b = qsort([2,1]) = [1,2]
val test19c = qsort([2,1,4,2,3,0,9]) = [0,1,2,2,3,4,9]
val test19d = qsort([1]) = [1]
val test19e = qsort([]) = []
val test20 = divide([1,2,3,4,5,6,7,8,9]) = ([1,3,5,7,9],[2,4,6,8])
val test20b = divide([1,2,3]) = ([1,3],[2])
val test20c = divide([1,2]) = ([1],[2])
val test20d = divide([1]) = ([1],[])
val test20e = divide([]) = ([],[])
val test21 = not_so_quick_sort([11, 13,1,42,2,11,3,2,14,8,7]) = [1,2,2,3,7,8,11,11,13,14,42]
val test21b = not_so_quick_sort([2,1]) = [1,2]
val test21c = not_so_quick_sort([2,1,4,2,3,0,9]) = [0,1,2,2,3,4,9]
val test21d = not_so_quick_sort([1]) = [1]
val test21e = not_so_quick_sort([]) = []
val test22 = fullDivide(2,40) = (3,5)
val test22b = fullDivide(3,10) = (0,10)
val test23 = factorize(20) = [(2,2),(5,1)]
val test23b = factorize(36) = [(2,2),(3,2)]
val test23c = factorize(878698923) = [(3,1),(23,1),(937,1),(13591,1)]
val test24 = multiply([(2,2),(5,1)]) = 20
val test24b = multiply([(2,2),(3,2)]) = 36
val test24c = multiply([(3,1),(23,1),(937,1),(13591,1)]) = 878698923
val test25 = all_products([(2,2),(5,1)]) = [1,2,4,5,10,20]
val test25b = all_products([(2,2),(3,2)]) = [1,2,3,4,6,9,12,18,36]
val test25c = all_products([(2,1),(3,1)]) = [1,2,3,6]
val test25d = all_products([(2,1),(3,1),(5,1)]) = [1,2,3,5,6,10,15,30]本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere