-
Notifications
You must be signed in to change notification settings - Fork 0
5. Defining functional data structures & Pattern matching
เราจะมาเจาะประเด็น
functional data structures are by definition immutable
เราจะมาพิสูจน์กันว่าทำได้อย่างไร ซึ่งมันไม่ใช่การ copy data ไปเรื่อยๆ แต่มีวิธีการที่เรียกว่า "Data Sharing"
Singly Linked List Example
sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
object List {
def sum(ints: List[Int]): Int = ints match {
case Nil => 0
case Cons(x,xs) => x + sum(xs)
}
def product(ds: List[Double]): Double = ds match {
case Nil => 1.0
case Cons(0.0, _) => 0.0
case Cons(x,xs) => x * product(xs)
}
def apply[A](as: A*): List[A] =
if (as.isEmpty)
Nil
else
Cons(as.head, apply(as.tail: _*))
}
Cons. mean Constructor หรือ รูปแบบโครงสร้าง
List("a", "b")
the same asCons("a", Cons("b", Nil))
singly linked list data structure in memory
Cons. Cons.
["a"][*-]-> ["b"][*-]-> Nil
Head|Tail Head|Tail
เราจะใช่ pattern matching สำหรับเพื่อวิเคราะห์ Code ด้านบน เพื่อความเข้าใจง่าย
คือ switch-case statement แต่พิเศษตรงที่สามารถ match กับ pattern ที่รับเข้ามาได้
> List(1,2,3) match { case _ => 42 } results in 42
ไม่ว่าอะไรเข้ามาก็ return 42
> List(1,2,3) match { case Cons(h,_) => h } results in 1
List(1,2,3) คือ Cons(1, Cons(2, Cons(3, Nil)))
match กับ pattern Cons(h,_) => h
ดังนั้น (h คือ 1) และ (_ คือ Cons(2, Cons(3, Nil)))
> List(1,2,3) match { case Cons(_,t) => t } results in List(2,3)
List(1,2,3) คือ Cons(1, Cons(2, Cons(3, Nil)))
match กับ pattern Cons(_,t) => t
ดังนั้น (t คือ List(2,3)) และ (_ คือ 1)
def drop[A](l: List[A], n: Int): List[A] =
if (n <= 0) l
else l match {
case Nil => Nil
case Cons(_, t) => drop(t, n - 1)
}
drop(List(1, 2, 3), 1) shouldBe List(2,3)
drop(List(1, 2, 3), 0) shouldBe List(1, 2, 3)
drop(List("a", "b"), 2) shouldBe List()
drop(List(1, 2), 3) shouldBe List()
drop(Nil, 1) shouldBe Nil
เราจะมาอธิบาย Data sharing ด้วย code นี้กัน Data Sharing ไม่ใช่การ copy data ทั้งก้อนเพื่อเอาไปทำอะไรที่เราต้องการ มันสุ่มเสี่ยงที่จะเกิด mutable data (data ที่เปลี่ยนแปลงค่าได้) ในวิธีการของ function drop() เราข้างบนนี้เป็น immutable data ก็คือเราไม่ได้มีการเปลี่ยนแปลงค่าอะไรจาก List เดิมเลย แต่เรา drop ค่าด้วยการ return ค่าใหม่ ขึ้นมาให้ด้วยการใช้ list เดิม ทำ recursive ไปเรื่อยๆ จนกว่า เงื่อนไข function นั้นจะสำเร็จ
// เราจะไล่ code นีก้น
drop(List(1, 2, 3), 1) shouldBe List(2,3)?
- l คือ List(1,2,3) หรือก็คือ Cons(1, Cons(2, Cons(3, Nil)))
- n คือ 1
- l เข้า case else, matching กับ Cons(_,t) ซึ่ง t คือ Cons(2, Cons(3, Nil)) และ _ คือ 1 แต่เราไม่ได้ใช้ในที่นี้
- เข้า function drop(t, n-1) โดยที่ t คือ Cons(2, Cons(3, Nil)), และ n คือ 1
-
จะสังเกตุได้ว่า Cons(2, Cons(3, Nil)) เป็น data ที่ถูก sharing จากค่าเดิม เพื่อเอาเข้าไปใน argument ของ drop()
โดยที่ไม่ได้แก้ค่า l เลย จึงเป็น immutable
-
- จากข้อ 3 นั้น n กลายเป็น 0 จึงเข้า case if ทำให้ return l ล่าสุดขึ้นไปก็คือ Cons(2, Cons(3, Nil)) หรือ List(2, 3)
ดังนั้น drop(List(1, 2, 3), 1) shouldBe List(2,3) เป็น จริง
จากตรงนี้
def sum(ints: List[Int]): Int = ints match {
case Nil => 0
case Cons(x,xs) => x + sum(xs)
}
def product(ds: List[Double]): Double = ds match {
case Nil => 1.0
case Cons(x, xs) => x * product(xs)
}
สังเกตุได้ว่ามันเป็น pattern เดิมๆที่ เอาค่าใน list ทีละตัวมา + กัน หรือ * กัน จากซ้ายไปขวา เราสามารถ improve ได้ โดยใช้ HOF เพื่อแยก function การทำงาน(+, *) ออกมา
def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
as match {
case Nil => z
case Cons(x, xs) => f(x, foldRight(xs, z)(f))
}
เพื่อความเข้าใจ ว่า foldRight ทำอะไร
foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0)((x,y) => x + y)
1 + foldRight(Cons(2, Cons(3, Nil)), 0)((x,y) => x + y)
1 + (2 + foldRight(Cons(3, Nil), 0)((x,y) => x + y))
1 + (2 + (3 + (foldRight(Nil, 0)((x,y) => x + y))))
1 + (2 + (3 + (0)))
6
จะเห็นได้ว่าเราแยกส่วน การ + และ การ * ได้ดังนี้
def sum2(ns: List[Int]) = foldRight(ns, 0)((x,y) => x + y)
def product2(ns: List[Double]) = foldRight(ns, 1.0)(_ * _)
ดังนั้นเวลา pattern การใส่ data แต่ละตัวไปใช้บ่อยๆ แต่มี function จัดการแตกต่างกันไป ให้ใช้ HOF แทน
The Greatest come from Diversity. - GaoEy