6. ADT (Algebraic Data Type) and Tree - Gaoey/scala-diary GitHub Wiki
List is just one example of what’s called an algebraic data type (ADT). (Somewhat confusingly, ADT is sometimes used elsewhere to stand for abstract data type.)
An ADT is just a data type defined by one or more data constructors, each of which may contain zero or more arguments.
We say that the data type is the sum or union of its data constructors, and each data constructor is the product of its arguments, hence the name algebraic data type.
แปลไทย: data type คือ การรวมกัน(union) ของ data constructor(data constructor ก็คือ case class หรือก็คือ class ที่มี constructor ด้วยตัวมันเอง) และ แต่ละ constructor ก็มี argument ของมันเอง
Algebraic data types(ADT) สามารถนำมาทำเป็น data structure ที่เรารู้จัก
Let’s define a simple binary tree data structure:
// Tree คือ ADT ที่มีการรวบ data constructor(Leaf, Branch) ไว้
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
ซึ่ง Pattern matching เป็นวิธีที่สะดวกในการเข้าถึงองค์ประกอบต่างๆของ ADT ได้ดี
List ก็คือ Singly Linked List จึงเป็น ADT Tree ก็คือ tree ที่เรารู้จัก จากตัวอย่างข้างบนก็เป็น ADT
Tree ADT
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
Example
Branch(Branch(Leaf("a"),Leaf("b")), Branch(Leaf("c"),Leaf("d")))
Branch
v ----- [-*][*-] ----- v
| left right |
Branch Branch
v -- [-*][*-] -- v v -- [-*][*-] -- v
| left right | | left right |
| | | |
Leaf Leaf Leaf Leaf
["a"] ["b"] ["c"] ["d"]
หา size ใน tree
def size[A](t: Tree[A]): Int = t match {
case Leaf(_) => 1
case Branch(l, r) => 1 + size(l) + size(r)
}
def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
size(t) shouldBe 5
หา depth ของ tree
def depth[A](t: Tree[A]): Int = t match {
case Leaf(_) => 0
case Branch(l, r) => 1 + (depth(l) max depth(r))
}
def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
depth(t) shouldBe 2
map ใน tree
def map[A, B](t: Tree[A])(f: A => B): Tree[B] = t match {
case Leaf(a) => Leaf(f(a))
case Branch(l, r) => Branch(map(l)(f), map(r)(f))
}
def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
Tree.map(t)(_ * 2) shouldBe Branch(Branch(Leaf(2), Leaf(4)), Leaf(6))
เราจะเห็นได้ว่ามี pattern ของ tree ที่ทำซ้ำๆคือ เคส Leaf ที่ทำอะไรบางอย่างและ เคส Branch ที่ทำอะไรบางอย่าง เราจึงทำ HOF ขึ้นมาเพื่อให้เขียน code ซ้ำๆน้อยลง เรียกว่า fold
def fold[A, B](t: Tree[A])(f: A => B)(g: (B, B) => B): B = t match {
case Leaf(a) => f(a)
case Branch(l, r) => g(fold(l)(f)(g), fold(r)(f)(g))
}
def sizeViaFold[A](t: Tree[A]): Int =
fold(t)(a => 1)(1 + _ + _)
def maximumViaFold(t: Tree[Int]): Int =
fold(t)(a => a)(_ max _)
def depthViaFold[A](t: Tree[A]): Int =
fold(t)(a => 0)((d1, d2) => 1 + (d1 max d2))
def mapViaFold[A, B](t: Tree[A])(f: A => B): Tree[B] =
fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_, _))
def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
sizeViaFold(t) shouldBe 5
maximumViaFold(t) shouldBe 3
depthViaFold(t) shouldBe 2
mapViaFold(t)(_ % 2 == 0) shouldBe Branch(Branch(Leaf(false), Leaf(true)), Leaf(false))