Kotlin core programming - algebraic data types and pattern matching (3)

One 、 Algebraic data type （ADT）

In computer programming , Especially in functional programming and type theory ,ADT It is a combination type （composite type）. for example , A type is composed of other types . Two common types of algebra are “ and （sum）” The type and “ product （product）” type .

1.1、 From algebra to type

Algebra. , Simple understanding is the symbol that can represent numbers , such as x,y etc. . Look at two expressions ：

x * 1 = z
a + 2 = c

It can be seen that , Algebra in the first expression x And 1 Through multiplication, we get a new algebra z, Algebra in the second expression a And 2 A new algebra is obtained by adding c. Think about it , If algebra and numbers in two expressions are replaced by types or values in programming language , Then whether they can get a new type through some operation ？

When we replace these algebras or numbers with types , So this type is replaced by algebra or numbers , And the new types produced by these types are called algebraic types （ADT）.

1.2、 Count

Each type is instantiated , There will be corresponding values , such as Boolean There are two possible values for type ：true or false. The value type is 2, It's called counting .
Another example Unit type , It means that there is only one instance , That is to say, there is only one value , So the way of counting ,Unit The corresponding number 1.

1.3、 Product type

stay ADT in , The representation of product type is similar to multiplication , We can understand it as a combination . For example, there is a type a, A type b, To combine into one type c It should be ：

c = a * b

The above said Boolean The type corresponds to 2,Unit The type corresponds to 1, Then the product type produced by their combination should be ：

2 * 1 = 2

Using actual code to express the combination of two types is ：

class BooleanProductUnit (a: Boolean, b: Unit){
    }

This code builds a named BooleanProductUnit Class , There is a type of Boolean Parameters of a And a type of Unit Parameters of b. Take another look at the instance value corresponding to this class ：

val a = BooleanProductUnit (false, Unit)
val b = BooleanProductUnit (true, Unit)

You can see ,BooleanProductUnit Class can only have two values at most . It should be clear , When we use classes for composition , It's actually a kind of product operation , Product types can be seen as types that hold certain types at the same time , such as BooleanProductUnit Types hold at the same time Boolean The type and Unit type .

Because we can judge a certain type or a certain kind of value according to the count , So counting can also be used at compile time for when Such statements do branch checking .

1.4、 And type and sealing class

Previously, we introduced that the product type corresponds to multiplication in algebraic operations , So and type （sum） As the name suggests, it corresponds to addition in algebra . Define an enumeration class Day：

enum class Day {
     SUN, MON, TUE, WED, THU, FRI, SAT }

Enumeration class is a and type . Because every constant in an enumeration class is an object , For example, in the example above SUN, It is the same as other constants , There can only be one value , So we write it down as 1.

• And types are type safe . Because it is a closed loop , For example, the above enumeration class Day, All in all 7 Possible values , No other values are possible , So don't worry about illegal situations when using .
• And type is a “or” The relationship between . The product type can have several types , For example, in the former area type BooleanProductUnit Types have both Boolean and Unit, So the product type is a “and” Relationship . And the and type can only be one of them at a time , You cannot have two types at the same time .

But the functions of and types are relatively simple when used , The expansibility is not strong . We need a grammar that is more powerful in expression , That's it Last chapter 2.1 The sealing class mentioned in section .

sealed class Day {
    
    class SUN : Day()
    class MON : Day()
    class TUE : Day()
    class WED : Day()
    class THU : Day()
    class FRI : Day()
    class SAT : Day()
}

Use sealed classes , In other words, the biggest advantage of and type is , When we use when Don't consider illegal situations when expressing , That is to say, we can omit else Branch . Consider the following code ：

    fun schedule(day: Day) {
    
        when (day) {
    
            is Day.SUN -> fun1()
            is Day.MON -> fun2()
            is Day.TUE -> fun3()
            is Day.WED -> fun4()
            is Day.THU -> fun5()
            is Day.FRI -> fun6()
            is Day.SAT -> fun7()
        }
    }

This code is a ADT And when Examples of expression combination . You can see , We don't need to write an extra one here else To represent the default options , Because it's type safe .

1.5、 Construct algebraic data types

How to construct an algebraic data type , For example, we now need to calculate the circle according to the corresponding conditions 、 Rectangle 、 The area of the triangle . First , Find their common ground , That is, they are all geometric figures （Shape）, Then you can use sealed classes to abstract ：

sealed class Shape {
    
    class Circle(val radius: Double) : Shape()
    class Rectangle(val width: Double, val height: Double) : Shape()
    class Triangle(val base: Double, val height: Double) : Shape()
}

Now we abstract these figures into ADT, Whole Shape Is a and type , Among them Circle、Rectangle、Triangle That is, by adding the basic type Double Product types constructed into classes and combined .

ADT The biggest advantage is that you can use it with confidence when expression , Use now when Expression to define a method for calculating the area of each figure ：

    fun getArea(shape: Shape): Double = when (shape) {
    
        is Shape.Circle -> Math.PI * shape.radius * shape.radius
        is Shape.Rectangle -> shape.width * shape.height
        is Shape.Triangle -> shape.base * shape.height / 2.0
    }

You can see , adopt ADT and when expression , The code is very clean , If you use Java Realization , You need to write a pile if-else expression , But also consider the illegal situation , Poor readability .

Two 、 Pattern matching

2.1、 What is mode

stay Chapter one The second section introduces “ expression ” The concept of . A number 、 An instance of an object , Or say , Any combination that can find a specific value can be called an expression .

What we call pattern , It is essentially these expressions , What pattern matching matches is actually an expression . therefore , When we construct patterns, we are constructing expressions .

2.2、 Common patterns

We learned that patterns in pattern matching are actually expressions . This section will pass when Expression to explain several common pattern matching .

1、 Constant mode

The constant pattern is simple , With what we know well if-else perhaps switch-case Statements are almost no different , Is to compare whether two constants are equal .

    fun constantPattern(a: Int) = when (a) {
    
        1 -> "It is 1"
        2 -> "It is 2"
        else -> "It is other number"
    }

2、 Type pattern

The type pattern is actually the above 1.5 Examples introduced in .

sealed class Shape {
    
    class Circle(val radius: Double) : Shape()
    class Rectangle(val width: Double, val height: Double) : Shape()
    class Triangle(val base: Double, val height: Double) : Shape()
}

    fun getArea(shape: Shape): Double = when (shape) {
    
        is Shape.Circle -> Math.PI * shape.radius * shape.radius
        is Shape.Rectangle -> shape.width * shape.height
        is Shape.Triangle -> shape.base * shape.height / 2.0
    }

3、 Logical expression pattern

In the use of when When you make a match , There is also a common match , That is to match logical expressions .

    // example 1
    fun logicPattern(a: Int) = when {
    
        a in 2..11 -> "$a >1 and <10"
        else -> ">10"
    }

    // example 2
    fun logicPattern(a: String) = when {
    
        a.contains("a") -> "str contains a"
        else -> "str no contains a"
    }

example 1 in , We match whether a number is in a numerical range .
example 2 in , We matched whether a string contains another string .

Be careful , there when There are no parameters behind , In both cases ,when Each branch of the expression performs something similar to if Expression to judge and so on .

2.3、 Handle nested expressions

First, let's define a structure ：

• Num Class represents the value of an integer ;
• Operate Class is a tree structure , Some complex expressions are used , among opName Attributes represent common operators , such as “+” “-” “*” “/”.

    sealed class Expr {
    
        data class Num(val value: Int) : Expr()
        data class Operate(val opName: String, val left: Expr, val right: Expr) : Expr()
    }

Now return the corresponding results according to different conditions , First judgement expr Whether it is Num type , If so, go straight back , Otherwise, go to the next judgment . There are two else if, If they are not satisfied ,else Just go back to expr In itself .

It can be seen that , If you use this code Java To write , It will be more complicated , because else if The conditions in also need to do a lot of type conversion statements to execute ,Kotlin This is because it supports Smar Casts（3.1 Will introduce ）.

    fun simplifyExpr(expr: Expr): Expr = if (expr is Expr.Num) {
    
        expr
    } else if (expr is Expr.Operate   // If the conditions are met  expr  Will automatically switch to  Expr.Operate  type 
            && expr.opName == "+"   //expr  Convert to  Expr.Operate  Then you can call  opName  The attribute is 
            && expr.left is Expr.Num  // If the conditions are met  expr.left  Will automatically switch to  Expr.Num  type 
            && expr.left.value == 0) {
      //expr.left  Convert to  Expr.Operate  Then you can call  opName  The attribute is 
        expr.right
    } else if (expr is Expr.Operate
            && expr.opName == "+"
            && expr.right is Expr.Num
            && expr.right.value == 0) {
    
        expr.left
    } else expr

You can find ,if-else Statements are not concise in dealing with complex nested expressions , Poor readability , First, you can find that you want to return expr.right Conditions to be met ：

• expr is Expr.Operate
• expr.opName == “+”
• expr.left is Expr.Num
• expr.left.value == 0

return expr.left Conditions to be met ：

• expr is Expr.Operate
• expr.opName == “+”
• expr.right is Expr.Num
• expr.right.value == 0

Use when Expression to rewrite .

    fun simplifyExpr(expr: Expr): Expr = when (expr) {
    
        is Expr.Num -> expr
        is Expr.Operate -> when (expr) {
    
            Expr.Operate("+", Expr.Num(0), expr.right) -> expr.right
            Expr.Operate("+", expr.left, Expr.Num(0)) -> expr.left
            else -> expr
        }
    }

3、 ... and 、 Enhanced pattern matching

3.1、 Type testing / Type conversion

Type testing and type conversion workflow ： First, the type will be tested , Determine the type of value given , Then type conversion . such as ：

expr instanceof Expr.Operate && (Expr.Operate)expr.name.equals("+")

stay Kotlin in , Support by itself Smart Casts, So there is no need to do type conversion , You only need to implement type testing .

expr.left is Expr.Num && expr.left.value = 0

Just judge first expr.left Is the type Expr.Num, next Kotlin Will automatically help us convert to Expr.Num type .

3.2、 Object oriented decomposition

In the previous sections , We all have a problem when using pattern matching , It is necessary to constantly determine the type of a given object , Like the one above ：expr.left is Expr.Num, Then access its internal properties according to the specific object type . If it is Java Words , You also need to cast , Then we can realize the operation of specific objects .

Solve this problem , We can define a series of methods in the parent class , Determine whether it is a value by calling a method , Then implement these methods in subclasses , You can do corresponding operations in different subclasses , You don't have to write code to judge the type many times , Like here isZero Method is used to determine whether an expression is 0,isAddZero Method is used to determine whether the operator is “+” also left Attribute or right Whether one of them is 0. This idea is called object-oriented decomposition .

    sealed class Expr {
    
        abstract fun isZero(): Boolean
        abstract fun isAddZero(): Boolean
        abstract fun left(): Expr
        abstract fun right(): Expr
        data class Num(val value: Int) : Expr() {
    
            override fun isZero(): Boolean = this.value == 0
            override fun isAddZero(): Boolean = false
            override fun left(): Expr = throw Throwable("no element")
            override fun right(): Expr = throw Throwable("no element")
        }

        data class Operate(val opName: String, val left: Expr, val right: Expr) : Expr() {
    
            override fun isZero(): Boolean = false
            override fun isAddZero(): Boolean = this.opName == "+" && (this.left.isZero() || this.right.isZero())
            override fun left(): Expr = this.left
            override fun right(): Expr = this.right
        }
    }

You can see , In addition to defining the methods that need to be used to judge isZero、isAddZero Outside , Also defined left、right Method , This is because by calling isZero perhaps isAddZero To judge ,Smart Casts It will no longer work , That is, the compiler will not automatically determine and then convert to the corresponding type , The compiler only knows that the type is Expr, So you need to define left、right Method to get the corresponding type Num, Then the corresponding method can be called .

Now let's implement simplifyExpr Method , Put the innermost Expr.Num(0) Come back out .

    fun simplifyExpr(expr: Expr): Expr = when {
    
        expr.isAddZero() && expr.right().isAddZero() && expr.right().left().isZero() -> expr.right().left()
        else -> expr
    }

        val expr = Expr.Operate("+", Expr.Num(0), Expr.Operate("+", Expr.Num(0), Expr.Num(1)))
        println(simplifyExpr(expr)) // The result is  Num(value=0)

Through object-oriented decomposition , We did simplify the code . But the problem is clear , If the business is complex , We need to define many methods to make judgments , This makes the structure of the whole class very bloated , It's almost all the implementation of some methods . in addition , If you need to add a subclass , We have to implement all these methods again , It may also cause the methods in the previous subclasses to need to be re implemented , The price is high . Then look at 3.3.

3.3、 Visitor design patterns

First, we define another class Visitor. This class acts as an access , Use it to access the classes we need to operate on （ Here, it is referred to as the target class ）.

    class Visitor {
    
        fun matchZero(): Boolean = false
        fun matchZero(expr: Expr.Num): Boolean = expr.value == 0

        fun matchAddZero(): Boolean = false
        fun matchAddZero(expr: Expr.Operate): Boolean = when (expr) {
    
            Expr.Operate("+", Expr.Num(0), expr.right) -> true
            Expr.Operate("+", expr.left, Expr.Num(0)) -> true
            else -> false
        }

        fun doSimplifyExpr(expr: Expr.Num): Expr = expr
        fun doSimplifyExpr(expr: Expr.Operate, v: Visitor): Expr = when {
    
            (expr.right is Expr.Num && v.matchAddZero(expr) && v.matchAddZero())
                    && (expr.right is Expr.Operate && expr.right.left is Expr.Num)
                    && v.matchZero(expr.right.left) -> expr.right.left
            else -> expr
        }
    }

Next, we need to define corresponding methods in each subclass , And use parameters to inject the visitor object .

    sealed class Expr {
    
        abstract fun isZero(v: Visitor): Boolean
        abstract fun isAddZero(v: Visitor): Boolean
        abstract fun simplifyExpr(v: Visitor): Expr
        abstract fun left(): Expr
        abstract fun right(): Expr
        data class Num(val value: Int) : Expr() {
    
            override fun isZero(v: Visitor): Boolean = v.matchZero(this)
            override fun isAddZero(v: Visitor): Boolean = v.matchAddZero()
            override fun simplifyExpr(v: Visitor): Expr = v.doSimplifyExpr(this)
            override fun left(): Expr = throw Throwable("no element")
            override fun right(): Expr = throw Throwable("no element")
        }

        data class Operate(val opName: String, val left: Expr, val right: Expr) : Expr() {
    
            override fun isZero(v: Visitor): Boolean = v.matchZero()
            override fun isAddZero(v: Visitor): Boolean = v.matchAddZero(this)
            override fun simplifyExpr(v: Visitor): Expr = v.doSimplifyExpr(this, v)
            override fun left(): Expr = this.left
            override fun right(): Expr = this.right
        }
    }

Next you can call .

    fun simplifyExpr(expr: Expr, visitor: Visitor): Expr = when {
    
        expr.isAddZero(visitor) && expr.right().isAddZero(visitor) && expr.right().left().isZero(visitor) -> expr.right().left()
        else -> expr
    }

        val expr = Expr.Operate("+", Expr.Num(0), Expr.Operate("+", Expr.Num(0), Expr.Num(1)))
        println(simplifyExpr(expr, Visitor())) // The result is  Num(value=0)

The advantage of adopting visitor mode is , We put the implementation of methods in the class outside , This makes the structure of the class look more concise .