https://www.coursera.org/learn/programming-languages/home

B站搬运：

https://www.bilibili.com/video/BV1dL411j7L7

https://www.coursera.org/learn/programming-languages/supplement/cVK0L/extra-practice-problems

### 代码

(* problem 1 *)
fun compose_opt f g x =
case g x of
NONE => NONE
| SOME y =>
case f y of
NONE => NONE
| SOME z => SOME z

(* problem 2 *)
fun do_until f p x =
if p x
then do_until f p (f x)
else x

(* problem 3 *)
fun factorial1 x =
let
fun f(x, prod) = (x - 1, x * prod)
fun p(x, prod) = not (x = 0)
in
#2 (do_until f p (x, 1))
end

(* problem 4 *)
fun fixed_point f x =
do_until f (fn x => not (x = (f x))) x

(* problem 5 *)
fun map2 f (x, y) =
(f x, f y)

(* problem 6 *)
fun app_all f g x =
let
val y = g x
fun helper arr =
case arr of
[] => []
| v::arr_rst => (f v) @ (helper arr_rst)
in
helper y
end

(* problem 7 *)
(* https://smlfamily.github.io/Basis/list.html#SIG:LIST.foldr:VAL *)
fun my_foldr f init xs =
let
val reverse_xs = List.rev xs
fun fold f init xs =
case xs of
[] => init
| x::xs' => fold f (f(x, init)) xs'
in
fold f init reverse_xs
end

(* problem 8 *)
fun partition f xs =
let
fun helper xs (first, second) =
case xs of
[] => (first, second)
| x::xs' =>
if f x
then helper xs' (first @ [x], second)
else helper xs' (first, second @ [x])
in
helper xs ([], [])
end

(* problem 9 *)
fun unfold f xs =
let
fun helper xs res =
case f xs of
NONE => res
| SOME (y, x) => helper x (res @ [y])
in
helper xs []
end

(* problem 10 *)
fun factorial2 x =
let
val arr = unfold (fn n => if n = 0 then NONE else SOME(n, n-1)) x
in
List.foldl (op *) 1 arr
end

(* problem 11 *)
fun my_map f arr =
let
fun helper (x, init) = [f x] @ init
in
List.foldr helper [] arr
end

(* problem 12 *)
fun my_filter f arr =
let
fun helper (x, init) =
if f x
then [x] @ init
else init
in
List.foldr helper [] arr
end

(* problem 13 *)
fun my_foldl f init xs =
let
val reverse_xs = List.rev xs
in
my_foldr f init reverse_xs
end

(* problem 14 *)
datatype 'a tree = Node of 'a * 'a tree * 'a tree
| Leaf

fun tree_map f tree =
case tree of
Leaf => Leaf
| Node (a, tree1, tree2) => Node (f(a), tree_map f tree1, tree_map f tree2)

fun tree_fold f init tree =
case tree of
Leaf => init
| Node (a, tree1, tree2) => f (a, (tree_fold f init tree1), (tree_fold f init tree2))

fun tree_filter f tree =
case tree of
Leaf => Leaf
| Node (a, tree1, tree2) =>
if f a
then Node (a, tree_filter f tree1, tree_filter f tree2)
else Leaf

### 测试

(* https://www.coursera.org/learn/programming-languages/discussions/weeks/4/threads/SUxukGoiEeuw8Q5h5Kj7KQ *)

use "hw3_extra.sml";

val tests = [
("test1",
let fun f s = if String.size s > 3 then SOME (explode s) else NONE
fun g i = if i > 0 then SOME (Int.toString i) else NONE
in
[
(* 1 *) compose_opt SOME SOME NONE = SOME NONE,
(* 2 *) compose_opt f g 0 = NONE,
(* 3 *) compose_opt f g 123 = NONE,
(* 4 *) compose_opt f g 1234 = SOME [#"1", #"2", #"3", #"4"]
]
end
),

("test2", [
(* 1 *) do_until (fn x => x div 2) (fn x => x mod 2 <> 1) 12 = 3
]),

("test3", [
(* 1 *) factorial1 0 = 1,
(* 2 *) factorial1 1 = 1,
(* 3 *) factorial1 2 = 2,
(* 4 *) factorial1 5 = 120
]),

("test4", [
(* 1 *) fixed_point (fn x => x) "a" = "a",
(* 2 *) fixed_point (fn x => if x > 0 then x - 1 else if x < 0 then x + 1 else x) 42 = 0,
(* 3 *) fixed_point (fn x => if x = 1 then x else if x mod 2 = 0 then x div 2 else 3 * x + 1) 2021 = 1
]),

("test5", [
(* 1 *) map2 (fn x => 2 * x) (1, 2) = (2, 4),
(* 2 *) map2 String.size ("first", "second") = (5, 6)
]),

("test6", [
(* 1 *) app_all (fn n => [n, 2 * n, 3 * n]) (fn n => [n, 2 * n, 3 * n]) 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9],
(* 2 *) app_all (fn n => [n, 2 * n, 3 * n]) (fn _ => []) 1 = [],
(* 3 *) app_all (fn _ => []) (fn n => [n, 2 * n, 3 * n]) 1 = [],
(* 4 *) app_all String.explode (map Int.toString) [12, 34, 56] = [#"1", #"2", #"3", #"4", #"5", #"6"]
]),

("test7", [
(* 1 *) my_foldr (op +) 42 [] = 42,
(* 2 *) my_foldr (op ^) "#" ["ab", "cd", "ef"] = "abcdef#"
]),

("test8", [
(* 1 *) partition (fn _ => true) ["a", "b", "c"] = (["a", "b", "c"], []),
(* 2 *) partition (fn _ => false) ["a", "b", "c"] = ([], ["a", "b", "c"]),
(* 3 *) partition (fn x => not x) [true, false, true] = ([false], [true, true]),
(* 4 *) partition (fn x => x mod 2 = 1) [] = ([], []),
(* 5 *) partition (fn x => x mod 2 = 0) [1, 2, 3, 4, 5] = ([2, 4], [1, 3, 5])
]),

("test9", [
(* 1 *) unfold (fn n => if n = 0 then NONE else SOME (n, n - 1)) 5 = [5, 4, 3, 2, 1],
(* 2 *) unfold (fn _ => NONE) true = [],
(* 3 *) unfold (fn xs => case xs of [] => NONE | _::xs' => SOME (xs, xs')) [1, 2, 3]
= [[1, 2, 3], [2, 3], ]
]),

("test10", [
(* 1 *) factorial2 0 = 1,
(* 2 *) factorial2 1 = 1,
(* 3 *) factorial2 2 = 2,
(* 4 *) factorial2 5 = 120
]),

("test11", [
(* 1 *) my_map (fn x => x) [] = [],
(* 2 *) my_map (op +) [(1, 2), (3, 4), (5, 6)] = [3, 7, 11],
(* 3 *) my_map String.size ["hello", "sml"] = [5, 3]
]),

("test12", [
(* 1 *) my_filter (fn _ => true) [] = [],
(* 2 *) my_filter (fn _ => true) [1, 2, 3] = [1, 2, 3],
(* 3 *) my_filter (fn _ => false) [1, 2, 3] = [],
(* 4 *) my_filter (fn s => String.size s < 3) ["a", "ab", "abc", "abcd"] = ["a", "ab"]
]),

("test13", [
(* 1 *) my_foldl (op +) 42 [] = 42,
(* 2 *) my_foldl (op ^) "#" ["ab", "cd", "ef"] = "efcdab#"
]),

("test14", [
(* 1 *) tree_map Int.toString Leaf = Leaf,
(* 2 *) tree_map Int.toString (Node (42, Leaf, Leaf)) = Node ("42", Leaf, Leaf),
(* 3 *) tree_map Int.toString (Node (1, Node (2, Leaf, Leaf), Node (3, Leaf, Node (4, Leaf, Leaf)))) =
(Node ("1", Node ("2", Leaf, Leaf), Node ("3", Leaf, Node ("4", Leaf, Leaf)))),
(* 4 *) tree_fold (fn (x, y, z) => x + y + z) 0 Leaf = 0,
(* 5 *) tree_fold (fn (x, y, z) => x + y + z) 0
(Node (1, Node (2, Leaf, Leaf), Node (3, Leaf, Node (4, Leaf, Leaf)))) = 10,
(* 6 *) tree_fold (fn tup => Node tup) Leaf
(Node (1, Node (2, Leaf, Leaf), Node (3, Leaf, Node (4, Leaf, Leaf)))) =
(Node (1, Node (2, Leaf, Leaf), Node (3, Leaf, Node (4, Leaf, Leaf)))),
(* 7 *) tree_filter (fn _ => true) Leaf = Leaf,
(* 8 *) tree_filter (fn _ => false) (Node (42, Leaf, Leaf)) = Leaf,
(* 9 *) tree_filter (fn x => x)
(Node (true,
Node (true,
Node (false, Leaf, Leaf),
Node (false,
Leaf,
Node (true, Leaf, Leaf))),
Node (true,
Node (true, Leaf, Leaf),
Node (false, Leaf, Leaf)))) =
(Node (true,
Node (true, Leaf,Leaf),
Node (true,
Node (true, Leaf, Leaf),
Leaf)))
])
]

(* Summarize *)

val list_fail =
let
fun pair_with_index i xs =
case xs of
[] => []
| x::xs' => (i, x) :: (pair_with_index (i + 1) xs')
val list_fail_index =
List.foldr (fn ((i, b), xs) => if b then xs else i :: xs) []
fun make_fail_info (s, bs) =
((List.map (fn i => s ^ ":" ^ (Int.toString i))) o list_fail_index o (pair_with_index 1)) bs
in
(List.foldr (op @) []) o (List.map make_fail_info)
end

val FAIL_LIST = list_fail tests
val ALL_PASSED = null FAIL_LIST