现代编程思想 多元组，结构体与枚举类型 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

现代编程思想 树 Hongbo Zhang 1 数据结构：树 树 ⼆叉树 ⼆叉搜索树 ⼆叉平衡树 2 ⽣活中的树状图 ⽣活中有很多的数据的结构与⼀颗树相似 谱系图（⼜称，家族树） ⽂件结构 数学表达式 …… 3 树的逻辑结构 数据结构中，树是由有限个节点构成的具有层次关系的集合 节点是存储数据的结构，节点之间存在亲⼦关系：⽗节点和⼦节点 如果树不为空，则它拥有⼀个根节点：根节点没有⽗节点 4 树的逻辑结构 这不是⼀颗树 5 树的逻辑结构 计算机中的树根节点在上，⼦节点在⽗节点下⽅ 相关术语 节点的深度：根节点下到这个节点的路径的⻓度（边的数量） 根节点深度为0 节点的⾼度：节点下到叶节点的最⻓路径的⻓度 叶节点⾼度为0 树的⾼度：根节点的⾼度 只有⼀个节点的树⾼度为0 空树（没有节点的树）⾼度为-1 也有的定义将树的⾼度等同于最⼤层次，以根为第⼀层 6 树的存储结构 树的存储⽅式有多种（以⼆叉树为例，省略节点存储的数据） 节点与⼦节点关系的列表： [ (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 课程概览 课程 主题 课程 主题 课程介绍与程序设计 接⼜：集合与表 ⾯向值编程 结构体 命令 函数 列表与递归 可变状态 与可变数据结构 列表 元组 嵌套模式 抽象堆栈结构机器 数据类型与树

度 ⽬标 通过特征，判断属于哪⼀类鸢尾花 构建并训练神经⽹络，正确率95%以上 2 神经⽹络 神经⽹络是机器学习的⼀种 模拟⼈的⼤脑神经结构 单个神经元通常有 多个输⼊ ⼀个输出 神经元在达到⼀定阈值后激活 通常分为多层结构 3 神经⽹络 ⼀个典型的神经⽹络通常包含 输⼊层：接受输⼊的参数 输出层：输出计算结果 隐含层：输⼊层与输出层之间的层级 神经⽹络的架构 验证集：在训练结束后验证成果，避免过拟合 数据量较少，可以直接进⾏完整训练 每⼀轮训练都使⽤训练集中的全部数据 如果数据较多，则需要考虑分批训练 16 总结 本章节介绍了神经⽹络的基础知识 神经⽹络的结构 神经⽹络的训练 具体实现参⻅⽉兔试⽤环境 参考资料 What is a neural network 17

List::[Const(0)], List:: [Const(1)]) if (result i32) i32.const 0 else i32.const 1 end 18 编译程序 利⽤内建 Buffer 数据结构，⽐字符串拼接更⾼效 1. fn Instruction::to_wasm(self : Instruction, buffer : Buffer) -> Unit 2. fn Function::to_wasm(self Buffer) -> Unit 3. fn Program::to_wasm(self : Program, buffer : Buffer) -> Unit 19 编译指令 利⽤内建 Buffer 数据结构，⽐拼接字符串更⾼效 1. fn Instruction::to_wasm(self : Instruction, buffer : Buffer) -> Unit { 2. match self 23 构建解释器 ⼀种可能的解释器 操作数栈 参与运算的数值 函数的返回数量，返回后的剩余代码 指令队列 当前执⾏的指令 分为普通指令和控制指令（如函数结束时的返回） 24 解释器结构 1. enum StackValue { 2. Val(Value) // 普通数值 3. // 函数堆栈，存放本地变量及剩余指令 4. Func(@map.Map[String, Value]