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. val : 1 } 8. alter(x, x) 9. println(x.val.to_string()) // x.val的值将会被改变两次 10. } 10 别名 指向相同的可变数据结构的两个标识符可以看作是别名 x val 1 alter(x, x) a init b x val 10 alter(x, x) a init b x val 20 alter(x ⽉兔也会检查函数返回结果是否与类型声明相同，可以避免错误的返回类型声明 21 可变数据 使⽤场景⼴泛 直接操作程序外环境，如硬件等 ⼀些情况下性能更好，如随机访问数组等 可以构建部分复杂数据结构，如图 重复利⽤空间（原地修改） 可变数据并不总是与引⽤透明性冲突 1. fn fib_mut(n: Int) -> Int { // 对于相同输⼊，总是有相同输出 2. let mut

Function）；相对的，函数对类型的每个值定 义了输出的，我们称为完全函数（Total Function） 为了避免程序运⾏时因不被允许的操作中⽌，也为了区分对应合理与不合理输⼊的输 出，我们使⽤ Option[T] 这⼀数据结构 8 Option的定义 Option[T] 分为两种情况： ⽆值： None 有值： Some(value: T) 例如，我们可以⽤ Option 定义⼀个整数除法的完全函数 1. = Nil 4. } 模式匹配并替换标识符 1. 1 + 1 + length(Nil) ... 1 + 1 + 0 2 29 结构化递归 对基于递归定义的数据结构 定义对基础数据结构的计算 定义对递归数据结构的计算 1. fn length(list: List[Int]) -> Int { 2. match list { 3. Nil => 0 fib(n) 的值 36 ⾃顶向下：以斐波那契数列为例 我们需要⼀个数据结构，平均存取速度应当与当前存储数据量⼤⼩⽆关 以求解斐波那契数列为例，我们假设的 IntMap 应有如下接⼝： 1. fn make(num: Int) -> IntMap // 创建数据结构 2. fn put(map: IntMap, num: Int, value:

现代编程思想 树 Hongbo Zhang 1 数据结构：树 树 ⼆叉树 ⼆叉搜索树 ⼆叉平衡树 2 ⽣活中的树状图 ⽣活中有很多的数据的结构与⼀颗树相似 谱系图（⼜称，家族树） ⽂件结构 数学表达式 …… 3 树的逻辑结构 数据结构中，树是由有限个节点构成的具有层次关系的集合 节点是存储数据的结构，节点之间存在亲⼦关系：⽗节点和⼦节点 如果树不为空，则它拥有⼀个根节点：根节点没有⽗节点 也有的定义将树的⾼度等同于最⼤层次，以根为第⼀层 6 树的存储结构 树的存储⽅式有多种（以⼆叉树为例，省略节点存储的数据） 节点与⼦节点关系的列表： [ (0, 1), (0, 2), (1, 3) ] 代数数据结构定义 1. Node(0, 2. Node(1, 3. Leaf(3), 4. Empty), 5. Leaf(2)) 列表定义 数据的逻辑结构独⽴于存储结构 KD-Tree：⽀持K-维度的数据（例如平⾯中的点、空间中的点等）的存储与查询的⼆ 叉树，每⼀层更换分叉判定的维度 B-Tree：适合顺序访问，利于硬盘存储数据 R-Tree：存储空间⼏何结构 …… 8 数据结构：⼆叉树 ⼆叉树要么是⼀棵空树，要么是⼀个节点；它最多具有两个⼦树：左⼦树与右⼦树 叶节点的两个⼦树都是空树 基于递归枚举类型的定义（本节课默认存储数据为整数） 1. enum IntTree

11. } 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]

现代编程思想 队列：可变数据结构实现 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. Some(node) => aux2(node.next, 1 + cumul) 6. } 7. } 8. aux2(self.head, 0) 9. } 18 总结 本章节我们介绍了使⽤可变数据结构定义队列 循环队列与单向链表的实现 尾调⽤与尾递归 19

不同的哈希映射为数组索引时可能相同 解决哈希表的冲突 直接寻址（分离链接）：同⼀索引下⽤另⼀数据结构存储 列表 ⼆叉平衡搜索树等 开放寻址 线性探查：当发现冲突后，索引递增，直到查找空位放⼊ ⼆次探查（索引递增 ）等 4 哈希表：直接寻址 当发⽣哈希/索引冲突时，将相同索引的数据装进⼀个数据结构中 例：添加0、5（哈希值分别为0、5）⾄⻓度为5的数组中时： 0 5 5 哈希表：直接寻址 添加/更新操作 添加时，根据键的哈希计算出应当存放的位置 遍历集合查找键 如果找到，修改值 否则，添加键值对 删除操作类同 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

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

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

但各个运行时的实现， 成熟度不一 • 使用扩展特性，基本 需要限定运行时 WASM 扩展特性 • 基本接口已在 WASM 1.0 标准化 • 但只能交换简单数据类型 • 交换缓冲区和高级数据结构的方法各有不一 WASM 外部语言接口（FFI） • WASI (WebAssembly System Interface) • 用于允许 WASM 代码调用操作系统的能力 （stdout、socket这些）

简单的接⼝可以⾃动⽣成，在定义最后声明 derive(<接⼝>) 即可 1. struct BoxedInt { value : Int } derive(Default, Eq, Compare, Debug) 需要数据结构内部的数据同样实现接⼝ 9 表：利⽤接⼝实现 ⼀个表是键值对的集合 对于每⼀个 键 存在⼀个对应 值 例： { 0 -> "a", 5 -> "Hello", 7 -> "a"} 1.