เราจะมาเจาะประเด็น

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 as Cons("a", Cons("b", Nil))

singly linked list data structure in memory

  Cons.       Cons.
["a"][*-]-> ["b"][*-]-> Nil
Head|Tail   Head|Tail

---

Pattern Matching

เราจะใช่ 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)

---

Efficiency ของ Data Sharing

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)?

1. l คือ List(1,2,3) หรือก็คือ Cons(1, Cons(2, Cons(3, Nil)))
2. n คือ 1
3. l เข้า case else, matching กับ Cons(_,t) ซึ่ง t คือ Cons(2, Cons(3, Nil)) และ _ คือ 1 แต่เราไม่ได้ใช้ในที่นี้
4. เข้า function drop(t, n-1) โดยที่ t คือ Cons(2, Cons(3, Nil)), และ n คือ 1
   • จะสังเกตุได้ว่า Cons(2, Cons(3, Nil)) เป็น data ที่ถูก sharing จากค่าเดิม เพื่อเอาเข้าไปใน argument ของ drop() โดยที่ไม่ได้แก้ค่า l เลย จึงเป็น immutable
5. จากข้อ 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) เป็น จริง

---

Recursion over lists and generalizing to higher-order functions

จากตรงนี้

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 แทน