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 ạ