现代编程思想 多元组，结构体与枚举类型 Hongbo Zhang 1 基础数据类型：多元组与结构体 2 回顾：多元组 多元组：固定⻓度的不同类型数据的集合 定义： (<表达式>, <表达式>, ...) 类型： (<表达式类型>, <表达式类型>, ...) 例如： 身份信息： ("Bob", 2023, 10, 24): (String, Int, Int, Int) 成员访问： ⼀个多元组类型的元素即是每个组成类型的元素构成的有序元素组 集合的笛卡尔积，⼜称积类型 例：扑克牌的所有花⾊：{ } 4 结构体 元组的问题在于，难以理解其所代表的数据 (String, Int) ：⼀个⼈的姓名和年龄？姓名和⼿机号？地址和邮编？ 结构体允许我们赋予名称 struct PersonalInfo { name: String; age: Int } struct ContactInfo 5 结构体的定义 结构体的定义形如 struct <结构体名称> { <字段名>: <类型> ; ... } struct PersonalInfo { name: String; age: Int} 定义结构体的值时，形如 { <字段名>: <值> , ... } let info: PersonalInfo = { name: "Moonbit", age: 1, } 结构体的值的定义不在意顺序：

赋值操作是⼀个命令 在⽉兔中，结构体的字段默认不可变，我们也允许可变的字段，需要⽤ mut 标识 1. struct Ref[T] { mut val : T } 2. 3. fn init { 4. let ref: Ref[Int] = { val: 1 } // ref 本身只是⼀个数据绑定 5. ref.val = 10 // 我们可以修改结构体的字段 6. println(ref println(ref.val.to_string()) // 输出 10 7. } 8 变量 我们可以将带有可变字段的结构体看作是引⽤ 1 var x = 1 x = 2 x 2 x let ref = { val : 1 } ref.val = 10 ref ref 1 10 val val mut ref = { val : 1 } ref = { val : 10 } } ref ref 1 1 val val 10 val 9 别名 指向相同的可变数据结构的两个标识符可以看作是别名 1. fn alter(a: Ref[Int], b: Ref[Int]) { 2. a.val = 10 3. b.val = 20 4. } 5. 6. fn init { 7. let x: Ref[Int] = { val : 1 } 8

1 ⽉兔MoonBit 现代静态类型多范式编程语⾔ 语法轻量，易上⼿ 参考资料: moonbitlang.cn 2 开发环境准备 3 ⽉兔开发环境 开发⼯具 VS Code插件：语⾔服务器、包级别构建等功能 命令⾏⼯具：项⽬级别构建、项⽬测试、依赖管理等功能 开发环境 浏览器环境（⽆命令⾏⼯具） 云原⽣开发环境 腾讯云Coding Gitpod.io Github 需要依赖云原⽣开发环境供应商，如腾讯云Coding等 新建/克隆仓库并启动开发环境后，安装"MoonBit Language"插件 进阶开发需安装命令⾏⼯具，或克隆云原⽣开发模板。后续参考⽉兔构建系统教程 6 本地开发环境 安装VS Code或VS Codium，并安装"MoonBit Language"插件 进阶开发需安装命令⾏⼯具（⽀持Windows、MacOS与Ubuntu等环境），并参考⽉ 兔构建系统教程 (2023, 10, 24).1 == 10 20 其他数据类型 ⽉兔有丰富的类型结构 函数类型 op_add : (Int, Int) -> Int 单值类型 (): Unit 列表类型 List::Cons(1, Nil): List[Int] …… 我们会在后续课程中⻅到它们，以及⾃定义数据结构 21 计算表达式的值 22 简化 vs 运⾏ 我们可以将⽉兔的表达式看作定义值的⼀种⽅式

但各个运行时的实现， 成熟度不一 • 使用扩展特性，基本 需要限定运行时 WASM 扩展特性 • 基本接口已在 WASM 1.0 标准化 • 但只能交换简单数据类型 • 交换缓冲区和高级数据结构的方法各有不一 WASM 外部语言接口（FFI） • WASI (WebAssembly System Interface) • 用于允许 WASM 代码调用操作系统的能力 （stdout、socket这些） wasm 独立运行时 .wasm 独立运行时 .wasm Kubernetes + WASM • 方法（2）直接将 WASM 看作镜像的可选架构 Kubernetes runwasi 插件 / crun 运行时（可选） WASM Image WASM 运行时（可选） WASM Image WASM Image WASM Image Kubernetes 用于 WASM 生态的价值

现代编程思想 树 Hongbo Zhang 1 数据结构：树 树 ⼆叉树 ⼆叉搜索树 ⼆叉平衡树 2 ⽣活中的树状图 ⽣活中有很多的数据的结构与⼀颗树相似 谱系图（⼜称，家族树） ⽂件结构 数学表达式 …… 3 树的逻辑结构 数据结构中，树是由有限个节点构成的具有层次关系的集合 节点是存储数据的结构，节点之间存在亲⼦关系：⽗节点和⼦节点 如果树不为空，则它拥有⼀个根节点：根节点没有⽗节点 如果没有⼦节点的节点可称为叶节点 任何节点不能是⾃⼰的后代节点：树中不能有环路 树的⼀条边指的是⼀对节点(u, v)，其中u是v的⽗节点或者v是u的⽗节点 4 树的逻辑结构 这不是⼀颗树 5 树的逻辑结构 计算机中的树根节点在上，⼦节点在⽗节点下⽅ 相关术语 节点的深度：根节点下到这个节点的路径的⻓度（边的数量） 根节点深度为0 节点的⾼度：节点下到叶节点的最⻓路径的⻓度 树的存储结构 树的存储⽅式有多种（以⼆叉树为例，省略节点存储的数据） 节点与⼦节点关系的列表： [ (0, 1), (0, 2), (1, 3) ] 代数数据结构定义 1. Node(0, 2. Node(1, 3. Leaf(3), 4. Empty), 5. Leaf(2)) 列表定义 数据的逻辑结构独⽴于存储结构 7 种类繁多的树结构 线段树

Function）；相对的，函数对类型的每个值定 义了输出的，我们称为完全函数（Total Function） 为了避免程序运⾏时因不被允许的操作中⽌，也为了区分对应合理与不合理输⼊的输 出，我们使⽤ Option[T] 这⼀数据结构 8 Option的定义 Option[T] 分为两种情况： ⽆值： None 有值： Some(value: T) 例如，我们可以⽤ Option 定义⼀个整数除法的完全函数 1. fn 整型的列表类型为 List[Int] 字符串的列表类型为 List[String] 浮点数的列表类型为 List[Double] 18 模式匹配 我们可以通过模式匹配来分情况查看列表的内部结构 match <表达式> { <模式1> => <表达式> <模式2> => <表达式> } 模式可以⽤数据的构造⽅式定义。模式中定义了标识符，其作⽤域为对应表达式 1. fn head_opt(list: head = 1 3. let tail = Cons(2, Nil) 4. Some(head) 5. } 21 模式匹配Option 同样地，我们也可以⽤模式匹配查看 Option 的结构来获得值 1. fn get_or_else(option_int: Option[Int], default: Int) -> Int { 2. match option_int { 3.

} 12. } 我们希望存储很多很多类型在堆栈中 每个类型都要定义⼀个对应的堆栈吗？ IntStack 和 StringStack 似乎结构⼀模⼀样？ 7 泛型数据结构与泛型函数 泛型数据结构与泛型函数以类型为参数，构建更抽象的结构 1. enum Stack[T] { 2. Empty 3. NonEmpty(T, Stack[T]) 4. } 5. fn Stack::empty[T]() rest) => (Some(top), rest) 11. } 12. } 将 T 替换为 Int 或 String 即相当于 IntStack 与 StringStack 8 泛型数据结构与泛型函数 我们⽤ [<类型1>, <类型2>, ...] 来定义泛型的类型参数 enum Stack[T]{ Empty; NonEmpty(T, Stack[T]) } struct Pair[A B } fn identity[A](value: A) { value } Stack 与 Pair 可以看做从类型上的函数：类型构造器 类型参数多数时候会根据参数被⾃动推导 9 泛型数据结构：队列 我们定义如下的操作： 1. fn empty[T]() -> Queue[T] // 创建空队列 2. fn push[T](q: Queue[T], x: T) -> Queue[T]

直接寻址（分离链接）：同⼀索引下⽤另⼀数据结构存储 列表 ⼆叉平衡搜索树等 开放寻址 线性探查：当发现冲突后，索引递增，直到查找空位放⼊ ⼆次探查（索引递增 ）等 4 哈希表：直接寻址 当发⽣哈希/索引冲突时，将相同索引的数据装进⼀个数据结构中 例：添加0、5（哈希值分别为0、5）⾄⻓度为5的数组中时： 0 5 5 哈希表：直接寻址 哈希表结构 1. struct Entry[K 添加/更新操作 添加时，根据键的哈希计算出应当存放的位置 遍历集合查找键 如果找到，修改值 否则，添加键值对 删除操作类同 0 3 1. 计算对应数组索引 4 9 2.遍历对应数据结构 7 哈希表：直接寻址 添加/更新操作 1. fn put[K : Hash + Eq, V](map : HT_bucket[K, V], key : K, value : V) -> Unit let index = key.hash().mod_u(map.length) // 计算对应索引 3. let mut bucket = map.values[index] // 找到对应数据结构 4. while true { 5. match bucket.val { 6. None => { // 如果没有找到，添加并退出循环 7. bucket

现代编程思想 队列：可变数据结构实现 Hongbo Zhang 1 队列 我们曾经介绍过队列这个数据结构 先进先出 利⽤两个堆栈进⾏实现 我们利⽤可变数据结构进⾏实现 基于数组的循环队列 单向链表 2 队列 我们实现以下函数（以整数队列为例） 1. struct Queue { .. } 2. 3. fn make() -> Queue // 创建空列表 4. fn push(self: start: 0, end: 0, length: 0 5. } 6. } 默认值应该是什么？ Option::None T::default() 10 单向链表 每个数据结构都指向下⼀个数据结构 像锁链⼀样相连 1. struct Node[T] { 2. val: T 3. mut next: Option[Node[T]] // 指向下⼀个节点 4. } 5. 6 Some(node) => aux2(node.next, 1 + cumul) 6. } 7. } 8. aux2(self.head, 0) 9. } 18 总结 本章节我们介绍了使⽤可变数据结构定义队列 循环队列与单向链表的实现 尾调⽤与尾递归 19

常⻅数据结构与算法 多种编程范式 关注模块化和组合性 3 课程⼯具 MoonBit⽉兔 现代静态类型多范式编程语⾔ 语法轻量，易上⼿ 浏览器开发环境、云原⽣开发环境或本地集成开发环境 4 课程概览 课程 主题 课程 主题 课程介绍与程序设计 接⼜：集合与表 ⾯向值编程 结构体 命令 函数 列表与递归 可变状态 与可变数据结构 列表 元组 嵌套模式 抽象堆栈结构机器 数据类型与树