当前位置:网站首页>Kotlin core programming - algebraic data types and pattern matching (3)
Kotlin core programming - algebraic data types and pattern matching (3)
2022-07-06 00:42:00 【csdn1225987336】
List of articles
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 .
边栏推荐
- Arduino六足机器人
- Search (DFS and BFS)
- Go learning --- structure to map[string]interface{}
- Atcoder beginer contest 254 [VP record]
- Spark AQE
- Room cannot create an SQLite connection to verify the queries
- 图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
- vSphere实现虚拟机迁移
- Synchronized and reentrantlock
- NLP generation model 2017: Why are those in transformer
猜你喜欢
XML Configuration File
Spark SQL null value, Nan judgment and processing
Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike
【EI会议分享】2022年第三届智能制造与自动化前沿国际会议(CFIMA 2022)
XML配置文件
MySQL storage engine
MIT doctoral thesis | robust and reliable intelligent system using neural symbol learning
Arduino hexapod robot
Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
随机推荐
[groovy] compile time meta programming (compile time method interception | method interception in myasttransformation visit method)
免费的聊天机器人API
Uniapp development, packaged as H5 and deployed to the server
云导DNS和知识科普以及课堂笔记
How to use the flutter framework to develop and run small programs
Promise
小程序容器可以发挥的价值
For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
【EI会议分享】2022年第三届智能制造与自动化前沿国际会议(CFIMA 2022)
小程序技术优势与产业互联网相结合的分析
Spark SQL UDF function
Start from the bottom structure and learn the introduction of fpga---fifo IP core and its key parameters
CTF daily question day44 rot
anconda下载+添加清华+tensorflow 安装+No module named ‘tensorflow‘+KernelRestarter: restart failed,内核重启失败
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
Room cannot create an SQLite connection to verify the queries
FFmpeg抓取RTSP图像进行图像分析
uniapp开发,打包成H5部署到服务器
Illustrated network: the principle behind TCP three-time handshake, why can't two-time handshake?
Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike