Algebraic Data Type trong Kotlin và Swift
This post hasn't been updated for 3 years
Introduction
Algebraic Data Type (Kiểu dữ liệu đại số) là một khái niệm lạ lẫm đối với các lập trình viên thuộc kiểu lập trình mệnh lệnh. Trong lập trình hàm thì đây là 1 trong những tính năng được sử dụng rất phổ biến và thường được dùng để implement những cấu trúc dữ liệu phức tạp hoặc để xử lý 1 cách trọn vẹn tất cả các kết quả của 1 business use case.
Vậy thì Algebraic Data Type là gì? Nó là 1 kiểu dữ liệu (Data Type) được tạo ra bởi các phép tính "đại số" (Algebraic). Đại số ở đây là tích (product) và tổng (sum).
- Sum là sự luân phiên giữa các giá trị. Ví dụ
Boolean
là 1 sum type với 1 trong 2 giá trị làTrue
hoặcFalse
, nhưng ko thể vừa làTrue
và vừa làFalse
được. - Product là sự kết hợp của các giá trị. Ví dụ 1
Entry
trongMap
bao gồm 2 giá trị làKey
vàValue
.
Kiểu dữ liệu này được thể hiện bằng những cách tiếp cận khác nhau trong Kotlin và Swift, cụ thể:
Swift:
- Product type được thể hiện bằng tuple.
- Sum type được thể hiện bằng enum.
Kotlin:
- Product type được thể hiện bằng 1
data class
, về cơ bản thì ta có thể coi nó là 1 tuple có tên (Kotlin có tuple nhưng đã deprecated). - Sum type được thể hiện bằng
sealed class
.
Trong nội dung bài viết này, tôi xin phép được tập trung vào việc bàn luận về Sum type do phần lớn chúng ta đều đã sử dụng thành thạo Product type. Và do Kotlin là 1 ngôn ngữ tương đối "mới" (không phải mới ra đời, mà là mới được đưa vào sử dụng trong production do phiên bản 1.0 chỉ mới được release năm ngoái) và cách tiếp cận của nó với Sum type khá là lạ, tôi sẽ nói về sealed class
nhiều hơn so với enum
của Swift.
sealed class
sealed class
cho phép chúng ta thể hiện sự phân cấp class, trong đó mỗi object chỉ có thể thuộc 1 trong các kiểu dữ liệu đã cho. Về cơ bản sealed class
là một phiên bản mở rộng của enum
, khác biệt ở chỗ mỗi enum
constant chỉ có thể có 1 instance, trong khi đó thì mỗi subclass của sealed class
có thể có nhiều instance như class thường vậy, và do đó chúng ta có thể chứa state trong các class này.
Để hiểu hơn về sealed class
thì hãy đi vào 1 ví dụ đơn giản là implement kiểu Boolean
nói ở trên:
sealed class Boolean
class True(): Boolean()
class False(): Boolean()
Ở đây chúng ta đã tạo ra 1 sealed class
là Boolean
chứa 2 kiểu dữ liệu là True
và False
. 1 số đặc tính của sealed class
mà chúng ta cần biết là:
sealed class
là 1 abstract class, nó có thể chứa abstract properties hoặc functions nhưng nó không thể được khởi tạo trực tiếp.sealed class
không thể có non-private constructor (constructor mặc định làprivate
)- Subclass của 1
sealed class
không nhất thiết phải là nested class (nằm trongsealed class
) nhưng bắt buộc phải nằm cùng 1 file vớisealed class
. Tuy vậy nhưng những class extend subclass củasealed class
(thừa kế gián tiếp) thì có thể cho vào đâu cũng được.
Sức mạnh của sealed class
được thể hiện rõ nhất khi chúng ta kết hợp nó với việc sử dụng pattern matching bằng biểu thức when
. Ví dụ với Boolean
:
fun evaluate(value: Boolean) = when(value) {
is True -> System.out.println("True")
is False -> System.out.println("False")
}
Như các bạn có thể thấy, chúng ta không cần phải có 1 branch else
trong when
như các kiểu dữ liệu khác. Điều này bởi vì compiler đã biết được là chúng ta đã handle tất cả các case có thể xảy ra với kiểu Boolean
(chỉ có thể là True
hoặc False
). Nếu bạn xoá 1 case đi như dưới đây:
fun evaluate(value: Boolean) = when(value) {
is True -> System.out.println("True")
}
compiler sẽ báo cho chúng ta là đã handle thiếu 1 case có thể xảy ra và không cho code đc compile:
when expression must be exhaustive, add necessary 'is False' branch or 'else' branch instead
Đây là 1 tính năng rất hay, vì chúng ta có thể lợi dụng type system để nhắc nhở cho chúng ta việc handle tất cả các trường hợp có thể xảy ra của 1 use case. Nếu trong tương lai chúng ta có thêm 1 trường hợp nào nữa thì compiler cũng sẽ báo cho chúng ta biết để có thể xử lý.
Trên đây là 1 ví dụ quá đơn giản và có thể bạn đã nhận ra là nó có thể đc implement bằng enum
, tuy vậy thì nếu dùng enum
vào bên trên thì bạn bắt buộc phát thêm 1 branch else
. Hãy cùng xem 1 số ví dụ phức tạp hơn về cách sử dụng sum type trong Kotlin.
Binary tree
Đây là ví dụ của Wikipedia về cách implement 1 binary tree trong Haskell:
data Tree = Empty
| Leaf Int
| Node Tree Tree
Trong đó thì Empty
để chỉ 1 cây rỗng, Leaf
chứa data với kiểu Int
, Node
sắp xếp data thành các nhánh.
Hãy thử xem Kotlin và Swift giải quyết bài toán trên như thế nào nhé. Để tăng độ phức tạp và độ hoàn chỉnh thì chúng ta sẽ dùng generics để thể hiện kiểu dữ liệu chứa trong Leaf
và Node
thay vì Int
như trên, và ta tạm coi bài toán implement 1 full binary tree, mỗi node đều có 0 hoặc 2 node con, mặc dù chúng ta có thể implement rooted binarry tree bằng optionals để thể hiện 1 trong 2 node con có thể null.
Swift
Như đã nói ở trên, chúng ta sử dụng enum
để thể hiện sum type trong Swift:
enum Tree<T> {
case Empty
case Leaf(data: T)
case Node(data: T, left: Tree<T>, right: Tree<T>)
}
Node
có 2 nhánh trái và phải cũng nhận vào type Tree
, vậy nên đây cũng là 1 kiểu dữ liệu đệ quy.
Khi bạn paste đoạn code trên vào Playground, Xcode sẽ báo lỗi
error: recursive enum 'Tree<T>' is not marked 'indirect'
Do enum
là 1 value type giống như struct
, compiler cần phải biết được size của nó khi compile. Bởi vì associated value trong enum cũng chính là 1 phần của enum nên khi compiler tính toán size của nó sẽ rơi vào 1 vòng lặp vĩnh viễn với case Node
(bởi vì associated value của nó là chính nó). Bởi vì lí do này, chúng ta không thể có đệ quy trực tiếp đối với enum
trong Swift.
Tuy vậy chúng ta vẫn có thể có đệ quy "gián tiếp" bằng cách giữ associated value của Node
trong 1 reference type như class hoặc protocol, và khi đó thì associated value sẽ chỉ là 1 pointer với size cố định. Hoặc chúng ta có thể sử dụng keyword indirect
để compiler có thể tự thêm 1 layer gián tiếp cho enum
của chúng ta:
enum Tree<T> {
case Empty
case Leaf(data: T)
indirect case Node(data: T, left: Tree<T>, right: Tree<T>)
}
Kotlin
Kiểu dữ liệu này được thể hiện bằng sealed class
như sau:
sealed class Tree<T>
class Empty() : Tree<Nothing>()
data class Leaf<T>(val data: T) : Tree<T>()
data class Node<T>(val data: T, val left: Tree<T>, val right: Tree<T>) : Tree<T>()
Nhìn qua thì hơi dài dòng hơn Swift 1 chút đúng không ạ
Ở đây chúng ta cũng có kiểu dữ liệu đệ quy như trên, nhưng do sealed class
là 1 class nên có thể có đệ quy trực tiếp (giá trị được lưu giữ thông qua reference).
Calculate depth of tree
Hãy cùng implement 1 hàm để tính chiều cao của cây:
Swift
func depth<T>(tree: Tree<T>) -> Int {
switch(tree) {
case .Empty:
return 0
case .Leaf(_):
return 1
case .Node(_, let left, let right):
return 1 + max(depth(tree: left), depth(tree: right))
}
}
Kotlin
fun <T> depth(tree: Tree<T>) : Int = when(tree) {
is Empty -> 0
is Leaf -> 1
is Node -> 1 + maxOf(depth(tree.left), depth(tree.right))
}
Ở đây đầu tiên chúng ta check xem cây này có rỗng không, nếu rỗng thì chiều cao là 0. Sau đó dùng đệ quy để tính toán chiều cao của subtree trái và phải để lấy số lớn hơn, cuối cùng là + với 1 để thể hiện là root node.
Bạn có thể thấy là ở cả Kotlin và Swift, chúng ta không cần thêm 1 branch else
hoặc default
nếu đã xử lý tất cả các case của sum type. Đối với sum type trong các ngôn ngữ nói chung, compiler đóng vai trò rất quan trọng trong việc đảm bảo 1 switch case đã có đầy đủ tất cả các trường hợp mà chúng ta define ra với việc sử dụng pattern matching. Ví dụ khi chúng ta thử xoá 1 trường hợp trong switch:
Xcode
IntelliJ IDEA
Một điểm thú vị nữa là nếu bạn để ý thì ở case is Node
, compiler đã smart cast object tree
sang kiểu Node
nên chúng ta ko cần phải cast bằng tay mà có thể truy cập trực tiếp các member của Node
luôn. Đây là 1 trong những tính năng rất hay của Kotlin mà không có trong Java.
Hãy thử tính chiều cao của cây dưới đây nhé
let tree = Tree.Node(1, .Node(2, .Leaf(4), .Leaf(5)), .Leaf(3))
depth(tree: tree) //3
val tree = Node(1, Node(2, Leaf(4), Leaf(5)), Leaf(3))
println(depth(tree)) //3
Fetching data
Đây có lẽ là 1 ví dụ sẽ gần gũi hơn với công việc của chúng ta. Giả sử bài toán đặt ra là lấy news feed của 1 user về nếu họ đã đăng nhập, chúng ta sẽ có 3 trường hợp sau đây:
- User chưa đăng nhập.
- User đã đăng nhập và lấy news feed thành công.
- User đã đăng nhập và lấy news feed thất bại.
Với cách làm bình thường thì chúng ta sẽ sử dụng interface với 3 hàm:
interface Result {
fun onUserNotSignedIn(errorCode: Int)
fun onFetchSuccessfully(feeds: List<Feeds>)
fun onFetchFailed(errorCode: Int, msg: String)
}
và sẽ có callback để gọi vào đúng hàm. Nhưng 1 cách khác để làm code trở nên dễ đọc và dễ theo dõi hơn cách này là sử dụng sum type:
sealed class Result
data class UserNotSignedIn(val errorCode: Int) : Result()
data class FetchSuccessfully(val feeds: List<Feeds>) : Result()
data class FetchFailed(val errorCode: Int, val msg: String) : Result()
Sau đó ta tạo ra 1 hàm để xử lý tất cả các trường hợp này:
fun handle(result: Result) : Unit = when(result) {
is UserNotSignedIn -> openSignedInScreen()
is FetchSuccessfully -> displayResults(result.feeds)
is FetchFailed -> displayError(result.msg)
}
Cách sử dụng:
fun fetching(): Result {
//Do network requests...
//Simulate the situation where the fetching failed
return FetchFailed(404, "Not found")
}
handle(fetching())
Under the hood
Hãy cùng xem bytecode được compiler generate ra cho hàm handle
ở trên (Tools -> Kotlin -> Show Kotlin Bytecode)
LINENUMBER 113 L2
ALOAD 1
INSTANCEOF UserNotSignedIn
IFEQ L3
L4
INVOKESTATIC TestKt.openSignedInScreen ()V
GOTO L5
L3
LINENUMBER 114 L3
ALOAD 1
INSTANCEOF FetchSuccessfully
IFEQ L6
L7
ALOAD 0
CHECKCAST FetchSuccessfully
INVOKEVIRTUAL FetchSuccessfully.getFeeds ()Ljava/util/List;
INVOKESTATIC TestKt.displayResults (Ljava/lang/Object;)V
GOTO L5
L6
LINENUMBER 115 L6
ALOAD 1
INSTANCEOF FetchFailed
IFEQ L8
L9
ALOAD 0
CHECKCAST FetchFailed
INVOKEVIRTUAL FetchFailed.getMsg ()Ljava/lang/String;
INVOKESTATIC TestKt.displayError (Ljava/lang/String;)V
GOTO L5
L8
NEW kotlin/NoWhenBranchMatchedException
DUP
INVOKESPECIAL kotlin/NoWhenBranchMatchedException.<init> ()V
ATHROW
L10
Nếu bạn ko quen đọc bytecode thì có thể decompile sang code Java, chúng ta sẽ được như sau:
public static final void handle(@NotNull Result result) {
Intrinsics.checkParameterIsNotNull(result, "result");
if (result instanceof UserNotSignedIn) {
openSignedInScreen();
} else if (result instanceof FetchSuccessfully) {
displayResults(((FetchSuccessfully)result).getFeeds());
} else {
if (!(result instanceof FetchFailed)) {
throw new NoWhenBranchMatchedException();
}
displayError(((FetchFailed)result).getMsg());
}
}
Có thể thấy là compiler đã generate ra 1 dãy if-else để check instanceof
của các subclass của sealed class
. Nếu giá trị match với class thì nó sẽ smart cast sang type tương ứng, còn nếu không match 1 case nào thì kotlin/NoWhenBranchMatchedException
sẽ được throw ra.
Conclusion
Ở bài này chúng ta đã tìm hiểu về cách sử dụng sum type kết hợp với pattern matching của biểu thức when
/ switch
để có thể chắc chắn là bạn đã xử lý tất cả các kết quả có thể xảy ra của 1 use case. Cảm ơn các bạn đã theo dõi
All Rights Reserved