Algebraic Data Type trong Kotlin và Swift

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ặc False, 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 trong Map 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 trong sealed class) nhưng bắt buộc phải nằm cùng 1 file với sealed class. Tuy vậy nhưng những class extend subclass của sealed 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