Functional Programming’s Toolkit: Fold

I- Giới thiệu Functional Programming

Functional Programming (lập trình hàm – FP) nhắm đến tính kết hợp (composability) các hàm (function) để tối đa hóa khả năng tái sử dụng (reusability) trong chương trình. Điểm khác biệt lớn nhất của lập trình hàm khác với lập trình thủ tục thuần túy (procedural programming) nằm ở điểm thay vì thực hiện tuần tự theo từng bước với các biến để lưu trạng thái thì FP chú trọng đến thực thi luồng chương trình thông qua việc kết hợp các hàm bậc cao (high order function). Đối với các ngôn ngữ có hỗ trợ high order function thì các hàm cũng có thể được truyền như là các tham số hoặc là kết quả trả về. Do đó các thuật toán trong FP có thể được diễn tả một cách ngắn gọn và trong sáng.

Hầu hết các ngôn ngữ lập trình hỗ trợ FP đều có một bộ ‘công cụ’ những hàm tận dụng High order function như map, fold, filter v.v… Mỗi hàm này đặc trưng cho một pattern hay gặp trong lập trình, ví dụ như map biến đổi từng thành viên nhưng vẫn giữ nguyên cấu trúc của một kiểu dữ liệu, filter dùng để tạo ra 1 cấu trúc mới chứa những phần tử đáp ứng một tiêu chuẩn đặt ra. Trong những hàm này thì map và filter được hỗ trợ khá rộng rãi trong hầu hết các ngôn ngữ lập trình, còn fold thì ít được biết đến hơn. Do vậy bài viết này sẽ viết về fold trước thay vì về map như các series về functional programming khác.

II- Định nghĩa của Fold

Như đã nói ở trên, mỗi hàm trong bộ ‘công cụ’ đều đặc trưng cho một pattern trong lập trình, vậy với fold thì problem pattern là gì? Fold thường được dùng để tính toán một giá trị bằng cách kết hợp các phần tử của một cấu trúc (thường là một List – danh sách). Một ví dụ đơn giản nhất của fold là như sau:

 (1 to 10).fold(0)(_ + _)
 res0: Int = 55

Câu lệnh trên tương ứng với biểu thức sau:

 0 + (1 + (2 + (3 +....... + (9 + (10))))))))))

Trong đó giá trị 0 là giá trị ban đầu sẽ được cộng với từng giá trị từ 1 đến 10 (có thể tưởng tượng giống như 1 mẩu giấy dài được ‘gấp’ lại liên tục).

Hàm fold được định nghĩa trong trait TraversableOnce của Scala như sau (TraversableOnce là trait chứa những method chung cho Traversable và Iterator):

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)
def foldLeft[B](z: B)(op: (B, A) => B): B = {
  var result = z
  this foreach (x => result = op(result, x))
  result
}

Vậy implementation mặc định của fold là hàm foldLeft (sự khác biệt giữa fold, foldLeft và foldRight sẽ được trình bày ở phần sau). Hàm foldLeft lấy giá trị của z làm kết quả ban đầu và thực hiện op với result và x (từ trong Traversable) cho hết mọi giá trị trong Traversable.

III- foldLeft & foldRight & fold

Cũng trong TraversableOnce ta có thể thấy foldRight được định nghĩa theo foldLeft như sau:

def foldRight[B](z: B)(op: (A, B) => B): B =
  reversed.foldLeft(z)((x, y) => op(y, x))

Vậy foldRight sẽ đảo ngược cấu trúc lại và gọi op với tham số cũng được đổi chỗ. Trực quan thì có thể hiểu foldLeft và foldRight như sau:

Vậy sự khác biệt của foldLeft và foldRight trong khi sử dụng là gì? foldLeft thường được sử dụng với các toán tử có tính liên kết trái (left associate) còn foldRight dùng với liên kết phải. Với các toán tử như +, * có tính giao hoán thì trái hay phải cũng như nhau do vậy foldLeft hay foldRight cũng như nhau. Còn với các toán tử khác như – hay / thì chúng có tính liên kết trái do vậy phải dùng foldLeft:

 scala> (1 to 10).foldLeft(0)(_ - _)  // Đúng
 res10: Int = -55

scala> (1 to 10).foldRight(0)(_ - _) // Sai
 res11: Int = -5

Ngoài ra, đối với một số cấu trúc dữ liệu, đặc biệt là các cấu trúc có tính ‘lười’ – laziness như Stream, foldLeft cũng có thể được viết tối ưu hơn:

 @tailrec
   override final def foldLeft[B](z: B)(op: (B, A) => B): B = {
   if (this.isEmpty) z
   else tail.foldLeft(op(z, head))(op)
 }

Vậy foldLeft trong Stream được tối ưu dùng đệ quy đuôi (tail call recursion) nhằm hạn chế việc phình stack do gọi hàm liên tục.

Nếu nhìn theo định nghĩa của foldLeft và foldRight ở trên, bạn có thể nghĩ rằng foldLeft sẽ được dùng nhiều hơn do chạy nhanh hơn (không phải tạo một cấu trúc List tạm để đảo ngược thứ tự) và hầu hết các toán tử có tính liên kết trái. Điều này đúng trong hầu hết các trường hợp với Scala, tuy nhiên không hoàn toàn đúng với fold nói chung trong các ngôn ngữ lập trình. Đối với ngôn ngữ Haskell có lượng giá lười (lazy evaluation), foldRight không hề chậm hơn so với foldLeft và thậm chí còn có ưu điểm là có thể hoạt động với infinitive list.

Vậy còn fold thì sao? fold được định nghĩa theo foldLeft do vậy chỗ nào dùng fold là có thể thay bằng foldLeft được. Tuy nhiên fold vẫn có ưu điểm riêng, nhìn vào kiểu của fold:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1
 def foldLeft[B](z: B)(op: (B, A) => B): B

ta có thể thấy fold có type constraint chặt chẽ hơn so với foldLeft, ngoài ra Scala định nghĩa fold có thể được thực hiện theo bất kỳ thứ tự nào, do vậy các cấu trúc dữ liệu có thể tự viết phiên bản tính toán song song của fold để tăng tốc độ xử lý.

IV- Sử dụng fold

Với định nghĩa như trên, ta thấy rằng khi nào ta cần lấy 1 giá trị dựa trên toàn bộ các phần tử của 1 cấu trúc. Một số ví dụ là các hàm như sum, min, max v.v.. và đúng như vậy, TraversableOnce định nghĩa các hàm này dựa trên fold:

 def aggregate[B](z: =>B)(seqop: (B, A) => B, combop: (B, B) => B): B = foldLeft(z)(seqop)
 def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)
 def product[B >: A](implicit num: Numeric[B]): B = foldLeft(num.one)(num.times)

các hàm cơ bản như map, filter cũng có thể được định nghĩa bằng fold. Không chỉ với Seq fold còn có thể được sử dụng với các cấu trúc khác như trie hay tree, miễn là chúng cung cấp phương thức `foreach` để có thể duyệt trên toàn bộ các phần tử của cấu trúc. Thậm chí cả Option type trong Scala cũng cung cấp fold:

@inline final def fold[B](ifEmpty: => B)(f: A => B): B =
 if (isEmpty) ifEmpty else f(this.get)

Do Option chỉ chứa một giá trị nên trong trường hợp này fold tương đương với 1 lệnh `if` cho hai trường hợp chứa None hoặc Some(A).

Ngoài các hàm đơn giản trên, fold còn được dùng trong rất nhiều các cấu trúc và bài toán phức tạp khác, chẳng hạn như parsing (http://okmij.org/ftp/papers/XML-parsing.ps.gz – A better XML parser through functional programming). Vậy khi gặp một bài toán cần tạo ra một giá trị từ một cấu trúc generics, bạn hãy thử tìm cách sử dụng fold xem, có thể sẽ tìm ra được lời giải ngăn gọn hơn rất nhiều.