Progamming Languages 第一部分作业

发表于 2019-03-13 分类于编程与算法，课程笔记阅读次数：本文字数： 1.5k 阅读时长 ≈ 5 分钟

本篇博客为 coursera programming languages 课程的第一部分的课程作业。

作业要求

完成 11 个关于日期的 SML 函数
在所有的问题中，日期的类型均为 int*int*int（年月日）
- 一个合理的日期的年份为正数，月份在 1-12 之间，日期不超过 31（暂未考虑月份的限制）
day of year 代表一个从 1-365 之间的数字，可以用来特定到某一天

问题及解答

问题 1

完成一个函数 is_order
- 输入为两个日期
- 输出为 true 或 false
如果前一个日期在后一个日期之前，则输出 true ，否则输出 false

解答

获取具体的年月日，逐一比较即可
使用 let 表达式使函数更加简洁

fun is_older (date1 : int * int * int, date2 : int * int * int) =
    let 
        val y1 = #1 date1
        val m1 = #2 date1
        val d1 = #3 date1
        val y2 = #1 date2
        val m2 = #2 date2
        val d2 = #3 date2
    in
        y1 < y2 orelse (y1=y2 andalso m1 < m2)
                orelse (y1=y2 andalso m1=m2 andalso d1 < d2)
    end

问题 2

完成一个函数 number_in_month
- 输入为一个日期的 list 和一个月份
- 输出为 list 中有多少日期在给定月份中

解答

使用递归遍历 list 即可

fun number_in_month (dates : (int * int * int) list, month : int) =
    if null dates
    then 0
    else if #2 (hd dates) = month
    then 1 + number_in_month(tl dates, month)
    else number_in_month(tl dates, month)

问题 3

完成一个函数 number_in_months
- 输入为一个日期的 list 和一个月份的 list
- 输出为 list 中有多少日期在给定 list 包含的月份中
假设月份 list 中没有重复

解答

使用上一个问题的结果，构建递归

fun number_in_months(dates : (int * int * int) list, months : int list) =
    if null months
    then 0
    else number_in_month(dates, hd months) + number_in_months(dates, tl months)

问题 4

完成一个函数 date_in_month
- 输入为一个日期的 list 和一个月份
- 输出为位于给定月份中的日期组成的 list
日期的顺序保持原样

解答

与问题 2 类似

fun dates_in_month (dates : (int * int * int) list, month : int) =
    if null dates
    then []
    else if #2 (hd dates) = month
    then (hd dates)::dates_in_month(tl dates, month)
    else dates_in_month(tl dates, month)

问题 5

完成一个函数 date_in_months
- 输入为一个日期的 list 和一个月份的 list
- 输出为位于任意一个给定月份中的日期组成的 list

解答

与问题 3 类似
使用 @ 连接符连接两个 list

fun dates_in_months(dates : (int * int * int) list, months : int list) =
    if null months
    then []
    else dates_in_month(dates, hd months) @ dates_in_months(dates, tl months)

问题 6

完成一个函数 get_nth
- 输入为一个 string list 和一个整数 n
- 输出为该 list 的第 n 个元素
  - 从 1 开始计数

解答

使用递归遍历 list

fun get_nth (lst : string list, n : int) =
    if n=1
    then hd lst
    else get_nth(tl lst, n-1)

问题 7

完成一个函数 date_to_string
- 输入为一个日期
- 输出为一个字符串（如 January 20, 2013）
使用操作符 ^ 来连接字符串
使用库函数 Int.toString 来将 int 转换为 string

解答

构建一个月份的 string list，使用问题 6 的结果将月份转换为 string
年份和日期直接转换即可

fun date_to_string (date : int * int * int) =
    let
        val names = ["January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"]
    in
        get_nth(names,#2 date) ^ " " ^ Int.toString(#3 date) ^ ", " ^ Int.toString(#1 date)
    end

问题 8

完成一个函数 number_before_reaching_sum
- 输入一个整数 sum 和一个 int list
  - 假设均为正数
- 返回一个整数 n
  - list 的前 n 个元素的和小于 sum
  - 前 n+1 个元素的和大于等于 sum

解答

使用递归遍历 list
- 注意等号的处理

fun number_before_reaching_sum (sum : int, lst : int list) =
    if sum <= hd lst
    then 0
    else 1 + number_before_reaching_sum(sum - hd lst, tl lst)

问题 9

完成一个函数 what_month
- 输入一个 day of year
- 返回其所属的月份

解答

构建一个每月日期的 list，使用问题 8 的结果计算所属月份

fun what_month (day_of_year : int) =
    let
        val month_lengths = [31,28,31,30,31,30,31,31,30,31,30,31]
    in
        1 + number_before_reaching_sum(day_of_year, month_lengths)
    end

问题 10

完成一个函数 month_range
- 输入两个 day of the year： day1 和 day2
- 返回一个 int list [m1,m2,...,mn]
  - 其中 m1 是 day1 的月份, m2 是 day1+1 的月份...... mn 是 day2 的月份

解答

使用问题 9 的结果，通过递归生成 list

fun month_range (day1 : int, day2 : int) =
    if day1 > day2
    then []
    else what_month day1 :: month_range(day1 + 1, day2)

问题 11

完成一个函数 oldest
- 输入一个日期的 list
- 输出一个 (int*int*int) option
  - 如果 list 中不包含日期，则为 NONE
  - 否则返回 SOME d ，其中 d 是 list 中最早的日期

解答

使用问题 1 的结果，通过递归查找
- 标准答案使用了多个 let 表达式
  - 第一个 let 用于生成 option
  - 第二个 let 用于避免重复的递归

fun oldest (dates : (int * int * int) list) =
    if null dates
    then NONE
    else let 
             fun f dates =
                 if null (tl dates)
                 then hd dates
                 else let
                          val ans = f (tl dates)
                      in
                          if is_older(ans, hd dates)
                          then ans
                          else hd dates
                      end
          in
              SOME(f dates)
          end

问题 12（挑战问题）

完成两个函数 number_in_months_challenge 和 dates_in_months_challenge
- 其与问题 3 和问题 5 类似，只是现在月份的 list 允许存在重复

解答

先构建一个函数，去除重复
- mem 函数判断 x 在 xs 中是否存在

fun mem(x : int, xs : int list) =
    not (null xs) andalso (x = hd xs orelse mem(x, tl xs))
fun remove_duplicates(xs : int list) =
    if null xs
    then []
    else
        let 
            val tl_ans = remove_duplicates (tl xs)
        in
            if mem(hd xs, tl_ans)
            then tl_ans
            else (hd xs)::tl_ans
        end

fun number_in_months_challenge(dates : (int * int * int) list, months : int list) =
    number_in_months(dates, remove_duplicates months)

fun dates_in_months_challenge (dates : (int * int * int) list, months : int list) =
    dates_in_months(dates, remove_duplicates months)

问题 13（挑战问题）

完成一个函数 reasonable_date
- 输入一个日期
- 输出其是否为一个合法的日期

解答

列出所有规则，逐一判断即可
- 比较复杂的规则为每个月的合理天数

fun reasonable_date (date : int * int * int) =
    let    
        fun get_nth (lst : int list, n : int) =
            if n=1
            then hd lst
            else get_nth(tl lst, n-1)
        val year  = #1 date
        val month = #2 date
        val day   = #3 date
        val leap  = year mod 400 = 0 orelse (year mod 4 = 0 andalso year mod 100 <> 0)
        val feb_len = if leap then 29 else 28
        val lengths = [31,feb_len,31,30,31,30,31,31,30,31,30,31]
    in
        year > 0 andalso month >= 1 andalso month <= 12
        andalso day >= 1 andalso day <= get_nth(lengths,month)
    end