数据类型与结构：从列表到树的探索

### 数据类型与结构：从列表到树的探索 #### 1. 函数定义与模式匹配 在编程中，函数的定义和模式匹配是非常重要的概念。例如，下面的代码展示了如何将整数转换为字符串： ```sml fun iconv 0 = "0" | iconv n = iconv1 n; val iconv = fn : int -> string; and iconv1 0 = " " | iconv1 n = (iconv1 (n div 10))^(chr (n mod 10+ord "0")); val iconv1 = fn : int -> string; ``` 这个 `iconv` 函数用于将整数转换为字符串。当输入为 0 时，直接返回 "0"；否则，调用 `iconv1` 函数进行转换。`iconv1` 函数通过递归的方式，将整数的每一位转换为字符并拼接起来。 另外，还有一个函数 `symbs_to_string` 用于将符号列表转换为字符串： ```sml fun symbs_to_string [ ] = "" | symbs_to_string (h::t) = sconv h^symbs_to_string t; val symbs_to_string = fn : symbol list -> string; ``` 这个函数使用了模式匹配，当列表为空时返回空字符串；否则，将列表的头部元素转换为字符串并与剩余元素转换后的字符串拼接起来。 模式匹配是一种强大的编程技术，它允许我们根据不同的输入模式执行不同的操作。一般来说，函数可以通过以下方式定义： ```sml fn pattern1 => expression1 | pattern2 => expression2 | … ``` 其中，模式可以是以下几种类型： 1. 常量 2. 绑定变量 3. 模式列表 4. 模式元组 5. 数据类型模式 6. 通配符模式 `_` 当函数被调用时，参数会依次与每个模式进行匹配，直到找到匹配的模式。匹配规则如下： 1. 模式中的常量必须与参数中的位置相同。 2. 模式中的绑定变量将被设置为参数中对应位置的值。 3. 模式中的元组必须与参数中的元组在位置和结构上对应。 4. 模式中的列表必须与参数中的列表在位置和结构上对应。 5. 模式中的数据类型必须与参数中的数据类型在位置、构造函数和结构上对应。 6. 通配符模式可以匹配参数中对应位置的任何值。 一旦找到匹配的模式，就会返回相应表达式的值。 #### 2. 数据类型的应用 数据类型在编程中用于定义新的类型。我们可以定义具有固定离散值的类型，通过构造函数名来标识这些值。例如，我们可以定义一个表示书籍索引的类型： ```sml datatype entry = word of string | page of int; ``` 这个数据类型表示书籍预处理后的条目，可能是字符串单词或整数页码。 下面是一些相关的练习，帮助我们更好地理解数据类型的应用： 1. **添加页码到页码列表**：编写一个函数，将一个整数页码添加到整数页码列表的末尾，前提是该页码不在列表中。函数类型为 `int list -> int -> int list`。 2. **添加单词和页码到索引**：编写一个函数，将一个单词和页码添加到索引中。如果单词已经在索引中，将页码添加到该单词的页码列表中；如果单词不在索引中，创建一个新的条目。函数类型为 `(string * int list) list -> string -> int -> (string * int list) list`。 3. **从条目列表更新索引**：编写一个函数，根据条目列表更新索引。函数需要有绑定变量来表示条目列表、当前页码和索引。如果第一个条目是单词，则将其添加到当前页码的索引中，并使用剩余的条目列表更新新的索引；如果第一个条目是页码，则将该页码作为当前页码，使用剩余的条目列表更新索引。函数类型为 `entry list -> int -> (string * int list) list -> (string * int list) list`。 4. **从条目列表创建索引**：编写一个函数，根据条目列表创建索引。函数类型为 `entry list -> (string * int list) list`。 #### 3. 停车场记录处理 另一个例子是停车场记录的处理。我们可以定义一个数据类型来表示停车场的记录： ```sml datatype park = enter of string | exit of string | time of int; ``` 这个数据类型表示车辆的进入、离开和时间标记。 下面是相关的练习： 1. **添加注册号码和进入时间到元组列表**：编写一个函数，将注册号码和进入时间作为元组添加到元组列表中，按照注册号码的字母顺序排列。函数类型为 `string -> int -> (string * int) list -> (string * int) list`。 2. **更新元组列表**：编写一个函数，根据给定的注册号码找到元组，并将给定的离开时间添加到元组中的负进入时间中。函数类型为 `string -> int -> (string * int) list -> (string * int) list`。 3. **处理停车场列表**：编写一个函数，根据停车场列表、当前时间和元组列表，处理停车场列表以生成最终的元组列表。如果停车场列表为空，则返回元组列表；如果列表以时间开头，则使用该时间作为当前时间处理剩余的列表；如果列表以车辆进入的注册号码开头，则将注册号码和负当前时间作为新元组添加到元组列表中，并处理剩余的列表；如果列表以车辆离开的注册号码开头，则将当前时间添加到对应元组的负进入时间中，并处理剩余的列表。函数类型为 `park list -> int -> (string * int) list -> (string * int) list`。 #### 4. 道路车辆记录处理 道路车辆记录的处理也是一个有趣的应用场景。我们可以定义一个数据类型来表示道路上的事件： ```sml datatype event = car | bus | lorry | time of int * int; ``` 这个数据类型表示车辆（汽车、巴士、卡车）和时间记录。 下面是相关的练习： 1. **将车辆列表转换为摘要列表**：编写一个函数，将车辆列表转换为摘要列表，每个时间段的记录包含开始时间和该时间段内汽车、巴士和卡车的数量。函数类型为 `event list -> (int * int * int) -> event list -> (event * int * int * int) list`。 2. **查找没有巴士的时间段**：编写一个函数，返回摘要列表中所有没有巴士的时间段。函数类型为 `(event * int * int * int) list -> (event * int * int * int) list`。 3. **查找精确小时的摘要条目**：编写一个函数，返回摘要列表中所有时间为精确小时的摘要条目。函数类型为 `(event * int * int * int) list -> (event * int * int * int) list`。 4. **应用函数到满足条件的列表元素**：编写一个函数，将函数 `f` 应用到列表中满足属性 `p` 的所有元素上。函数类型为 `('a -> bool) -> ('a -> 'b) -> 'a list -> 'b list`。 5. **使用上述函数定义其他函数**：使用上一个函数来定义查找没有巴士的时间段和查找精确小时的摘要条目的函数。 ##