# Examples Here are some examples built with MoonBit. # Contents: * [Sudoku Solver](sudoku/index.md) * [Squares, Units, and Peers](sudoku/index.md#squares-units-and-peers) * [Preprocessing the Grid](sudoku/index.md#preprocessing-the-grid) * [Search](sudoku/index.md#search) * [Conclusion](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) ## Sudoku Solver Sudoku is a logic-based puzzle game that originated in 1979. It was well-suited for print media like newspapers, and even in the digital age, many Sudoku game programs are available for computers and smartphones. Despite the variety of entertainment options today, Sudoku enthusiasts continue to form active online communities. This article will demonstrate how to write a suitable program to solve Sudoku using MoonBit.  ### Squares, Units, and Peers The most common form of Sudoku is played on a 9x9 grid. We label the rows from top to bottom as A-I, and the columns from left to right as 1-9. This gives each square in the grid a coordinate, for example, the square containing the number 0 in the grid below has the coordinate C3. ```default 1 2 3 4 5 6 7 8 9 A . . . . . . . . . B . . . . . . . . . C . . 0 . . . . . . D . . . . . . . . . E . . . . . . . . . F . . . . . . . . . G . . . . . . . . . H . . . . . . . . . I . . . . . . . . . ``` This 9x9 grid has a total of 9 units, and each unit contains squares that must have unique digits from 1 to 9. However, in the initial state of the game, most squares do not contain any digits. ```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 ``` Beyond the units, another important concept is peers. A square's peers include other squares in the same row, column, and unit. For example, the peers of C2 include these squares: ```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| | ---------+---------+--------- | | | | | | ---------+---------+--------- | | | | | | ``` No two squares that are peers can contain the same digit. We need a data type, `Grid[T]`, to store the 81 squares and the information associated with each square. This can be implemented using a hashtable, but using an array would be more compact and simple. First, we write a function to convert coordinates A1-I9 to indices 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") } ``` Then we wrap the array and provide operations for creating, accessing, assigning values to specific coordinates, and copying `Grid[T]`. By overloading the op_get and op_set methods, we can write convenient code like `table["A2"]` and `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 } ``` Next, we prepare some constants: ```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] = ...... ``` The process of constructing the units and peers tables is tedious, so it will not be detailed here. ### Preprocessing the Grid We use a string to represent the initial Sudoku grid. Various formats are acceptable; both `.` and `0` represent empty squares, and other characters like spaces and newlines are ignored. ```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 . . . . . . ``` For now, let's not consider game rules too much. If we only consider the digits that can be filled in each square, then 1-9 are all possible. Therefore, we initially set the content of all squares to `['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) ... } ``` Next, we need to assign values to the squares with known digits from the input. This process can be implemented with the function `assign(values, key, val)`, where `key` is a string like `A6` and `val` is a character. It is easy to write such code. ```moonbit fn assign(values : Grid[@immut/sorted_set.T[Char]], key : String, val : Char) -> Unit { values[key] = @immut/sorted_set.singleton(val) } ``` This implementation is simple and precise, but we can do more. Now, we can reintroduce the rules that we set aside earlier. However, the rules themselves do not tell us what to do. We need heuristic strategies to gain insights from the rules, similar to solving Sudoku with pen and paper. Let's start with the elimination method: - **Strategy 1**: If a square `key` is assigned a value `val`, then its peers (peers[key]) should not contain `val` in their lists of possible values, as this would violate the rule that no two squares in the same unit, row, or column can have the same digit. - **Strategy 2**: If there is only one square in a unit that can hold a specific digit (possibly happen after applying the above rule several times), then that digit should be assigned to that square. We adjust the code by defining an `eliminate` function, which removes a digit from the possible values of a square. After performing the elimination task, it applies the above strategies to `key` and `val` to attempt further eliminations. Note that it includes a boolean return value to handle possible contradictions. If the list of possible values for a square becomes empty, something went wrong, and we return `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 } } ``` Next, we define `assign(values, key, val)` to remove all values except `val` from the possible values of `key`. ```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 } ``` These two functions apply heuristic strategies to each square they access. A successful heuristic application introduces new squares to consider, allowing these strategies to propagate widely across the grid. This is key to quickly eliminating invalid options. In fact, this preprocessing can already solve some simple Sudoku puzzles. ```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 #| ), ) } ``` If you are interested in artificial intelligence, you might recognize this as a Constraint Satisfaction Problem (CSP), and `assign` and `eliminate` are specialized arc consistency algorithms. For more on this topic, refer to Chapter 6 of *Artificial Intelligence: A Modern Approach*. ### Search After preprocessing, we can boldly use brute-force enumeration to search for all feasible combinations. However, we can still use the heuristic strategies during the search process. When trying to assign a value to a square, we still use `assign`, which allows us to apply previous optimizations to eliminate many invalid branches during the search. Another point to note is that conflicts may arise during the search (when a square's possible values are exhausted). Since mutable structures make backtracking troublesome, we directly copy values each time we assign a value. ```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() } } ``` Let's run the example taken from [magictour](http://magictour.free.fr/top95), a list of difficult Sudoku puzzles, which is not easy for humans. ```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 #| ), ) } ``` On a regular development machine, it takes only about 0.11 seconds to solve this Sudoku. ### Conclusion The purpose of games is to relieve boredom and bring joy. If playing a game becomes more anxiety-inducing than exciting, it might go against the game designer's original intent. The article demonstrated that simple elimination methods and brute-force search can quickly solve some Sudoku puzzles. This does not mean that Sudoku is not worth playing; rather, it reveals that one should not be overly concerned with an unsolvable Sudoku puzzle. Let's play with MoonBit with ease! This tutorial references Peter Norvig's Sudoku-solving write-up. ## 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.