Laziness and Infinite Data Structures

September 16, 2016

Khái niệm về lazy evaluation không tồn tại trực tiếp trên các non-functional programming nhưng tuy nhiên nó khá dễ dàng để nắm bắt. Hãy nghĩ về một dạng if-statement như sau :


def expensiveOperation() = ???
    val a = "foo"
    val b = "foo"       
if ((a == b) || expensiveOperation()) true else false

Ở phần lớn các ngôn ngữ lập trình cơ bản nhất, toán tử || đánh giá đối số (a == b) và hàm expensiveOperation() có ý nghĩa rằng nó sẽ không được thực hiện nếu (a==b) là true. Nó chỉ được thực hiện nếu (a==b) trả về false. Lazy evaluation trong scala cho phép bạn định nghĩa các hành vi tương tự nhau trong nhiều hoàn cảnh khác nhau.

Chúng ta có thể định nghĩa các biến của chúng ta thành lazy, có nghĩa là chúng sẽ không được thực thi cho đến khi chúng được sử dụng lần đầu tiên, trái ngược với các biến bình thường, chúng sẽ được thực thi ngay khi định nghĩa. Mỗi khi có một lazy variables được thực thi, gía trị của chúng sẽ được lưu trữ lại.


case class Order(name: String, price: Int)

case class User(id: Int, orders: Seq[Order]) {
  lazy val cheapOrders: Seq[Order] = orders.filter(_.price <= 50)
}

Trong ví dụ này, chúng ta có một case class cho lớp User abstraction, chứa một danh sách các đơn hàng. cheapOrders và expensiveOrders sẽ không được nhận giá trị trong suốt quá trình khởi tạo case class , không giống như val bình thường hay làm. Chúng chỉ được thực thi khi chúng ta gọi chúng trực tiếp. Tại sao không sử dụng một phương thức ? Vấn đề ở đây là nếu chúng ta có một tính toán phức tạp, nếu gọi một phương thức nhiều lần sẽ thực thi chúng nhiều lần. Lazy variables sẽ được lưu trữ khi chúng được gọi, như thế thì sẽ tối ưu rất hiệu quả trong một số trường hợp.

Một ví dụ về việc delayed execution là by-name function parameters. Thông thường, function parameters sẽ được thực thi khi chúng được pass. Tuy nhiên, trong một số trường hợp chúng ta không muốn thực thi function parameters trước khi thực sự cần thiết. (suy nghĩ về những tính toán phức tạp một lần nữa)


trait Person
case class User() extends Person
case class Admin() extends Person

def loadAdminsOrUsers(needAdmins: => Boolean, loadAdmins: => Seq[Admin],
                      loadUsers: => Seq[User]): Seq[Person] = {
  if (needAdmins) loadAdmins
  else loadUsers
}

Ở đây chúng ta có 3 tham số by-name functions, với những logic phức tạp. Chúng ta không muốn tất cả chúng được thực thi, vậy nên chúng ta không thể pass chúng như giá trị, điều mà chúng ta vẫn thường làm. Ký tự => có nghĩa rằng chúng ta đang tự pass hàm như những giá trị trả về (return values) của nó. Giờ, chúng ta có thể gọi nó bất cứ khi nào chúng ta cần.

Cả laziness và by-name parameters đều được sử dụng để thừa kế một trong những cấu trúc mạnh mẽ nhất trong functional programming : infinite data structures. Trong những ngôn ngữ lập trình cơ bản, tất cả các cấu trúc dữ liệu đều có một kích thước xác định, hoạt động tốt trong hầu hết các trường hợp, nhưng đôi khi chúng ta không thể biết được kích thước của nó trước khi nó kết thúc. Với delayed execution, điều đó có thể trở thành khả thi để định nghĩa cấu trúc dữ liệu ở dạng tổng tổng quát mà không "filling them up" với dữ liệu, trước khi chúng ta thực sự phải làm với cấu trúc dữ liệu đó.

Nghe có vẻ rất tuyệt vời phải không nhỉ 😀 Nhưng thực sự thì nó sẽ làm việc ra sao ? Hãy sử dụng một infinite data structures (cấu trúc dữ liệu vô hạn), được gọi là stream, để tạo ra các số nguyên tố. Trong Java để tạo ra các số nguyên tố, chúng ta sẽ viết một số function để tạo ra các số nguyên tố đến một số giới hạn. Sau đó chúng ta có thể gọi function này để tạo ra một danh sách các số nguyên tố N và đặt nó ở một nơi nào đó. Nếu chúng ta cần một danh sách số nguyên tố khác nhau ở các nơi khác nhau, chúng ta lại phải generate lại danh sách đó từ đầu. Ở trong Scala, chúng ta sẽ làm điều đó như thế này :


val primes: Stream[Int] = {
  def generatePrimes (s: Stream[Int]): Stream[Int] =
    s.head #:: generatePrimes(s.tail filter (_ % s.head != 0))
    
  generatePrimes(Stream.from(2))
}

Cú pháp không có nhiều ý nghĩa với chúng ta và nó cũng không quan trọng lúc này. Điều quan trọng là chúng ta có thể làm gì với cấu trúc dữ liệu này. Ví dụ, chúng ta muốn lấy 5 số nguyên tố đầu tiên mà lớn hơn 100. Đó là một phần với stream:


primes.filter(_ > 100).take(5).toList

Kết quả của dòng này là sẽ trả về một List(101,103,107,109,113) như mong đợi. Điều thú vị ở đây là có thể đặt primes ở bất cứ nơi nào trong function của chúng ta, mà nó vẫn chưa được thực thi. Chúng ta cũng có thể đặt bất cứ action ở trên đầu của chúng (như filter ở ví dụ trên), và nó cũng sẽ không tạo ra bất cứ result nào cho đến khi chúng ta cần chúng. Còn rất nhiều điều thú vị ở Scala Functional Programming, chúng ta có thể tìm kiếm một vấn đề thú vị khác trong blog sau.

Refferences :
http://www.vasinov.com/blog/16-months-of-functional-programming/#toc-laziness

Post Views: 63