
<!-- path: example/index.md -->
# 示例

这里有一些使用 MoonBit 构建的示例。

# 目录：

* [数独求解器](sudoku/index.md)
  * [方格、单元和同级](sudoku/index.md#squares-units-and-peers)
  * [预处理网格](sudoku/index.md#preprocessing-the-grid)
  * [搜索](sudoku/index.md#search)
  * [总结](sudoku/index.md#conclusion)
* [Lambda 演算](lambda/index.md)
  * [无类型 lambda 演算的基本规则](lambda/index.md#basic-rules-of-untyped-lambda-calculus)
  * [自由变量与变量捕获](lambda/index.md#free-variables-and-variable-capture)
  * [德布朗指数](lambda/index.md#de-bruijn-index)
  * [在 `TermDBI` 上做规约](lambda/index.md#reduce-on-termdbi)
  * [改进](lambda/index.md#improvement)
* [G-Machine](gmachine/index.md)
  * [G-Machine 第一部分](gmachine/gmachine-1.md)
  * [G-Machine 第二部分](gmachine/gmachine-2.md)
  * [G-Machine 第三部分](gmachine/gmachine-3.md)
* [Myers Diff](myers-diff/index.md)
  * [Myers diff](myers-diff/myers-diff.md)
  * [Myers diff 2](myers-diff/myers-diff2.md)
  * [Myers diff 3](myers-diff/myers-diff3.md)
* [线段树](segment-tree/index.md)

<!-- path: example/sudoku/index.md -->
## 数独求解器

数独是一种基于逻辑的益智游戏，起源于 1979 年。它非常适合报纸等印刷媒体，即使在数字时代，许多数独游戏程序也可用于计算机和智能手机。尽管如今娱乐选择多种多样，但数独爱好者仍在继续组建活跃的社区（在线论坛，例如：[enjoysudoku](http://forum.enjoysudoku.com/)）。本文将演示如何使用 MoonBit 编写合适的程序来解决数独问题。

### 方格、单元和同级

最常见的数独形式是在 9x9 网格上进行的。我们将从上到下的行标记为 A-I，从左到右的列标记为 1-9。这为网格中的每个方格提供了一个坐标，例如，下面网格中包含数字 0 的方格的坐标为 C3。

```default
  1 2 3 4 5 6 7 8 9
A . . . . . . . . .
B . . . . . . . . .
C . . 0 . . . . . .
D . . . . . . . . .
E . . . . . . . . .
F . . . . . . . . .
G . . . . . . . . .
H . . . . . . . . .
I . . . . . . . . .
```

这个 9x9 的网格共有 9 个单元，每个单元包含的方格必须具有从 1 到 9 的唯一数字。但是在游戏的初始状态下，大多数方格不包含任何数字。

```default
 4  1  7 | 3  6  9 | 8  2  5
 6  3  2 | 1  5  8 | 9  4  7
 9  5  8 | 7  2  4 | 3  1  6
---------+---------+---------
 8  2  5 | 4  3  7 | 1  6  9
 7  9  1 | 5  8  6 | 4  3  2
 3  4  6 | 9  1  2 | 7  5  8
---------+---------+---------
 2  8  9 | 6  4  3 | 5  7  1
 5  7  3 | 2  9  1 | 6  8  4
 1  6  4 | 8  7  5 | 2  9  3
```

除了单元之外，另一个重要概念是同级。一个方格的同级包括同一行、同一列和同一单位的其他方格。例如，C2 的同级包括以下方格：

```default
    A2   |         |
    B2   |         |
    C2   |         |
---------+---------+---------
    D2   |         |
    E2   |         |
    F2   |         |
---------+---------+---------
    G2   |         |
    H2   |         |
    I2   |         |

         |         |
         |         |
 C1 C2 C3| C4 C5 C6| C7 C8 C9
---------+---------+---------
         |         |
         |         |
         |         |
---------+---------+---------
         |         |
         |         |
         |         |

 A1 A2 A3|         |
 B1 B2 B3|         |
 C1 C2 C3|         |
---------+---------+---------
         |         |
         |         |
         |         |
---------+---------+---------
         |         |
         |         |
         |         |
```

没有两个同级的格子可以包含相同的数字。

我们需要一个数据类型 Grid[T] 来存储这 81 个方格以及与每个方格相关的信息。这可以使用哈希表来实现，但使用数组会更紧凑、更简单。首先，我们编写一个函数将坐标 A1-I9 转换为索引 0-80：

```moonbit
// A1 => 0, A2 => 1
fn square_to_int(s : String) -> Int {
  if s is [('A'..='I') as a, ('1'..='9') as b, ..] {
    let row = a.to_int() - 'A'.to_int() // 'A' <=> 0
    let col = b.to_int() - '1'.to_int() // '1' <=> 0
    return row * 9 + col
  } else {
    abort("Grid_to_int(): \{s} is not a Grid")
  }
}

///
test {
  inspect(square_to_int("A1"), content="0")
  inspect(square_to_int("A7"), content="6")
  inspect(square_to_int("I9"), content="80")
}
```

然后我们包装这个数组，并提供创建、访问、为特定坐标赋值以及复制 Grid[T] 的操作。通过重载 op_get 和 op_set 方法，我们可以编写类似 `table["A2"]` 和 `table["C3"] = ...` 的便捷代码。

```moonbit
///|
struct Grid[T](FixedArray[T])

///|
fn[T] Grid::new(val : T) -> Grid[T] {
  FixedArray::make(81, val)
}

///|
fn[T] Grid::copy(self : Grid[T]) -> Grid[T] {
  if self.0.length() == 0 {
    return []
  }
  let arr = FixedArray::make(81, self.0[0])
  let mut i = 0
  while i < 81 {
    arr[i] = self.0[i]
    i = i + 1
  }
  return arr
}

///|
##alias("_[_]")
fn[T] Grid::at(self : Grid[T], square : String) -> T {
  let i = square_to_int(square)
  self.0[i]
}

///|
##alias("_[_]=_")
fn[T] Grid::set(self : Grid[T], square : String, x : T) -> Unit {
  let i = square_to_int(square)
  self.0[i] = x
}
```

接下来我们准备一些常量：

```moonbit
let rows = "ABCDEFGHI"

let cols = "123456789"

type Squares =  @immut/sorted_set.SortedSet[String] 

// squares contains the coordinates of each square
let squares : Squares = ......

// units[coord] contains the other squares in the unit of the square at coord
// for example：units["A3"] => [C3, C2, C1, B3, B2, B1, A2, A1]
let units : Grid[Squares] = ......

// peers[coord] contains all the peers of the square at coord
// for example：peers["A3"] => [A1, A2, A4, A5, A6, A7, A8, A9, B1, B2, B3, C1, C2, C3, D3, E3, F3, G3, H3, I3]
let peers : Grid[Squares] = ......
```

构建单元和同级表的过程非常繁琐，因此这里不再详述。

### 预处理网格

我们使用字符串来表示初始数独网格。各种格式均可接受；. 和 0 均表示空方块，其他字符（如空格和换行符）将被忽略。

```default
##|400000805
##|030000000
##|000700000
##|020000060
##|000080400
##|000010000
##|000603070
##|500200000
##|104000000

##|4 . .   . . .   8 . 5
##|. 3 .   . . .   . . .
##|. . .   7 . .   . . .
##|
##|. 2 .   . . .   . 6 .
##|. . .   . 8 .   4 . .
##|. . .   . 1 .   . . .
##|
##|. . .   6 . 3   . 7 .
##|5 . .   2 . .   . . .
##|1 . 4   . . .   . . .
```

暂时先不考虑太多游戏规则，如果只考虑每个方格能填入的数字，那么 1-9 都是有可能的，因此我们初始将所有方格的内容设置为`['1', '2', '3', '4', '5', '6', '7', '8', '9']` (a List)。

```moonbit
fn Grid::parse(s : String) -> Grid[@immut/sorted_set.T[Char]] {
  let digits = @immut/sorted_set.from_array(cols.to_array())
  let values = Grid::new(digits)
  ...
}
```

接下来，我们需要将输入中已知数字的方块赋值。这个过程可以用函数 `assign(values, key, val)` 来实现，其中 `key` 是一个字符串，比如 `A6`，`val` 是一个字符。这样的代码写起来很容易。

```moonbit
fn assign(values : Grid[@immut/sorted_set.T[Char]], key : String, val : Char) -> Unit {
  values[key] = @immut/sorted_set.singleton(val)
}
```

这个实现简单而精确，但我们可以做得更多。

现在，我们可以重新引入之前搁置的规则。但是，规则本身并没有告诉我们该做什么。我们需要启发式策略来从规则中获得见解，类似于用笔和纸解决数独。让我们从消除法开始：

- **策略 1**：如果为一个方块 `key` 分配了一个值 `val`，则其对同级（'peers[key]'）的可能值列表中不应该包含 \`val'，因为这会违反同一单元、行或列中没有两个方块可以具有相同数字的规则。
- **策略 2**：如果一个单元中只有一个方格可以容纳特定的数字（在多次应用上述规则后可能发生），则应将该数字分配给该方格。

我们通过定义一个消除函数 `eliminate` 来调整代码，该函数从正方形的可能值中删除一个数字。执行消除任务后，它将上述策略应用于 `key` 和 `val` 以尝试进一步消除。请注意，它包含一个布尔返回值来处理可能的矛盾。如果方格的可能值列表为空，则出现问题，我们返回 `false`。

```moonbit
fn eliminate(
  values : Grid[@sorted_set.SortedSet[Char]],
  key : String,
  val : Char
) -> Bool {
  if !(values[key].contains(val)) {
    return true
  }
  values[key] = values[key].remove(val)
  // If `key` has only one possible value left, remove this value from its peers
  match values[key].length() {
    1 => {
      let val = values[key].min()
      let mut res = true
      for key in peers[key] {
        res = res && eliminate(values, key, val)
      }
      if !res {
        return res
      }
    }
    0 => return false
    _ => ()
  }
  //  If there is only one square in the unit of `key` that can hold `val`, assign `val` to that square
  let unit = units[key]
  let places = unit.filter(fn(sq) { values[sq].contains(val) })
  match places.length() {
    1 => {
      let key = places.min()
      return assign(values, key, val)
    }
    0 => return false
    _ => return true
  }
}
```

接下来，我们定义 `assign(values, key, val)` 来从 `key` 的可能值中删除除 `val` 之外的所有值。

```moonbit
///|
fn assign(
  values : Grid[@sorted_set.SortedSet[Char]],
  key : String,
  val : Char
) -> Bool {
  let other_values = values[key].remove(val)
  let mut result = true
  for val in other_values {
    result = result && eliminate(values, key, val)
  }
  return result
}
```

这两个函数将启发式策略应用于它们访问的每个方格。成功的启发式应用会引入新的方格供考虑，从而使这些策略在整个网格中广泛传播。这是快速消除无效选项的关键。事实上，这种预处理已经可以解决一些简单的数独难题。

```moonbit
let grid2 =
  #|0 0 3   0 2 0   6 0 0
  #|9 0 0   3 0 5   0 0 1
  #|0 0 1   8 0 6   4 0 0
  #|
  #|0 0 8   1 0 2   9 0 0
  #|7 0 0   0 0 0   0 0 8
  #|0 0 6   7 0 8   2 0 0
  #|
  #|0 0 2   6 0 9   5 0 0
  #|8 0 0   2 0 3   0 0 9
  #|0 0 5   0 1 0   3 0 0

test {
  inspect(
    Grid::parse(grid2).format(),
    content=(
      #| 4  8  3 | 9  2  1 | 6  5  7
      #| 9  6  7 | 3  4  5 | 8  2  1
      #| 2  5  1 | 8  7  6 | 4  9  3
      #|---------+---------+---------
      #| 5  4  8 | 1  3  2 | 9  7  6
      #| 7  2  9 | 5  6  4 | 1  3  8
      #| 1  3  6 | 7  9  8 | 2  4  5
      #|---------+---------+---------
      #| 3  7  2 | 6  8  9 | 5  1  4
      #| 8  1  4 | 2  5  3 | 7  6  9
      #| 6  9  5 | 4  1  7 | 3  8  2
      #|
    ),
  )
}
```

如果您对人工智能感兴趣，您可能会将其视为约束满足问题 (CSP)，而'分配'和'消除'是专门的弧一致性算法。有关此主题的更多信息，请参阅 Artificial Intelligence: A Modern Approach 第 6 章

### 搜索

经过预处理后，我们可以大胆地使用蛮力枚举来搜索所有可行的组合。但是，在搜索过程中，我们仍然可以使用启发式策略。当尝试为某个方块赋值时，我们仍然使用 `assign`，这使我们能够应用先前的优化来消除搜索过程中的许多无效分支。

另外需要注意的是，搜索过程中可能会发生冲突（当一个方格的可能值耗尽时）。由于可变结构使回溯变得麻烦，因此我们每次分配值时都直接复制值。

```moonbit
fn search(
  values : Grid[@sorted_set.SortedSet[Char]],
) -> Grid[@sorted_set.SortedSet[Char]]? {
  if values.contains(fn(digits) { !(digits.length() == 1) }) {
    let mut minsq = ""
    let mut n = 10
    for sq in squares {
      let len = values[sq].length()
      if len > 1 {
        if len < n {
          n = len
          minsq = sq
        }
      }
    }
    for digit in values[minsq] {
      let another = values.copy()
      if assign(another, minsq, digit) {
        let temp = search(another)
        match temp {
          None => continue
          Some(v) => return Some(v)
        }
      }
    } nobreak {
      return None
    }
  } else {
    return Some(values)
  }
}

fn solve(g : String) -> String {
  match search(Grid::parse(g)) {
    None => "can't solve \{g}"
    Some(v) => v.format()
  }
}
```

我们运行一个来自 [magictour](http://magictour.free.fr/top95) （一个困难数独谜题列表，对人类来说并不容易）的例子

```moonbit
let grid1 =
  #|4 . .   . . .   8 . 5
  #|. 3 .   . . .   . . .
  #|. . .   7 . .   . . .
  #|
  #|. 2 .   . . .   . 6 .
  #|. . .   . 8 .   4 . .
  #|. . .   . 1 .   . . .
  #|
  #|. . .   6 . 3   . 7 .
  #|5 . .   2 . .   . . .
  #|1 . 4   . . .   . . .

test {
  inspect(
    solve(grid1),
    content=(
      #| 4  1  7 | 3  6  9 | 8  2  5
      #| 6  3  2 | 1  5  8 | 9  4  7
      #| 9  5  8 | 7  2  4 | 3  1  6
      #|---------+---------+---------
      #| 8  2  5 | 4  3  7 | 1  6  9
      #| 7  9  1 | 5  8  6 | 4  3  2
      #| 3  4  6 | 9  1  2 | 7  5  8
      #|---------+---------+---------
      #| 2  8  9 | 6  4  3 | 5  7  1
      #| 5  7  3 | 2  9  1 | 6  8  4
      #| 1  6  4 | 8  7  5 | 2  9  3
      #|
    ),
  )
}
```

在普通开发机器上，求解这个数独只需要约 0.11 秒。

### 总结

游戏的目的是为了缓解无聊并带来快乐。如果玩游戏让人感到焦虑而不是兴奋，那么它可能违背了游戏设计师的初衷。本文表明，简单的消除法和强力搜索可以快速解决一些数独难题。这并不意味着数独不值得玩；相反，它表明人们不应该过分担心无法解决的数独难题。

让我们轻松玩转 MoonBit 吧！

本教程参考了 Norvig 的博客：[http://norvig.com/sudoku.html](http://norvig.com/sudoku.html)

<!-- path: example/lambda/index.md -->
## Lambda 演算

相信点开这篇文章的您或多或少地听说过函数式编程这个名词。在摩尔定律失效的今天，对多核处理器的充分利用成为了一种越发重要的程序优化方法，而函数式编程也因为其并行运算亲和的特点在大众视野中越发频繁地出现。究其原因，离不开它从其理论上的祖先之一 - lambda 演算那里所继承的特征。

而 lambda 演算这一起源于 20 世纪 30 年代，出自图灵导师阿隆佐·邱奇之手的形式系统如今已经发展成了蔚为大观的一个大家族，本文将展示其中最基础的一种：无类型 lambda 演算 (这也是最早阿隆佐·邱奇提出的那种)

### 无类型 lambda 演算的基本规则

无类型 lambda 演算中能做的事情只有定义 lambda (经常称为 Abstraction) 和调用 lambda (经常称为 Application)，它们也是 lambda 演算中的基础表达式。

由于函数式编程范式对主流编程语言的影响，大多数程序员对 lambda 表达式这个名字已经不会感到陌生了，不过，无类型 lambda 演算中的 lambda 要比主流编程语言简单一些。一个 lambda 通常看起来就像这样：`λx.x x`, 其中 x 是它的参数 (每个 lambda 只能有一个参数)，`.`是分隔参数与表达式具体定义的分隔符，后面的`x x`便是它的定义了。

##### NOTE
也有些材料的记法不写空格，上面的例子要改写成 `λx.xx`

上面的 `x x` 如果换成 `x(x)`, 可能更符合我们在一般语言中见到的函数调用。但在 lambda 演算较常见的写法中，调用一个 lambda 只需要在它和它的参数中间写个空格。此处我们调用 `x` 所给出的参数就是 `x` 自己。

以上两种表达式和定义 lambda 时引入的变量加在一起合称 lambda 项，我们在 MoonBit 里用一个 enum 类型来表示它：

```moonbit
enum Term {
  Var(String) // 变量
  Abs(String, Term) // 定义 lambda，变量用字符串表示
  App(Term, Term) // 调用 lambda
}

```

我们在日常编程中所接触的概念诸如布尔值，if 表达式，自然数算术乃至递归都可以通过 lambda 表达式实现，但这并非本文内容的重心所在。

##### SEE ALSO
有兴趣的读者可以参阅 [Programming with Nothing](https://tomstu.art/programming-with-nothing) 这篇博客。

要实现一个无类型 lambda 演算的解释器，我们所需要了解的基本就只有两条规则：Alpha 转换与 Beta 规约。

Alpha 转换所描述的事实是，lambda 的结构是重点，变量名叫什么没那么重要。`λx.x` 和 `λfoo.foo` 可以互相替换。对于某些有重复变量名的嵌套 lambda 例如 `λx.(λx.x) x`，重命名时不能把内层的变量也重命名了，例如上面的例子可以通过 Alpha 转换写成 `λy.(λx.x) y`。

Beta 规约则专注于处理 lambda 的调用，还是举一个例子：

```default
(λx.(λy.x)) (λs.(λz.z))
```

在无类型 lambda 演算中，调用 lambda 之后所需要作的事情仅仅是对参数进行替换 (substitution)，上面这个例子里就需要把变量 `x` 替换成 `(λs.(λz.z))`，得到的结果是

```default
(λy.(λs.(λz.z)))
```

### 自由变量与变量捕获

一个 lambda 项中的变量如果在它所处的上下文中没有定义，那么我们叫它自由变量。例如 `(λx.(λy.fgv h))` 这个 lambda 项中变量 `fgv` 和 `h` 就没有对应的 lambda 定义。

在进行 Beta 规约时，如果用于替换变量的那个 lambda 项中含有自由变量，可能会导致一种被称为“变量捕获”的行为

```default
(λx.(λy.x)) (λz.y)
```

上面这个表达式在替换后会变成

```default
λy.λz.y
```

`λz.y` 中的自由变量被当成了某个 lambda 的参数，这显然不是我们想要的。

变量捕获问题在编写解释器时的常见解决方案是在替换前遍历表达式得到一个自由变量的集合，做替换时遇到内层 lambda 就判断一下变量名在不在这个自由变量集合里面

<!-- Pseudo code. MANUAL CHECK -->
```moonbit
// (λx.E) T => E.subst(x, T)
fn subst(self : Term, var : String, term : Term) -> Term {
  let freeVars : Set[String] = term.get_free_vars()
  match self {
    Abs(variable, body) => {
      if freeVars.contains(variable) {
        //自由变量集合中有当前这个内层 lambda 的参数名，即会发生变量捕获
        abort("subst(): error while encountering \{variable}")
      } else {
        ...
      }
    }
    ...
  }
}

```

此处我们介绍一种较少见但具有一定便利性的方法：德布朗指数（de Bruijn index）。

### 德布朗指数

德布朗指数是一种用整数表示 lambda 项中变量的技术，具体地说，它用变量所在位置和原先引入它的位置中间有几层 lambda 来替换特定变量。

```default
λx.(λy.x (λz.z z))

λ.(λ.1 (λ.0 0))
```

上面的例子中，变量 `x` 和引入它的地方 `λx` 中间有一个 `λy`, 于是将 `x` 替换为 `1`，而 `z` 和定义它的位置中间没有夹杂其他的 lambda，于是直接用 `0` 替换。某种程度上说，德布朗指数的值描述的是变量与对应 lambda 的相对距离，此处的距离衡量标注就是中间嵌套的 lambda 层数。

##### NOTE
同一个变量在不同的地方可能会用不同的整数来替换。

我们定义一个新类型 `TermDBI` 来表示使用德布朗指数的 lambda 项：

```moonbit
enum TermDBI {
  Var(String, Int)
  Abs(String, TermDBI)
  App(TermDBI, TermDBI)
}
```

不过直接编写以及阅读德布朗指数形式的 lambda 很痛苦，所以我们需要编写一个将 `Term` 转换成 `TermDBI` 的函数 `debruijn()` - 这也是 `TermDBI` 类型定义中仍有 `String` 的原因，保留原变量名可用于它的 `Show` 的实现，这样就可以方便地用 `println` 打印求值结果查看了。

```moonbit
impl Show for TermDBI with output(self, logger) -> Unit {
  match self {
    Var(name, _) => logger.write_string(name)
    Abs(name, body) => logger.write_string("(\\\{name}.\{body})")
    App(t1, t2) => logger.write_string("\{t1} \{t2}")
  }
}
```

为了简化实现，如果输入的 Term 中含有自由变量，`debruijn()` 函数会直接报错。MoonBit 中一般用 `Result[V, E]` 类型表示可能会出错的计算，它有 `Ok(V)` 和 `Err(E)` 两个值构造子，分别代表计算成功与失败。

<!-- MANUAL CHECK -->
```moonbit
fn bruijn(self : Term) -> Result[TermDBI, String]
```

我们采取一种笨办法来保存变量名与相关联的嵌套深度，首先定义 `Index` 类型

```moonbit
struct Index {
  name : String
  depth : Int
}
```

然后写一个从 `@list.T[Index]` 中根据特定 `name` 查找对应 `depth` 的辅助函数

```moonbit
// Find the depth corresponding to the first varname in the environment
fn find(map : @list.List[Index], varname : String) -> Result[Int, String] {
  match map {
    Empty => Err(varname)
    More(i, tail=rest) =>
      if i.name == varname {
        Ok(i.depth)
      } else {
        find(rest, varname)
      }
  }
}

```

现在可以补全 `debruijn()` 函数了。

- `Var` 的处理最简单，只需要查表寻找对应 `depth` 即可。
- `Abs` 稍微复杂一点，首先对列表中所有 `index` 的 `depth` 加一 (因为 lambda 嵌套加深了一层)，然后在列表的开头加上 `{ name : varname, depth : 0 }`。
- `App` 在两个子项都能转换时成功，否则返回一个 `Err`

```moonbit
fn go(m : @list.List[Index], term : Term) -> Result[TermDBI, String] {
  match term {
    Var(name) => {
      let idx = find(m, name)
      match idx {
        Err(name) => Err(name)
        Ok(idx) => Ok(Var(name, idx))
      }
    }
    Abs(varname, body) => {
      let m = m
        .map(fn(index) { { name: index.name, depth: index.depth + 1 } })
        .add({ name: varname, depth: 0 })
      let res = go(m, body)
      match res {
        Err(name) => Err(name)
        Ok(term) => Ok(Abs(varname, term))
      }
    }
    App(e1, e2) =>
      match (go(m, e1), go(m, e2)) {
        (Ok(e1), Ok(e2)) => Ok(App(e1, e2))
        (Err(name), _) => Err(name)
        (_, Err(name)) => Err(name)
      }
  }
}

go(@list.empty(), self)
```

### 在 `TermDBI` 上做规约

规约主要处理的是 `App`，即调用：

```moonbit
fn TermDBI::eval(self : TermDBI) -> TermDBI {
  match self {
    App(t1, t2) =>
      match (t1.eval(), t2.eval()) {
        (Abs(_, t1), t2) => subst(t1, t2).eval()
        (t1, t2) => App(t1, t2)
      }
    Abs(_) => self
    // Eval should not encounter any free variables
    _ => panic()
  }
}

```

首先对两个子项尝试规约，然后看 `eval(t1)` 得到的是否是一个 lambda，如果是，就执行一步变量替换 (通过 `subst` 函数) 然后继续化简。对于 lambda (即 `Abs`), 直接原样返回即可。

`subst` 函数的实现在不用考虑自由变量的情况下简单了许多，只要记录递归到当前位置的深度并且与遇到的变量进行比对，大小相等就是需要替换的目标变量。

```moonbit
fn subst(t1 : TermDBI, t2 : TermDBI) -> TermDBI {
  fn go(t1 : TermDBI, t2 : TermDBI, depth : Int) -> TermDBI {
    match t1 {
      Var(_, d) => if d == depth { t2 } else { t1 }
      Abs(name, t) => Abs(name, go(t, t2, depth + 1))
      App(tl, tr) => App(go(tl, t2, depth), go(tr, t2, depth))
    }
  }

  go(t1, t2, 0)
}

```

完整代码在 [这里](/sources/lambda-expression/src/top.mbt)

### 改进

笔者在保存变量名到索引的对应关系时使用了 `@list.T[Index]` 类型，并且在每增加一层 lambda 时更新整个列表，但是这其实是个很笨的办法。相信聪明且注意力集中的读者很快就能发现，其实只需要保存一个 `@list.T[String]` 就够了，有兴趣的读者可以自己试着做一做。

<!-- path: example/gmachine/index.md -->
## G-Machine

惰性求值是编程语言领域的一个基本概念。Haskell 作为一种纯粹的函数式编程语言而闻名，它拥有健壮的惰性求值机制。这种机制不仅使开发人员能够编写更高效、更简洁的代码，而且还增强了程序的性能和响应能力，特别是在处理大型数据集或复杂的数据流时。

在本文中，我们将深入研究惰性求值机制，全面研究其原理和实现方法，然后探索如何在 [MoonBit](https://www.moonbitlang.com/) 中实现 Haskell 的求值语义。

## 目录：

* [G-Machine 第一部分](gmachine-1.md)
  * [高阶函数和性能挑战](gmachine-1.md#higher-order-functions-and-performance-challenges)
  * [惰性列表实现](gmachine-1.md#lazy-list-implementation)
  * [一种惰性求值语言及其抽象语法树](gmachine-1.md#a-lazy-evaluation-language-and-its-abstract-syntax-tree)
  * [为什么是图](gmachine-1.md#why-graph)
  * [约定](gmachine-1.md#conventions)
  * [G-Machine 概述](gmachine-1.md#g-machine-overview)
  * [G-Machine 状态解析](gmachine-1.md#dissecting-the-g-machine-state)
  * [每条指令的作用](gmachine-1.md#corresponding-effect-of-each-instruction)
  * [将超组合子编译成指令序列](gmachine-1.md#compiling-super-combinators-into-instruction-sequences)
  * [运行 G-Machine](gmachine-1.md#running-the-g-machine)
  * [总结](gmachine-1.md#conclusion)
  * [参考](gmachine-1.md#reference)
* [G-Machine 第二部分](gmachine-2.md)
  * [let 表达式](gmachine-2.md#let-expressions)
  * [添加原语](gmachine-2.md#adding-primitives)
  * [总结](gmachine-2.md#conclusion)
* [G-Machine 第三部分](gmachine-3.md)
  * [追踪上下文](gmachine-3.md#tracking-context)
  * [自定义数据结构](gmachine-3.md#custom-data-structures)
  * [结语](gmachine-3.md#epilogue)

<!-- path: example/myers-diff/index.md -->
## Myers Diff

## 目录：

* [Myers diff](myers-diff.md)
  * [“差异”的定义及其度量标准](myers-diff.md#defining-difference-and-its-measurement-criteria)
  * [算法概述](myers-diff.md#algorithm-overview)
  * [实现](myers-diff.md#implementation)
  * [结语](myers-diff.md#epilogue)
* [Myers diff 2](myers-diff2.md)
  * [记录搜索过程](myers-diff2.md#recording-the-search-process)
  * [回溯编辑路径](myers-diff2.md#backtracking-the-edit-path)
  * [打印 diff](myers-diff2.md#printing-the-diff)
  * [总结](myers-diff2.md#conclusion)
* [Myers diff 3](myers-diff3.md)
  * [分而治之](myers-diff3.md#divide-and-conquer)
  * [总结](myers-diff3.md#conclusion)

<!-- path: example/segment-tree/index.md -->
## 线段树

线段树是一种常见的数据结构，用于一些线性区间的修改、查询问题，比如对于以下问题：

- 给出一个长度已知的、有初值的数字数组，接下来要进行许多区间加法操作（将一个区间的数值加到所有元素上）和区间求和操作（计算一个区间的元素和）。

如果该问题使用正常的数组方式来遍历求解，假设该数组长度为 N，每次修改和查询的操作耗时是 O(N) 的；但线段树经过 O(N log N) 的构建之后，可以对上述两个操作做到 O(log N) 的优秀复杂度，足以体现其在区间问题上的重要性。

当然上面的例子只是线段树可以解决的一个简单问题，它可以做到的更复杂、更有趣的事情还有很多。在接下来的几篇文章当中我们将会学习使用线段树的概念以及如何使用 MoonBit 实现它，最终我们将一步步实现一棵支持区间加法与乘法、并可以查询区间和、拥有不可变特性的线段树。

本节我们将学习线段树的基本原理以及如何使用 MoonBit 编写一棵最基本的支持单点修改、查询的线段树。