这次回顾HW3 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/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], [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