Chương 5: Đệ quy

Trở về Mục lục cuốn sách

Chào đệ quy!

Ta có nhắc đến đệ quy ở chương trước. Trong chương này, chúng ta sẽ xem xét đệ quy kĩ hơn, về lý do tại sao nó quan trọng đối với Haskell và bằng cách nào ta có thể nhanh chóng giải quyết được vấn đề một cách tinh tế bằng cách nghĩ kiểu đệ quy.

SOVIET RUSSIA

Nếu bạn vẫn chưa biết đệ quy là gì, hãy đọc câu này. Ha ha! Đùa một chút thôi! Thực ra đệ quy là một cách định nghĩa hàm trong đó hàm được á dụng bên trong chính định nghĩa của nó. Nhiều định nghĩa trong toán học được cho dưới dạng đệ quy. Chẳng hạn, dãy Fibonacci được định nghĩa một cách đệ quy. Đầu tiên, ta định nghĩa hai số Fibonacci đầu tiên không bằng đệ quy. Ta nói F(0) = 0F(1) = 1, nghĩa là các số Fibonacci thứ 0 và thứ 1 lần lượt bằng 0 và 1. Sau đó ta nói rằng với mọi số tự nhiên khác thì số Fibonacci sẽ bằng tổng của hai số Fibonacci liền trước. Vì vậy F(n) = F(n-1) + F(n-2). Bằng cách này, F(3) bằng F(2) + F(1), tức là bằng (F(1) + F(0)) + F(1). Đến lúc này, vì chỉ còn các số Fibonacci đã định nghĩa sẵn theo cách không đệ quy, ta có thể yên tâm nói rằng F(3) bằng 2. Việc có một hoặc hai phần tử trong lời định nghĩa không đệ quy (like F(0)F(1) trong trường hợp này) còn được gọi là điều kiện biên và nó rất quan trọng nếu bạn muốn hàm đệ quy kết thúc được. Nếu không định nghĩa F(0)F(1) theo cách không đệ quy, thì ta sẽ không bao giờ nhận được đáp số với bất kì số nào vì đến số 0 thì máy sẽ tiếp tục tính tới những số âm. Đột nhiên, bạn sẽ thấy F(-2000) bằng F(-2001) + F(-2002) và trước mắt chưa thấy hồi kết thúc!

Đệ quy rất quan trọng trong Haskell vì khác với những ngôn ngữ mệnh lệnh, bạn tính toán trong Haskell bằng cách định nghĩa đôi tượng là gì chứ không phải khai báo bằng cách nào để đạt được nó. Đây là lý do tại sao không có vòng lặp while hoặc for trong Haskell, và thay vào đó nhiều lúc ta phải dùng đệ quy để khai báo một thứ là gì.

Maximum tuyệt vời

Hàm maximum nhận vào một danh sách các đối tượng có thể sắp xếp (chẳng hạn các thực thể của lớp Ord) rồi trả lại đối tượng lớn nhất trong số đó. Hãy nghĩ cách bạn lập trình hàm này trên phương diện mệnh lệnh. Có thể bạn sẽ tạo một biến để chứa giá trị lớn nhất hiện đã tìm được trong quá trình lặp qua những phần tử của danh sách và nếu có một phần tử số nguyên lớn hơn giá trị lớn nhất hiện có, bạn sẽ thay thế nó bằng phần tử mới ấy. Phù! Thật quá nhiều từ ngữ để miêu tả một thuật toán đơn giản như vậy!

Bây giờ hãy xem cách ta định nghĩa nó bằng đệ quy. Trước hết ta có thể lập một điều kiện biên và nói rằng giá trị lớn nhất của danh sách một phần tử thì chính bằng phần tử duy nhất đó. Tiếp theo ta có thể nói rằng giá trị lớn nhất của một danh sách dài hơn là phần tử đầu nếu như phần tử đầu này lớn hơn giá trị lớn nhất của đoạn đuôi danh sách. Như vậy đó! Bây giờ ta hãy thực hiện lập trình bằng Haskell.

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) 
    | x > maxTail = x
    | otherwise = maxTail
    where maxTail = maximum' xs

Như bạn có thể thấy, khớp mẫu rất hợp với đệ quy! Đa số các ngôn ngữ mệnh lệnh đều không có khớp mẫu vì vậy bạn phải viết rất nhiều câu lệnh if else để kiểm tra các điều kiện biên. Ở đây, ta chỉ việc đặt các điều kiện dưới dạng các mẫu. Như vậy điều kiện thứ nhất phát biểu rằng nếu danh sách là rỗng, chương trình sẽ đổ vỡ! Điều này có lý vì phần tử lớn nhất của một danh sách rỗng thì bằng bao nhiêu? Tôi không biết. Mẫu thứ hai cũng đặt ra một điều kiejn biên. Nó nói rằng nếu danh sách chỉ có một phần tử, thì hãy trả lại phần tử duy nhất đó.

Bây giờ mẫu thứ ba là nơi mọi chuyện thực sự diễn ra. Ta dùng khớp mẫu để tách một danh sách thành một phần tử đầu và phần đuôi. Đây là cách viết thường dùng trong đệ quy với danh sách, vì vậy bạn nên sử dụng thuần thục nó. Ta dùng một cách gắn where để định nghĩa maxTail là phần tử lớn nhất của phần còn lại danh sách. Sau đó ta kiểm tra xem liệu phần tử đầu có lớn hơn phần còn lại của danh sách hay không. Nếu có, ta trả lại phần tử đầu. Nếu không, ta trả lại phần tử lớn nhất của phần còn lại danh sách.

Hãy lấy một ví dụ danh sách các số rồi kiểm tra xem liệu cách làm này có đúng không: [2,5,1]. Nếu ta gọi maximum' với danh sách đó, hai mẫu đầu tiên sẽ không khớp. Mẫu thứ ba sẽ khớp và danh sách bị chia cắt thành 2[5,1]. Vế where muốn biết phần tử lớn nhất của [5,1], vì vậy ta sẽ đi theo con đường này. Một lần nữa, nó khớp với mẫu thứ ba và [5,1] bị chia cắt thành 5[1]. Và ở đây, vế where lại muốn biết số lớn nhất trong [1]. Vì đó là điều kiện biên rồi, nên nó trả lại 1. Rồi cũng xong! Bây giờ đi ngược lên một bậc, so sánh 5 với số lớn nhất trong [1] (chính là 1), rõ ràng ta được 5. Như vậy bây giờ ta biết rằng phần tử của [5,1]5. Vì vậy ta lại đi ngược lên một bậc, ở đó ta có 2[5,1]. So sánh 2 với số lớn nhất trong [5,1], hay 5, ta chọn 5.

Để viết hàm này thậm chí còn có cách rõ ràng hơn, đó là dùng max. Hẳn bạn còn nhớ, max là một hàm nhận vào hai số rồi trả lại số lớn hơn giữa chúng. Sau đây là cách viết lại maximum' bằng cách dùng max:

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)

Thật là thanh lịch! Nói ngắn gọn, phần tử lớn nhất trong danh sách thì bằng phần tử lớn hơn giữa phần tử đầu và phần tử lớn nhất trong phần còn lại của danh sách.

max

Một vài hàm đệ quy khác

Bây giờ khi ta đã biết cách nghĩ đệ quy nói chung, hãy cùng thực hiện lập ra một số hàm khác bằng cách đệ quy. Đầu tiên, ta sẽ lập hàm replicate. replicate nhận vào một Int và một phần tử nào đó rồi trả lại một danh sách gồm nhiều lần lặp lại chính phần tử đó. Chẳng hạn, replicate 3 5 trả lại [5,5,5]. Hãy cùng nghĩa về điều kiện biên. Suy đoán của tôi là điều kiện biên là số 0 hoặc nhỏ hơn. Nếu ta thử lặp lại thứ gì đó 0 lần, thì hàm cần trả lại một danh sách rỗng. Với các số âm cũng vậy, vì chúng thật sự không có nghĩa gì.

replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
    | n <= 0    = []
    | otherwise = x:replicate' (n-1) x

Ở đây ta đã dùng chốt canh thay vì mẫu vì cần kiểm tra điều kiện boole. Nếu n nhỏ hơn hoặc bằng 0, thì trả lại danh sách rỗng. Trường hợp ngược lại thì trả về một danh sách có x là phần tử thứ nhất cùng phần đuôi danh sách gồm x lặp lại n-1 lần. Cuối cùng, phần (n-1) sẽ khiến cho hàm được viết đạt tới điều kiện biên.

Lưu ý: Num không phải là một lớp con của Ord. Điều này nghĩa là những thứ nạo nên con số không nhất thiết phải có thứ tự nào đó. Đó là lý do mà ta phải chỉ định cả hai ràng buộc về lớp NumOrd khi làm phép cộng hoặc trừ, và cả phép so sánh.

Tiếp theo, ta sẽ tự lập hàm take. Hàm này lấy ra một số nhất định các phần tử trong một danh sách. Chẳng hạn, take 3 [5,4,3,2,1] sẽ trả lại [5,4,3]. Nếu ta thử lấy ra 0, hoặc ít hơn, các phần tử từ danh sách. Ta sẽ lấy được một danh sách rỗng. Mặt khác, nếu thử lấy bất kì thứ gì từ một danh sách rỗng, ta cũng chỉ lấy được danh sách rỗng. Lưu ý rằng có hai điều kiện biên như vậy. Và ta hãy viết cụ thể xem nào:

take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
    | n <= 0   = []
take' _ []     = []
take' n (x:xs) = x : take' (n-1) xs

painter

Mẫu thứ nhất chỉ định rằng nếu ta thử lấy 0 hoặc một số âm ccs phần tử, thì ta nhận được một danh sách rỗng. Lưu ý rằng ta dùng _ để khớp với danh sách vì ta thật sự không quan tâm đến nó là gì trong trường hợp này. Cũng lưu ý rằng ta dùng một chốt canh, nhưng không có phần otherwise. Điều đó nghĩa là nếu hóa ra n lớn hơn 0 thì giá trị cần khớp sẽ rơi xuống mẫu tiếp theo. Mẫu thứ hai yêu cầu rằng nếu ta định lấy bất kì thứ gì từ một danh sách rỗng, ta sẽ chỉ nhận được danh sách rỗng. Mẫu thứ ba chia danh sách thành một phần tử đầu và một đoạn đuôi. Sau đó mã lệnh nói rằng lấy n phần tử từ danh sách thì được một danh sách có phần tử đầu là x tiếp theo là một danh sách được lấy từ n-1 phần tử ở phần đuôi danh sách gốc. Hãy kiếm một mảnh giấy để thử ghi ra xem việc tiến hành lượng giá sẽ ra sao nếu ta thử lấy 3 phần tử từ danh sách [4,3,2,1].

reverse chỉ đơn giản là đảo ngược một danh sách. Hãy hình dung ra điều kiện biên. Là gì vậy nhỉ? Cố nghĩ tiếp đi nào… đó là danh sách rỗng! Một danh sách rỗng đảo ngược thì bằng chính danh sách rỗng đó. Được rồi. Thế phần còn lại? Ồ, bạn có thể nói vậy khi đã chia danh sách thành một phần tử đầu và đoạn đuôi, danh sách đảo ngược sẽ bằng phần đuôi đảo ngược, gắn vào sau nó là phần tử đầu của danh sách gốc.

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

Xong rồi đấy!

Vì Haskell cho phép dùng danh sách vô hạn nên phép đệ quy của ta không nhất thiết phải có một điều kiện biên. Nhưng nếu không có, nó sẽ không ngừng tuồn ra giá trị, hoặc tạo ra một cấu trúc dữ liệu vô hạn, như một danh sách vô hạn. Dù vậy, điều hay có ở danh sách vô hạn là ta có thể cắt chúng ở vị trí ta muốn. repeat nhận vào một phần tử rồi trả lại một danh sách vô hạn chỉ có chứa phần tử đó. Một cách viết hàm này theo dạng đệ quy là rất đơn giản, xem nhé.

repeat' :: a -> [a]
repeat' x = x:repeat' x

Khi gọi repeat 3, ta sẽ thu được danh sách bắt đầu bằng số 3 và tiếp theo là phần đuôi gồm vô hạn các số 3. Vì vậy, repeat 3 sẽ được ước lượng thành 3:repeat 3, vốn lại bằng 3:(3:repeat 3), bằng 3:(3:(3:repeat 3)), v.v. repeat 3 sẽ không bao giờ ngừng được ước lượng, nhưng take 5 (repeat 3) sẽ cho ta danh sách có năm con số 3. Như vậy cũng giống như viết replicate 5 3.

zip nhận vào hai danh sách và đan cài chúng với nhau. zip [1,2,3] [2,3] trả lại [(1,2),(2,3)], vì nó cắt bớt danh sách dài để vừa với danh sách ngắn. Thế còn nếu ta zip danh sách với một danh sách rỗng? À, khi đó ta nhận được một danh sách rỗng. Đó cũng chính là điều kiện biên. Tuy vậy, zip nhận hai danh sách làm đối số, cho nên sẽ có hai điều kiện biên.

zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

Trước hết, hai mẫu phát biểu rằng nếu danh sách thứ nhất hoặc thứ hai là danh sách rỗng, thì ta nhận được một danh sách rỗng. Mẫu thứ ba phát biểu rằng hai danh sách đan cài lại thì bằng việc cặp đôi hai phần tử đầu lại rồi xử lý hai phần đuôi được đan cài. Việc đan cài [1,2,3]['a','b'] sẽ dẫn đến cuối cùng phải đan cài [3] với []. Điều kiện biên đã xuát hiện và do đó kết quả là (1,'a'):(2,'b'):[], hay chính là [(1,'a'),(2,'b')].

Ta hãy tự lập thêm một hàm nữa đã có trong thư viện chuẩn — hàm elem. Nó nhận vào một phần tử và một danh sách rồi xem liệu rằng phần tử có trong danh sách hay không. Điều kiện biên, như thường thấy đối với danh sách, chính là danh sách rỗng. Ta biết rằng một danh sách rỗng thì không chứa phần tử nào, vì vậy chắc chắn nó không chứa phần tử ta cần tìm.

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x    = True
    | otherwise = a `elem'` xs

Khá đơn giản và như ta mong đợi. Nếu phần tử đầu không phải là phần tử đang xét thì ta kiểm tra phần đuôi. Nếu đạt đến một danh sách rỗng, thì kết quả sẽ là False.

Sắp xếp, nhanh lên!

Ta có một danh sách các thứ có thể sắp xếp được. Kiểu của chúng cùng thuộc vào lớp Ord. Và bây giờ, ta muốn sắp xếp chúng! Có một thuật toán rất hay để sắp xếp được gọi là quicksort (sắp xếp nhanh). Nó là một cách khéo léo sắp xếp các phần tử. Trong khi lập trình viết quicksort bằng ngôn ngữ mệnh lệnh thì phải tốn ít nhất là 10 dòng lệnh, thì cách việt bằng Haskell lại ngắn và thanh lịch hơn nhiều. Quicksort đã trở thành “sản phẩm chào hàng” cho Haskell. Vì vậy, ta hãy cùng viết nó ngay, dù rằng viết quicksort trong Haskell được coi là khá điệu bộ vì người ta thực hiện nó chỉ để khoe Haskell thanh lịch thế nào.

quickman

Như vậy, dấu ấn kiểu ở đây sẽ là quicksort :: (Ord a) => [a] -> [a]. Không có gì đáng ngạc nhiên. Còn điều kiện biên? Một danh sách rỗng, như được trông đợi. Một danh sách rỗng sau khi sắp xếp vẫn là danh sách rỗng. Và bây giờ là thuật toán chính: một danh sách được sắp xếp là một danh sách, trong đó tất cả những giá trị nhỏ hơn (hoặc bằng) phần tử đầu của danh sách gốc thì được xếp lên trước (bản thân những giá trị này đã được sắp xếp), rồi đến phần tử đầu trong danh sách gốc, theo sau là những phần tử lớn hơn phần tử đầu (bản thân chúng cũng được sắp xếp). Lưu ý rằng trong lời định nghĩa trên, chúng ta đã hai lần nhắc đến được sắp xếp, vì vậy có thể ta phải gọi đệ quy hai lần! Cũng lưu ý rằng để định nghĩa hàm ta dùng từ chú không phải làm thứ này, làm thứ nọ, rồi làm thứ kia …. Đó chính là vẻ đẹp của lập trình hàm! Bây giờ làm thế nào ta có thể lọc danh sách đẻ chỉ lấy những phần tử nhỏ hơn phần tử đầu danh sách và chỉ những phần tử nào lớn hơn? Dùng dạng gộp danh sách. Vì vậy, hãy bắt tay vào định nghĩa hàm này.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = 
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

Ta hãy chạy thử nó cho một trường hợp nhỏ để xem liệu có đúng không.

ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]
[1,2,2,3,3,4,4,5,6,7,8,9,10]
ghci> quicksort "the quick brown fox jumps over the lazy dog"
"        abcdeeefghhijklmnoooopqrrsttuuvwxyz"

Hoan hô! Đó chính là điều tôi muốn nói tới! Vì vậy, nếu ta có, chẳng hạn [5,1,9,4,6,7,3] và muốn sắp xếp nó, thì thuật toán này trước hết sẽ lấy phần tử đầu, vốn là 5 rồi đặt nó vào giữa hai danh sách nhỏ hơn và lớn hơn bản thân nó. Vì vậy lúc này ta có [1,4,3] ++ [5] ++ [9,6,7]. Ta biết rằng một khi danh sách được sắp xếp xong xuôi, số 5 sẽ đứng ở vị trí thứ tư vì có 3 số nhỏ hơn nó và 3 số lớn hơn nó. Bây giờ, nếu ta sắp xếp [1,4,3][9,6,7], ta có một danh sách đúng trật tự! Ta sắp xếp hai danh sách này cũng chính bằng hàm hiện tại. Sau cùng, chúng ta sẽ tách nhỏ đén mức đạt đến danh sách rỗng và một danh sách rỗng thì bản thân nó đã được sắp xếp rồi. Sau đây là hình minh họa:

quicksort

Một phần tử đã đặt đúng chỗ và không di chuyển nữa được tô màu da cam. Nếu lần lượt đọc từ trái sang phải, bạn sẽ thấy danh sách được sắp xếp. Mặc dù ta đã chọn cách so sánh mọi phần tử với phần tử đầu, nhưng không nhất thiết vậy mà có thể so sánh với bất kì phần tử nào. Trong quicksort, phần tử được ta so sánh với thì có tên gọi là “chốt”. Ở đây, chúng được tô màu xanh lá cây. Chúng ta chọn phần tử đầy vì nó rất dễ lấy được bằng cách khớp mẫu. Các phần tử nào nhỏ hơn chốt được tô màu xanh nhạt còn những phần tử lớn hơn chốt thì tô màu xanh đậm. Dải màu vàng biểu diễn cho ta kết quả áp dụng quicksort.

Suy nghĩ theo cách đệ quy

Đến giờ ta đã thực hành một số bài đệ quy và bạn có thể đã nhận thấy rằng có một dạng chung. Thường thì bạn định nghĩa một điều kiện biên và sau đó định nghĩa một hàm làm việc gì đó giữa một phần tử và một hàm khác được áp dụng cho phần còn lại. Bất kể đó là danh sách, cây, hay một cấu trúc dữ liệu nào khác. Một tổng là phần tử thứ nhất cộng với tổng của phần còn lại của danh sách. Một tích của danh sách là phần tử đầu nhân với tích của phần sau của danh sách. Chiều dài danh sách bằng 1 cộng với chiều dài của phần đuôi danh sách. Vân vân và vân vân …

brain

Dĩ nhiên, cũng cần phải có điều kiện biên. Thông thường điều kiện biên là tình huống nào đó mà việc áp dụng đệ quy trở nên vô nghĩa. Khi làm với danh sách, điều kiện biên thường gặp nhất là với danh sách rỗng. Nếu bạn phải xử lý cấu trúc cây thì điều kiện biên thường là một nút mà không có nhánh con nào nữa.

Cũng tương tự khi bạn phải xử lý với những con số theo cách đệ quy. Thường đệ quy liên quan đến một con số nào đó và hàm áp dụng với một biến thể của số này. Ta đã lập hàm giai thừa và đó là tích của một số và gia thừa của số đó trừ một. Một cách áp dụng hàm đệ quy như vậy chẳng có ý nghĩa gì với số không, vì giai thừa chỉ được định nghĩa với các số nguyên dương. Thường thì điều kiện biên hóa ra là một phần tử trung hòa. Trong phép nhân, phần tử trung hòa bằng 1 vì bạn lấy bất cứ số gì nhân với 1 cũng nhận được chính số đó. Cũng vậy, khi làm việc với danh sách, ta định nghĩa tổng của danh sách rỗng bằng 0 và 0 chính là phần tử trung hòa trong phép cộng. Trong quicksort, trường hợp biên là danh sách rỗng và phần tử trung hòa cũng là danh sách rỗng, vì nếu bạn cộng một danh sách rỗng vào một danh sách bạn sẽ thu lại danh sách gốc.

Vì vậy khi nghĩ về cách đệ quy để giải một bài toán, bạn hãy cố hình dung xem khi nào lời giải đệ quy không có tác dụng và xét xem liệu bạn có thể dùng trường hợp đó làm điều kiện biên không. Hãy nghĩ về các phần tử trung hòa và xem liệu bạn có tách nhỏ tham số của hàm (chẳng hạn, danh sách thường được chia thành phần đầu và phần đuôi qua việc khớp mẫu) và ở phần nào bạn sẽ dùng đệ quy đối với nó.

Advertisements

%(count) bình luận

Filed under Haskell

One response to “Chương 5: Đệ quy

  1. Pingback: Tự học lấy Haskell | Blog của Chiến

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s