7 变量 在⽉兔中，我们可以在代码块中⽤ let mut 定义临时变量 1. let mut x = 1 2. x = 10 // 赋值操作是⼀个命令 在⽉兔中，结构体的字段默认不可变，我们也允许可变的字段，需要⽤ mut 标识 1. struct Ref[T] { mut val : T } 2. 3. fn init { 4. let ref: Ref[Int] = { val: 本身只是⼀个数据绑定 5. ref.val = 10 // 我们可以修改结构体的字段 6. 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 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.

现代编程思想 队列：可变数据结构实现 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

Function）；相对的，函数对类型的每个值定 义了输出的，我们称为完全函数（Total Function） 为了避免程序运⾏时因不被允许的操作中⽌，也为了区分对应合理与不合理输⼊的输 出，我们使⽤ Option[T] 这⼀数据结构 8 Option的定义 Option[T] 分为两种情况： ⽆值： None 有值： Some(value: T) 例如，我们可以⽤ Option 定义⼀个整数除法的完全函数 1. 数据的数量是不定的 举例来说 ⼀句话中的⽂字：� '⼀' '句' '话' '中' '的' '⽂' '字' � DNA序列：� G A T T A C A � …… 13 列表的接⼝ 我们定义⼀个单向不可变列表 以整数的列表为例（暂名之 IntList ），它应当定义如下操作： 构造 nil : () -> IntList 返回⼀个空列表 = 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

测试驱动开发与设计 概念基础 常⻅数据结构与算法 多种编程范式 关注模块化和组合性 3 课程⼯具 MoonBit⽉兔 现代静态类型多范式编程语⾔ 语法轻量，易上⼿ 浏览器开发环境、云原⽣开发环境或本地集成开发环境 4 课程概览 课程 主题 课程 主题 课程介绍与程序设计 接⼜：集合与表 ⾯向值编程 结构体 命令 函数 列表与递归 可变状态 与可变数据结构 列表 元组 嵌套模式 抽象堆栈结构机器 抽象堆栈结构机器 数据类型与树 可变队列 树与⼆分查找 迭代与尾递归 ⼆叉搜索树的插⼊与删除 闭包与对象 泛型与⾼阶函数 案例：句法分析器与程序解释器 ⾼阶函数： 与 案例：⾃动积分与⼩游戏 所有课程资料均在互联⽹上公开 课程论坛：taolun.moonbitlang.cn 5 程序设计 6 基础设计流程 设计是将⾮正式的规范转化为可运⾏代码的过程 推荐采⽤由测试驱动的开发流程

现代编程思想 树 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]

不同的哈希映射为数组索引时可能相同 解决哈希表的冲突 直接寻址（分离链接）：同⼀索引下⽤另⼀数据结构存储 列表 ⼆叉平衡搜索树等 开放寻址 线性探查：当发现冲突后，索引递增，直到查找空位放⼊ ⼆次探查（索引递增 ）等 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

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.