# Examples Here are some examples built with MoonBit. # Contents: * [数独ソルバー](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 calculus](lambda/index.md) * [Basic rules of untyped Lambda calculus](lambda/index.md#basic-rules-of-untyped-lambda-calculus) * [Free Variables and Variable Capture](lambda/index.md#free-variables-and-variable-capture) * [De Bruijn Index](lambda/index.md#de-bruijn-index) * [Reduce on TermDBI](lambda/index.md#reduce-on-termdbi) * [Improvement](lambda/index.md#improvement) * [G-Machine](gmachine/index.md) * [G-Machine 1](gmachine/gmachine-1.md) * [G-Machine 2](gmachine/gmachine-2.md) * [G-Machine 3](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](segment-tree/index.md) ## 数独ソルバー 数独は、1979 年に生まれた論理パズルゲームです。新聞のような印刷媒体と相性がよく、デジタル時代の今でも、コンピュータやスマートフォン向けに多くの数独プログラムがあります。今日では娯楽の選択肢が多様になっていますが、数独愛好家は今なお活発なオンラインコミュニティを形成しています。この記事では、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| | ---------+---------+--------- | | | | | | ---------+---------+--------- | | | | | | ``` ピア同士の 2 つのマスに同じ数字を入れることはできません。 81 個のマスと各マスに関連する情報を保存するために、`Grid[T]` というデータ型が必要です。これはハッシュテーブルでも実装できますが、配列を使う方がコンパクトで単純です。まず、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] = ...... ``` units と peers の表を構築する処理は煩雑なので、ここでは詳しく扱いません。 ### 盤面の前処理 初期の数独盤面は文字列で表します。形式はさまざまでも構いません。`.` と `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']`（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 つのマスに同じ数字は入れられないからです。 - **戦略 2**: あるユニットの中で、特定の数字を入れられるマスが 1 つしかない場合（これは上の規則を何度か適用した後に起こりえます）、その数字はそのマスに割り当てるべきです。 コードを調整するために、あるマスの候補値から数字を取り除く `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 } ``` この 2 つの関数は、アクセスする各マスに対してヒューリスティック戦略を適用します。戦略がうまく働くと、新たに検討すべきマスが生まれ、それによって戦略が盤面全体へ広く伝播していきます。これが無効な候補を素早く取り除く鍵です。実際、この前処理だけで解ける簡単な数独もあります。 ```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）であり、`assign` と `eliminate` が特化したアーク整合性アルゴリズムであることに気づくかもしれません。この話題について詳しくは、*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 を楽しみましょう！ このチュートリアルは Peter Norvig の数独解法の記事を参考にしています。 ## Lambda calculus Functional programming rises with the fall of Moore's Law. The full utilization of multi-core processors has become an increasingly important optimization method, while functional programming also becomes more popularized with its affinity for parallel computation. The reasons behind this trend can be traced back to one of its theoretical ancestors—Lambda calculus. Lambda calculus originated from the 1930s. Created by Turing's mentor Alonzo Church, formal systems have now evolved a vast and flourishing family tree. This article will illustrate one of its most fundamental forms: untyped Lambda calculus (which was also one of the earliest forms proposed by Alonzo Church). ### Basic rules of untyped Lambda calculus The only actions allowed in untyped Lambda calculus are defining Lambdas (often referred to as Abstraction) and calling Lambdas (often referred to as Application). These actions constitute the basic expressions in Lambda calculus. Most programmers are no strange to the name "Lambda expression" as most mainstream programming languages are hugely influenced by functional language paradigm. Lambdas in untyped Lambda calculus are simpler than those in mainstream programming languages. A Lambda typically looks like this: `λx.x x`, where `x` is its parameter (each Lambda can only have one parameter), `.` is the separator between the parameter and the expression defining it, and `x x` is its definition. ##### NOTE Some materials may omit spaces, so the above example can be rewritten as `λx.xx`. If we replace `x x` with `x(x)`, it might be more in line with the function calls we see in general languages. However, in the more common notation of Lambda calculus, calling a Lambda only requires a space between it and its parameter. Here, we call the parameter given by `x`, which is `x` itself. The combination of the above two expressions and the variables introduced when defining Lambdas are collectively referred to as the Lambda term. In MoonBit, we use an enum type to represent it: ```moonbit enum Term { Var(String) // Variable Abs(String, Term) // Define lambda, variables represented by strings App(Term, Term) // Call lambda } ``` Concepts encountered in daily programming such as boolean values, if expressions, natural number arithmetic, and even recursion can all be implemented using Lambda expressions. However, this is not the focus of this article. ##### SEE ALSO Interested readers can refer to: [Programming with Nothing](https://tomstu.art/programming-with-nothing) To implement an interpreter for untyped Lambda calculus, the basic things we need to understand are just two rules: Alpha conversion and Beta reduction. **Alpha conversion** describes the fact that the structure of Lambda is crucial, and the names of variables are not that important. `λx.x` and `λfoo.foo` can be interchanged. For certain nested Lambdas with repeated variable names, such as `λx.(λx.x) x`, when renaming, the inner variables cannot be renamed. For example, the above example can be rewritten using Alpha conversion as `λy.(λx.x) y`. **Beta reduction** focuses on handling Lambda calls. Let's take an example: ```default (λx.(λy.x)) (λs.(λz.z)) ``` In untyped Lambda calculus, all that needs to be done after calling a Lambda is to substitute the parameter. In the example above, we need to replace the variable `x` with `(λs.(λz.z))`, resulting in: ```default (λy.(λs.(λz.z))) ``` ### Free Variables and Variable Capture If a variable in a Lambda term is not defined in its context, we call it a free variable. For example, in the Lambda term `(λx.(λy.fgv h))`, the variables `fgv` and `h` do not have corresponding Lambda definitions. During Beta reduction, if the Lambda term used for variable substitution contains free variables, it may lead to a behavior called "variable capture": ```default (λx.(λy.x)) (λz.y) ``` After substitution: ```default λy.λz.y ``` The free variable in `λz.y` is treated as a parameter of some Lambda, which is obviously not what we want. A common solution to the variable capture problem when writing interpreters is to traverse the expression before substitution to obtain a set of free variables. When encountering an inner Lambda during substitution, check if the variable name is in this set of free variables: ```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) { // The variable name is in the set of free variables // of the current inner Lambda, indicating variable capture abort("subst(): error while encountering \{variable}") } else { ... } } ... } } ``` Next, I'll introduce a less popular but somewhat convenient method: de Bruijn index. ### De Bruijn Index De Bruijn index is a technique for representing variables in Lambda terms using integers. Specifically, it replaces specific variables with Lambdas between the variable and its original imported position. ```default λx.(λy.x (λz.z z)) λ.(λ.1 (λ.0 0)) ``` In the example above, there is one Lambda `λy` between the variable `x` and its introduction position `λx`, so `x` is replaced with `1`. For variable `z`, there are no other Lambdas between its introduction position and its usage, so it is directly replaced with `0`. In a sense, the value of the de Bruijn index describes the relative distance between the variable and its corresponding Lambda. Here, the distance is measured by the number of nested Lambdas. ##### NOTE The same variable may be replaced with different integers in different positions. We define a new type `TermDBI` to represent Lambda terms using de Bruijn indices: ```moonbit enum TermDBI { Var(String, Int) Abs(String, TermDBI) App(TermDBI, TermDBI) } ``` However, directly writing and reading Lambda terms in de Bruijn index form is painful, so we need to write a function `bruijn()` to convert `Term` to `TermDBI`. This is also why there is still a `String` in the definition of the `TermDBI` type, so that the original variable name can be used for its `Show` implementation, making it easy to print and view the evaluation results with `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}") } } ``` To simplify implementation, if the input `Term` contains free variables, the `bruijn()` function will report an error directly. MoonBit provides a `Result[V, E]` type in the standard library, which has two constructors, `Ok(V)` and `Err(E)`, representing success and failure in computation, respectively. ```moonbit fn bruijn(self : Term) -> Result[TermDBI, String] ``` We take a clumsy approach to save variable names and their associated nesting depth. First, we define the `Index` type: ```moonbit struct Index { name : String depth : Int } ``` Then we write a helper function to find the corresponding `depth` based on a specific `name` from `@list.T[Index]`: ```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) } } } ``` Now we can complete the `bruijn()` function. - Handling `Var` is the simplest, just look up the table to find the corresponding `depth`. - `Abs` is a bit more complicated. First, add one to the `depth` of all `index` in the list (because the Lambda nesting depth has increased by one), and then add `{ name : varname, depth : 0 }` to the beginning of the list. - `App` succeeds when both sub-items can be converted; otherwise, it returns an `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) ``` ### Reduce on TermDBI Reduction mainly deals with App, i.e., calls: ```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() } } ``` First, attempt reduction on both sub-items, then see if `eval(t1)` results in a Lambda. If so, perform one step of variable substitution (via the `subst` function) and then continue simplifying. For Lambdas (`Abs`), simply return them as they are. The implementation of the `subst` function becomes much simpler when we don't need to consider free variables. We just need to keep track of the current depth recursively and compare it with the encountered variables. If they match, it's the variable to be replaced. ```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) } ``` Full code is available [here](/sources/lambda-expression/src/top.mbt) ### Improvement When mapping variable names to indices, we used the `@list.T[Index]` type and updated the entire list every time we added a new Lambda. However, this is actually quite a clumsy method. I believe you can quickly realize that to store a `@list.T[String]` should simply suffice. If you're interested, you can try it yourself. ## G-Machine Lazy evaluation stands as a foundational concept in the realm of programming languages. Haskell, renowned as a purely functional programming language, boasts a robust lazy evaluation mechanism. This mechanism not only empowers developers to craft code that's both more efficient and concise but also enhances program performance and responsiveness, especially when tackling sizable datasets or intricate data streams. In this article, we'll delve into the Lazy Evaluation mechanism, thoroughly examining its principles and implementation methods, and then explore how to implement Haskell's evaluation semantics in [MoonBit](https://www.moonbitlang.com/). ## Contents: * [G-Machine 1](gmachine-1.md) * [Higher-Order Functions and Performance Challenges](gmachine-1.md#higher-order-functions-and-performance-challenges) * [Lazy List Implementation](gmachine-1.md#lazy-list-implementation) * [A Lazy Evaluation Language and Its Abstract Syntax Tree](gmachine-1.md#a-lazy-evaluation-language-and-its-abstract-syntax-tree) * [Why Graph](gmachine-1.md#why-graph) * [Conventions](gmachine-1.md#conventions) * [G-Machine Overview](gmachine-1.md#g-machine-overview) * [Dissecting the G-Machine State](gmachine-1.md#dissecting-the-g-machine-state) * [Corresponding Effect of Each Instruction](gmachine-1.md#corresponding-effect-of-each-instruction) * [Compiling Super Combinators into Instruction Sequences](gmachine-1.md#compiling-super-combinators-into-instruction-sequences) * [Running the G-Machine](gmachine-1.md#running-the-g-machine) * [Conclusion](gmachine-1.md#conclusion) * [Reference](gmachine-1.md#reference) * [G-Machine 2](gmachine-2.md) * [let Expressions](gmachine-2.md#let-expressions) * [Adding Primitives](gmachine-2.md#adding-primitives) * [Conclusion](gmachine-2.md#conclusion) * [G-Machine 3](gmachine-3.md) * [Tracking Context](gmachine-3.md#tracking-context) * [Custom Data Structures](gmachine-3.md#custom-data-structures) * [Epilogue](gmachine-3.md#epilogue) ## Myers Diff ## Contents: * [Myers diff](myers-diff.md) * [Defining "Difference" and Its Measurement Criteria](myers-diff.md#defining-difference-and-its-measurement-criteria) * [Algorithm Overview](myers-diff.md#algorithm-overview) * [Implementation](myers-diff.md#implementation) * [Epilogue](myers-diff.md#epilogue) * [Myers diff 2](myers-diff2.md) * [Recording the Search Process](myers-diff2.md#recording-the-search-process) * [Backtracking the Edit Path](myers-diff2.md#backtracking-the-edit-path) * [Printing the Diff](myers-diff2.md#printing-the-diff) * [Conclusion](myers-diff2.md#conclusion) * [Myers diff 3](myers-diff3.md) * [Divide and Conquer](myers-diff3.md#divide-and-conquer) * [Conclusion](myers-diff3.md#conclusion) ## Segment Tree The Segment Tree is a common data structure used to solve various range modification and query problems. For instance, consider the following problem: - Given a known-length array of numbers with initial values, we need to perform multiple range addition operations (adding a value to all elements in a range) and range sum operations (calculating the sum of elements in a range). Using a standard array, assuming the length og this array is N, each modification and query would take O(N) time. However, after constructing a Segment Tree in O(log N) time, both operations can be performed in O(log N), highlighting the importance of Segment Trees for range queries. This example illustrates just one simple problem that Segment Trees can address. They can handle much more complex and interesting scenarios. In the upcoming articles, we will explore the concept of Segment Trees and how to implement them in MoonBit, ultimately creating a tree that supports range addition and multiplication, enables range sum queries, and has immutable properties. In this section, we will learn the basic principles of Segment Trees and how to write a simple Segment Tree in MoonBit that supports point modifications and queries.