Trong chương này, ta sẽ xét một số bài toán hay và cách tư duy theo kiểu lập trình hàm để giải quyết chúng càng đẹp càng tốt. Có thể chúng tôi sẽ không giới thiệu thêm khái niệm mới nào, mà ta sẽ biểu diễn những kiến thức Haskell mới học và thực tập kĩ năng lập trình. Từng mục sẽ trình bày một bài toán riêng. Trước hết là đề bài, sau đó ta sẽ cố gắng tìm ra cách tốt nhất (hoặc ít dở nhất) để giải quyết nó.
Máy tính dùng kí pháp Ba Lan ngược
Thường khi viết biểu thức toán học ở trường phổ thông, ta viết theo kiểu trung tố. Chẳng hạn, ta viết 10 - (4 + 3) * 2. Trong đó, +, * và - là các toán tử trung tố, cũng như những hàm trung tố ta đã gặp ở Haskell (+, `elem`, v.v.). Điều này rất tiện lợi vì con người chúng ta có thể dễ dàng đọc và “tách” các biểu thức này ngay khi mới nhìn qua. Nhược điểm là ta phải dùng cặp ngoặc đơn để chỉ định thứ tự ưu tiên của phép tính.
Kí pháp Ba Lan ngược (Reverse Polish Notation, RPN) là một cách khác để viết các biểu thức toán học. Ban đầu trông nó có vẻ kì quặc, nhưng thực ra nó rất dễ hiểu và sử dụng vì không cần có cặp ngoặc đơn và ta có thể dễ dàng nhập nó vào trong một chiếc máy tính tay. Dù rằng tuyệt đại đa số các máy tính tay hiện đại đều dùng kí pháp trung tố, nhiều người vẫn nguyện theo máy tính RPN. Sau đây là biểu thức trung tố nêu trên khi viết lại dưới dạng RPN: 10 4 3 + 2 * -. Bằng cách nào mà ta có thể tính được kết quả? Ồ, hãy hình dung đến ngăn xếp. Bạn duyệt qua biểu thức từ trái sang phải. Mỗi khi gặp một con số, hãy đẩy nó vào ngăn xếp. Khi gặp một toán tử, hãy gỡ hai con số ở đỉnh ngăn xếp (còn gọi là bung ra (pop)), dùng toán tử này và hai số để tính kết quả rồi lại đẩy kết quả trở lại ngăn xếp. Khi đi đến cuối biểu thức, nếu biểu thức này hợp lệ thì bạn chỉ có trong tay một con số; và số này chính là kết quả.
Ta hãy cùng nhau duyệt qua biểu thức 10 4 3 + 2 * - nhé! Trước hết ta đẩy 10 vào ngăn xếp và bây giờ ngăn xếp là 10. Phần tử tiếp theo là 4, vì vậy ta cũng đẩy nó vào ngăn xếp. Bây giờ ngăn xếp là 10, 4. Ta cũng làm tương tự đối với 3 và bây giờ ngăn xếp là 10, 4, 3. Và bây giờ, ta bắt gặp một toán tử, là +! Ta bung hai số trên cùng của ngăn xếp (vì vậy bây giờ ngăn xếp chỉ còn là 10), cộng hai số này lại rồi đẩy kết quả đó trở lại ngăn xếp. Lúc này ngăn xếp là 10, 7. Ta đẩy 2 vào ngăn xếp, bây giờ ngăn xếp là 10, 7, 2. Ta lại gặp phải một toán tử, vậy hãy bung 7 và 2 khỏi ngăn xếp, nhân chúng lại rồi đẩy kết quả đó trở vào ngăn xếp. Việc nhân 7 với 2 cho ra 14, và ngăn xếp bây giờ là 10, 14. Cuối cùng, có một dấu -. Ta bung 10 và 14 khỏi ngăn xếp, lấy 10 trừ 14 rồi đẩy kết quả tìm được vào ngăn xếp. Con số ở ngăn xếp bây giờ là -4 và vì không còn số nào hoặc toán tử nào còn lại trong biểu thức nữa nên đó chính là kết quả cần tìm!
Bây giờ khi đã biết cách tính biểu thức RPN bằng tay, ta hãy nghĩ cách làm sao cho một hàm Haskell nhận tham số là một chuỗi chứa biểu thức RPN, như "10 4 3 + 2 * -" rồi trả lại kết quả cho ta.
Khi đó kiểu của hàm sẽ là gì? Ta muốn nó nhận tham số là một chuỗi rồi tính ra kết quả là một con số. VÌ vậy có lẽ nó sẽ phải đại loại như solveRPN :: (Num a) => String -> a.
Hay đấy. Khi viết mã lệnh cho lời giải một bài toán lập trình Haskell, thì bạn cũng nên nghĩ ngược lại rằng bạn sẽ tính bằng tay như thế nào và có thể là thử xem bạn có thể hiểu sâu hơn được gì trong bài toán. Ở đây ta thấy rằng ta đã coi từng số hoặc toán tử đứng cách nhau là một phàn tử. Vì vậy có thể sẽ hữu ích nếu ta bắt đầu bằng việc chẻ nhỏ một chuỗi như "10 4 3 + 2 * -" thành một danh sách các phần tử như ["10","4","3","+","2","*","-"].
Tiếp theo, ta đã hình dung là phải làm gì với danh sách các phần tử nhỉ? Ta duyệt nó từ trái qua phải và theo dõi một ngăn xếp trong quá trình làm việc này. Liệu câu trước có gợi nhớ bạn điều gì không? Hãy nhớ là, trong mục nói về hàm gấp, ta đã nói rằng hầu như hàm nào mà bạn dùng khi duyệt danh sách từ trái sang phải và tích tụ dần một kết quả (bất kể đó là số, danh sách, ngăn xếp, v.v.) thì đều có thể lập được bằng một phép gấp.
Trong trường hợp này, ta sẽ dùng cách gấp từ phía trái, vì ta duyệt danh sách từ trái qua phải. Giá trị tích lũy sẽ là ngăn xếp và do đó, kết quả của phép gấp cũng sẽ là ngăn xếp; có điều là như ta đã thấy, nó sẽ chỉ có một phần tử.
Chỉ còn một điều nữa phải suy nghĩ là ta sẽ biểu diễn ngăn xếp thế nào? Tôi đề nghị rằng ta dùng một danh sách. Và tôi cũng đề nghị rằng ta giữ cho đỉnh của ngăn xếp là phần tử đầu của danh sách. Như vậy bởi vì việc thêm vào đầu danh sách thì nhanh hơn nhiều so với thêm vào cuối. Do đó nếu như ta có ngăn xếp 10, 4, 3, ta sẽ biểu thị bằng danh sách [3,4,10].
Bây giờ khi đã có đủ thông tin để phác họa hàm được xét. Nó sẽ nhận một chuỗi, như "10 4 3 + 2 * -" rồi phá vỡ nó thành một danh sách các phần tử bằng hàm words để thu được["10","4","3","+","2","*","-"]. Tiếp theo, ta sẽ gấp danh sách từ phía trái và cuối cùng là có danh sách chỉ gồm một phần tử là [-4]. Ta lấy phần tử đó ra khỏi danh sách và đây chính là kết qủa cuối cùng!
Vậy sau đây là bản phác họa hàm nói trên:
import Data.List
solveRPN :: (Num a) => String -> a
solveRPN expression = head (foldl foldingFunction [] (words expression))
where foldingFunction stack item = ...Ta lấy biểu thức rồi chuyển nó thành một danh sách các phần tử. Sau đó dùng hàm gấp đối với danh sách này. Lưu ý đến []dùng để biểu diễn cho giá trị tích lũy ban đầu. Biến tích lũy chính là ngăn xếp, vì vậy [] biểu thị một ngăn xếp rỗng, là nơi chúng ta bắt đầu. Sau khi thu được ngăn xếp cuối cùng chỉ chứa một phần tử, ta gọi head đối với danh sách để lấy phần tử ra rồi áp dụng read.
Như vậy tất cả những thứ còn lại đến giờ là lập một hàm gấp nhận vào một ngăn xếp, như [4,10], và một phần tử, như "3" rồi trả lại một ngăn xếp mới [3,4,10]. Nếu ngăn xếp là [4,10] và phần tử là "*", thì kết quả trả về sẽ phải là [40]. Nhưng trước đó, hãy biến hàm ta viết thành dạng dùng dấu chấm vì nó đang có quá nhiều cặp ngoặc tròn khiến tôi phát khiếp:
import Data.List
solveRPN :: (Num a) => String -> a
solveRPN = head . foldl foldingFunction [] . words
where foldingFunction stack item = ...À, được rồi. Tốt hơn nhiều. Như vậy hàm gấp sẽ nhận một ngăn xếp cùng một phần tử rồi trả lại ngăn xếp mới. Ta sẽ dùng khớp mẫu để lấy những phần tử trên cùng khỏi ngăn xếp và khớp mẫu với những toán tử như "*" và "-".
solveRPN :: (Num a, Read a) => String -> a
solveRPN = head . foldl foldingFunction [] . words
where foldingFunction (x:y:ys) "*" = (x * y):ys
foldingFunction (x:y:ys) "+" = (x + y):ys
foldingFunction (x:y:ys) "-" = (y - x):ys
foldingFunction xs numberString = read numberString:xsTa chia làm bốn dạng mẫu riêng. Các dạng mẫu sẽ được thử từ trên xuống dưới. Trước hết, hàm gấp sẽ xét xem liệu phần tử hiện thời là "*" hay không. Nếu đúng, thì nó sẽ nhận một danh sách như [3,4,9,3] rồi gọi hai phần tử đầu của nó, lần lượt là x và y. Vậy trong trường hợp này, x sẽ là 3 còn y sẽ là 4. ys sẽ là [9,3]. Nó sẽ trả lại một danh sách cũng giống như ys, chỉ khác là nó có phần tử đầu là tích của x và y. Như vậy ở đây ta sẽ bung hai con số trên đỉnh ngăn xếp, nhân chúng lại và đẩy kết quả về lại ngăn xếp. Nếu phần tử không phải là "*", thì việc khớp mẫu sẽ lọt qua và sẽ kiểm tra đến "+", và cứ như vậy.
Nếu phần tử chẳng thuộc về toán tử nào cả, thì ta sẽ giả sử nó là một chuỗi biểu thị cho một con số. Nếu nó là số, ta chỉ việc gọi read với chuỗi này để lấy giá trị số từ đó, rồi trả lại ngăn xếp với số đó đặt lên đỉnh trên cùng.
Và như vậy đấy! Cũng cần lưu ý rằng ta đã bổ sung một rang buộc lớp gồm có Read a vào lời khai báo hàm, vì ta gọi read với chuỗi thu được để lấy giá trị số. Vì vậy lời khai báo này cosnghiax là kết quả có thể là kiểu dữ liệu bất kì thuộc về các lớp Num và Read (như Int, Float, v.v.).
Với danh sách các phần tử ["2","3","+"], hàm ta viết sẽ bắt đầu gấp từ phía trái. Ngăn xếp ban đầu sẽ là []. Nó sẽ gọi hàm gấp với ngăn xếp (biến tích lũy) [] và phần tử là "2". Vì phần tử không phải là một toán tử nên nó sẽ được đọc vào bằng read and rồi thêm vào đầu của []. Vì vậy ngăn xếp mới của ta bây giờ sẽ là [2] và hàm gấp sẽ được gọi với ngăn xếp là [2] và phần tử là ["3"] để tạo ra ngăn xếp mới là [3,2]. Sau đó, nó được gọi lần thứ ba với ngăn xếp là [3,2] và phần tử là "+". Việc này khiến cho hai con số được bung khỏi ngăn xếp, cộng lại rồi đẩy trở về. Và ngăn xếp cuối cùng sẽ là [5], chính là con số được trả lại.
Ta hãy thử nghịch hàm vừa viết xem sao:
ghci> solveRPN "10 4 3 + 2 * -" -4 ghci> solveRPN "2 3 +" 5 ghci> solveRPN "90 34 12 33 55 66 + * - +" -3947 ghci> solveRPN "90 34 12 33 55 66 + * - + -" 4037 ghci> solveRPN "90 34 12 33 55 66 + * - + -" 4037 ghci> solveRPN "90 3 -" 87
Hay đấy, nó hoạt động rồi! Một điều hay ở hàm này là nó có thể dễ dàng sửa đổi được để cho phép dùng các toán tử khác. Thậm chí chúng không nhất thiết phải là toán tử hai ngôi. Chẳng hạn, ta có thể tạo một toán tử "log" để bung mỗi một con số khỏi ngăn xếp rồi đẩy lại giá trị logarit trở lại ngăn xếp. Ta cũng có thể lập một toán tử ba ngôi để bung ba số khỏi ngăn xếp rồi đẩy kết quả trở lại; hoặc những toán tử như "sum" để bung tất cả số ra rồi đẩy kết quả tính tổng trở lại ngăn xếp.
Ta hãy sửa lại hàm số để nhận thêm một vài toán tử khác. Để đơn giản, ta sẽ đổi lời khai báo kiểu sao cho nó trả lại một con số thuộc kiểu Float.
import Data.List
solveRPN :: String -> Float
solveRPN = head . foldl foldingFunction [] . words
where foldingFunction (x:y:ys) "*" = (x * y):ys
foldingFunction (x:y:ys) "+" = (x + y):ys
foldingFunction (x:y:ys) "-" = (y - x):ys
foldingFunction (x:y:ys) "/" = (y / x):ys
foldingFunction (x:y:ys) "^" = (y ** x):ys
foldingFunction (x:xs) "ln" = log x:xs
foldingFunction xs "sum" = [sum xs]
foldingFunction xs numberString = read numberString:xsỒ, hay quá! / dĩ nhiên là phép chia còn ** là lũy thừa với số có dấu phẩy động. Với phép tính logarit, ta chỉ việc khớp mẫu với một phần tử và phần còn lại của ngăn xếp vì ta chỉ cần một phần tử để tính logarit tự nhiên. Với toán tử tổng, ta chỉ việc trả lại một ngăn xếp có một phần tử, vốn là tổng của các số trong ngăn xếp tại thời điểm đó.
ghci> solveRPN "2.7 ln" 0.9932518 ghci> solveRPN "10 10 10 10 sum 4 /" 10.0 ghci> solveRPN "10 10 10 10 10 sum 4 /" 12.5 ghci> solveRPN "10 2 ^" 100.0
Lưu ý rằng ta có thể dùng các số có dấu phẩy động trong biểu thức, vì read biết cách đọc chúng.
ghci> solveRPN "43.2425 0.5 ^" 6.575903
Tôi nghĩ rằng chỉ bằng 10 dòng lệnh mà lập nên một hàm có thể tính được những biểu thức RPN bất kì với số có dấu chấm động và có tùy chọn mở rộng được dễ dàng thì thật là tuyệt.
Một điều cần lưu ý về hàm này là nó không thật sự dễ tính khi số liệu có lỗi. Chương trình sẽ đổ vỡ khi nhận số liệu đầu vào không hợp lệ. Ta sẽ viết một phiên bản chương trình “dễ tính” hơn với một lời khai báo là solveRPN :: String -> Maybe Float ngay khi ta làm quen với monad (chúng không đáng sợ đâu, thật đấy!). Ta cũng có thể viết ngay bây giờ, nhưng việc này sẽ tẻ nhạt hơn vì cần phải nhiều lần kiểm tra Nothing ở mỗi bước. Nếu bạn cảm thấy muốn được thử thách, thì hãy tiến lên và viết lấy chương trình! Gợi ý: bạn có thể dùng reads để xem liệu việc đọc có thành công hay không.
THis is trân quốc
ConversionConversion EmoticonEmoticon