Tạo các dãy vô hạn (Infinite Sequences) với Ruby

Các ngôn ngữ lập trình hàm (functional languages) như Clojure có tính năng là dãy - sequences. Sqequences có thể biến đổi các thuật toán thành các cấu trúc dữ liệu. Ta có thể gọi hàm trên dữ liệu được tạo ra bởi các thuật toán và có thể coi chúng là các collection kể cả khi độ dài của nó là vô tận.

Thư viện chuẩn của Ruby không có class hoặc module nào để thể hiện sequence nhưng nó cung cấp module Enumerable giúp ta có thể viết một sequence. Dân Ruby thường biết tới Enumerable thông qua các phương thức của Array như map hoặc select. Một Array như là [1, 2, 3, 4] thường được coi là một sequence hữu hạn và được tạo sẵn; chúng đã được khởi tạo với tất cả các thành viên mà ta có thể dùng các method để chạy trên chúng. Với Enumerable ta có thể thêm vào các chức năng để biến nó thành một sequence.

Enumerable Fibonacci

Trước tiên, ta sẽ xem xet một ví dụ với một chuỗi (sequence) vô hạn là Fibonacci. Ta có thể viết một hàm mà khởi tạo n số Fibonacci đầu tiên như sau:

def eager_fibonacci(n)
  a = b = 1
  result = []

  loop do
    break if result.size >= n

    result << a
    a, b = b, a + b
  end

  result
end

Đơn giản đúng không, tuy nhiên ta có thể nâng cấp nó lên đôi chút. Thay vì trả về một Array với các phần tử đã được tính toán sẵn, ta có thể trả về một Enumerator. Sau đó với Enumerator này ta có thể khởi tạo các phần tử một cách lần lượt, gọi đến đâu tạo đến đó.

def fibonacci
  Enumerator.new do |y|
    a = b = 1

    loop do
      y << a
      a, b = b, a + b
    end
  end
end

Enumerator đơn giản chỉ là một đối tượng Enumerable được dùng để duyệt các collection. Enumerable là một module được include trong rất nhiều class như Array hay Hash để cung cấp tính năng duyệt phần tử cho các object của các class này. Hàm khởi tạo của Enumerator nhận vào một block và đóng vai trò là một template cho một thuật toán liệt kê (thuật toán tạo ra các dãy số). Block này nhận vào một tham số, y, là một instance của class Enumerator::Yielder. Nó sẽ làm nhiệm vụ là đẩy ra giá trị ra cho các hàm gọi của Enumerable. Nói đơn giản là ta có thể coi một Enumerator tương tự như một Array; có thể duyệt từng phần tử và gọi các hàm trên các phần tử đấy.

Để lấy 10 phần tử đầu tiên của dãy Fibonacci được implement bằng Enumerator, ta dùng như sau:

fibonacci.take(10)

#=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

10 phần tử đầu tiên của dãy Fibonacci sẽ được tính toán và trả ra một mảng từ đó ta có thể duyệt nó như bình thường:

fibonacci.take(10).each{|i| puts i}

Ta có thể kết hợp sử dụng hàm lazy của Enumerator để tránh việc phải tính toán toàn trước toàn bộ các phần tử muốn lấy ra. Thay vào đó, các phần tử sẽ được khởi tạo lần lượt và ta có thể tính toán trên từng phần tử một. Sau đây là ví dụ về việc lấy 10 phần tử chẵn và lẻ đầu tiên của dãy Fibonacci:

fibonacci.lazy.select(&:even?).first(10)
#=> [2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040]

fibonacci.lazy.select(&:odd?).first(10)
#=> [1, 1, 3, 5, 13, 21, 55, 89, 233, 377]

Nếu muốn xem phải mất bao nhiêu vòng lặp để có thể lấy được 10 phần tử chẵn hoặc lẻ đầu tiên của dãy, hãy thêm hàm with_index của Enumerator:

fibonacci.lazy.with_index.select { |n, i| n.odd? }.first(10)
#=> [[1, 0], [1, 1], [3, 3], [5, 4], [13, 6], [21, 7], [55, 9], [89, 10], [233, 12], [377, 13]]

fibonacci.lazy.with_index.select { |n, i| n.even? }.first(10)
#=> [[2, 2], [8, 5], [34, 8], [144, 11], [610, 14], [2584, 17], [10946, 20], [46368, 23], [196418, 26], [832040, 29]]

Nhìn vào đây, ta thấy là để lấy được 10 phần tử lẻ đầu tiên của dãy Fibonacci thì phải mất 13 vòng lặp và 29 vòng lặp là số lượng để lấy ra được 10 phần tử chẵn đầu tiên của dãy Fibonacci. Nếu ta sử dụng cách thông thường để tạo dãy Fibonacci để làm điều này thì sẽ rất khó vì ta cần phải truyền vào số lượng phần tử muốn lấy ra từ dãy Fibonacci trước khi thực hiện thuật toán.

Một ví dụ nữa là tạo một dãy các số giai thừa với Enumerator:

factorial = Enumerator.new do |y|
  a = b = 1
  loop do
    y << a
    b = b + 1
    a = a * b
  end
end

factorial.take 5

#=> [1, 2, 6, 24, 120

Sequence Function

Clojure có một số hàm cho phép tạo ra các dãy sequences từ các hàm khác. Hãy xem ví dụ với hàm repeatedly. Hàm này sẽ gọi một function liên tục và đưa ra kết quả như một sequence. Để lấy ra một chuỗi sequence gồm 5 phần tử bất kỳ từ 0 đến 100, ta làm như sau:

(take 5 (repeatedly #(rand-int 100)))

Đoạn code trên chỉ đơn giản là lấy 5 kết quả đầu tiên của hàm repeatedly trong đó goi một hàm lấy một giá trị bất kỳ từ 0 -> 100.

Ta cũng có thể sử dụng Enumerator của Ruby để thực hiện điều tương tự. Ta sẽ tạo một phiên bản repeatedly riêng trong Ruby. Hàm này sẽ nhận vào một block và chạy nó một cách liên tục. Ta sẽ implement theo cách đơn giản nhất là sử dụng loop:

def repeatedly_foo(n, &block)
  result = []

  loop do
    break if result.size >= n

    result << block.call
  end

  result
end

Với cách implement này, block luôn bị gọi n lần và trả ra kết quả trước rồi từ đó ta mới có thể sử dụng kết quả này để thực hiện tính toán tiếp.

Bây giờ, ta sẽ bao đoạn loop với một Enumerator và ta có thể coi kết quả trả về như là một sequence:

def repeatedly(&block)
  Enumerator.new do |y|
    loop do
      y << block.call # "yield" the result to the Enumerator::Yielder
    end
  end
end

Bây giờ ta đã có một sequence mà có thể chain với các hàm Enumerator khác. Bây giờ ta đã có một phiên bản repeatedly tương đương với Clojure:

repeatedly { rand(100) }.take 5

#=> [54, 43, 93, 5, 87] # Kết quả này sẽ khác nhau với mỗi lần chạy.

Kết luận

Ta có thể áp dụng kỹ thuật sequence này vào các ứng dụng mà làm việc với các tập dữ liệu có độ dài không biết trước được như kết quả từ một truy vấn tìm kiếm, dữ liệu phân trang từ các API, dữ liệu từ các web crawl...

Tham khảo

Infinite Sequences in Ruby