Chương 10: Giải bài toán theo phong cách lập trình hàm

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

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 đó, +, *- 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ả.

this expression

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 72 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 1014 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.

Mẹo: sẽ thực sự có ích nếu bạn luôn bắt đầu bằng việc suy nghĩ lời khai báo kiểu của hàm là gì trước khi lập hàm đó và viết mã lệnh. Trong Haskell, lời khai báo kiểu hàm cho chúng ta biết rất nhiều điều về hàm, vì nó thực sự giúp ta đầu tiên là nghĩ về khai báo kiểu của một hàm trước khi nỗ lực tạo lập hàm và viết mã lệnh. Trong Haskell, khai báo kiểu của hàm cho ta rất nhiều thông tin về hàm, nhờ vào hệ thống kiểu mạnh mẽ.

HA HA HA

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ư "*""-".

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:xs

Ta 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à xy. 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 xy. 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 NumRead (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.

Từ Heathrow đến London

Bài toán tiếp theo là thế này: máy bay chở bạn vừa hạ cánh xuống nước Anh và bạn thuê xe hơi. Bạn phải khẩn trương đến dự họp và cần đi từ sân bay Heathrow về London càng nhanh càng tốt (nhưng phải an toàn!).

Có hai tuyến đường chính chạy từ Heathrow về London và nhiều mạch đường nhỏ giao cắt ngang. Để đi từ một điểm giao cắt đến điểm tiếp theo thì mất một thời gian nhất định nào đó. Bạn hãy tìm đường tối ưu để đi đến London, càng nhanh càng tốt! Bạn khởi đầu từ phía trái và có thể hoặc là đi thẳng tiếp hoặc chuyển sang tuyến đường chính còn lại.

Heathrow - London

Như bạn thấy ở trên hình, đường ngắn nhất đi từ Heathrow đến London trong trường hợp này là xuất phát từ đường chính B, chuyển tuyến đường, đi thẳng tiếp trên đường A, lại chuyển đường, rồi hai lần chạy thẳng trên B. Nếu chọn tuyến đường này, sẽ mất 75 phút. Nếu ta chọn bất kì tuyến nào khác, sẽ đi mất nhiều thời gian hơn.

Nhiệm vụ của ta là lập chương trình để nhận đầu vào biểu diễn cho một hệ thống đường rồi in ra đường đi ngắn nhất là thế nòa. Sau đây dữ liệu đầu vào trong trường hợp này:

50
10
30
5
90
20
40
2
25
10
8
0

Để tính nhẩm việc tách tập tin đầu vào, hãy đọc ba con số một rồi hình dung việc chia hệ thống đường thành các đoạn. Mỗi đoạn gồm có đường A, đường B và đường giao cắt ngang. Để nhóm các số vừa đủ thành các bộ ba thì ta hãy thêm một “đoạn đường ngang” tưởng tượng ở cuối với thời gian chạy qua đường này bằng 0. Đó là vì khi ta đã đến được London rồi thì chẳng cần biết là ta đến bằng đoạn cuối đường A hay B.

Cũng như ta đã làm khi giải bài toán máy tính tay RPN, ta sẽ giải bài này theo ba bước:

  • Tạm quên Haskell đi và hình dung cách giải bằng tay
  • Nghĩ xem ta sẽ biểu diễn dữ liệu trong Haskell như thế nào
  • Hình dung cách tính toán với dữ liệu này trong Haskell để có được lời giải

Trong mục máy tính RPN, đầu tiên là ta đã hình dung rầng khi tính biểu thức bằng tay, ta đã nhẩm trong đầu hình ảnh về ngăn xếp và rồi duyệt theo biểu thức, từng phần tử một. Ta đã quyết định dùng danh sách các chuỗi để biểu diễn biểu thức cần tính. Sau cùng, ta dùng một phép gấp trái để duyệt theo danh sách các chuỗi trong khi vẫn duy trì ngăn xếp để thu được kết quả cuối cùng.

Được rồi, vậy bằng cách nào ta tính nhẩm ra được con đường ngắn nhất đi từ Heathrow đến London? Ồ, ta hãy hình dung một bức tranh tổng thể rồi thử đoán một con đường ngắn nhất và hi vọng rằng lần đoán này đúng. Cách làm này dùng được với những dữ liệu đầu vào quy mô nhỏ, nhưng sẽ thế nào nếu tuyến đường của ta có 10.000 đoạn? Oái! Ta sẽ không thể nói chắc rằng cách ta chọn là tối ưu, mà chỉ kiểu như đảm bảo rằng cách đó là được.

Như thế chưa phải là lời giải hay. Sau đây là hình minh họa đơn giản của tuyến đường đang xét:

roads

Được rồi, bạn có thể hình dung được đường ngắn nhất đến chỗ giao cắt thứ nhất (dấu chấm màu xanh đầu tiên trên tuyến A, điểm A1) trên tuyến đường A là gì không? Thật quá đơn giản. Ta chỉ việc xem liệu đi thẳng theo A thì nhanh hơn hay đi thẳng theo B rồi rẽ vào đường ngang. Dĩ nhiên là sẽ nhanh hơn nếu đi theo B rồi rẽ ngang vì như vậy chỉ tốn 40 còn đi thẳng theo A sẽ tốn 50 phút. Thế còn đến điểm giao B1? Cũng theo cách tương tự thôi. Ta thây rằng sẽ nhanh hơn nhiều nếu đi thẳng theo B (mất có 10 phút), vì việc đi theo A và rồi rẽ ngang sẽ mất cả thảy là 80 phút!

Bây giờ khi đã biết đường ngắn nhất đến A1 rồi (đi theo B rồi rẽ ngang; ta sẽ gọi cách này là B, C với tổng thời gian 40) và ta biết được con đường nhanh nhất đến B1 (đi thẳng theo B, như vậy chỉ là B, thời gian là 10). Liệu kiến thức này giúp gì cho ta nếu muốn biết đường nhanh nhất dễn đến hai điểm giao cắt kế tiếp trên hai tuyến đường? Ồ, tất nhiên là có chứ!

Ta hãy xem đường nhanh nhất đến A2 là gì. Muốn đến được A2, ta sẽ phải hoặc là đi thẳng từ A1 đến A2, hoặc đi thẳng từ B1 rồi rẽ ngang (nhớ rằng ta chỉ có quyền đi thẳng hoặc rẽ ngang qua đường kia). Và vìa ta đã biết thời gian để đi đến A1B1, ta có thể dễ dàng hình dung ra đường tốt nhất đẻ đến A2 là gì. Mất 40 phút để đến A1 rồi 5 phút để đi từ A1 đến A2, và như vậy đường đi là B, C, A với tổng thời gian là 45. Chỉ mất 10 phút để tới B1, nhưng sau đó sẽ mất thêm 110 phút nữa để tới B2 rồi rẽ ngang! Vì vậy, hiển nhiên là đường nhanh nhất để tới A2B, C, A. Tương tự, đường nhanh nhất để tới B2 là đi thẳng từ A1 rồi rẽ ngang.

Có lẽ bạn đang tự hỏi: nhưng nếu đi tới A2 bằng cách trước hết là rẽ ngang tại B1 rồi mới đi thẳng thì sao? À, ta đã xét đến việc rẽ ngang từ B1 qua A1 khi tìm con đường ngắn nhất tới A1 rồi, vì vậy ta sẽ không phải tính đến nó nữa trong bước tiếp theo.

Bây giờ, khi đã có con đường tốt nhất tới A2B2, ta có thể lặp lại cách này đến tận khi tới cuối con đường. Một khi đã có các con đường nhanh nhất tới A4B4, thì đường nào nhanh hơn trong số đó sẽ là tối ưu!

Như vậy về bản chất, đối với đoạn đường thứ hai, ta chỉ lặp lại bước tính toán mà ta đã làm với đoạn thứ nhất, chỉ khác là tính đến những con đường nhanh nhất trước đó đi theo A và B là gì. Ta có thể nói rằng ta cũng tính đến những con đường nhanh nhất đi theo A và B trong bước thứ nhất, chỉ lưu ý rằng chúng đều là những “đoạn đường” tưởng tượng với thời gian đi bằng 0.

Sau đây là nội dung tóm tắt những nhận định nói trên. Để tìm được đường nhanh nhất từ Heathrow tới London, ta làm như sau: trước hết ta xết đường nhanh nhất đi theo tuyến đường A đến điểm giao cắt tiếp theo là gì. Có hai cách lựa chọn: đó là tiếp tục đi thẳng hoặc khởi đầu từ tuyến đường kia, đi thẳng và rồi rẽ ngang. Ta ghi nhớ thời gian đi theo mỗi cách rồi sau đó làm tương tự với chỗ đường giao đối diện với nó. Cứ thực hiện tính toán như thế này đối với mỗi đoạn đường đến khi tới điểm cuối. Khi đó, đường nhanh hơn trong số hai con đường cần xét chính là con đường tối ưu!

Như vậy cơ bản là ta giữ lại đường ngắn nhất đi theo A và đường ngắn nhất đi theo B rồi khi đến điểm cuối thì đường ngắn hơn trong hai tuyến đó chính là đường cần tìm. Bây giờ ta đã biết cách thủ công để tính ra đường ngắn nhất. Nếu có thời gian, sẵn giấy bút, bạn có thể tìm ra đường ngắn nhất qua một hệ thống đường có bao nhiêu đoạn cũng được.

Bước tiếp theo! Ta sẽ biểu diễn hệ thống đường này bằng kiểu dữ liệu trong Haskell như thế nào? Một cách hình dung các điểm đầu và các điểm giao cắt là như những đỉnh của đồ thị, từ đỉnh này chỉ tới các đỉnh khác. Nếu tưởng tượng rằng các điểm đầu thực ra là chỉ đến nhau qua một đoạn đường có chiều dài bằng 1 thì ta thấy rằng mỗi điểm giao cắt (hay đỉnh) sẽ chỉ đến một đỉnh phía bên kia và một đỉnh kế tiếp ở cùng phía. Trừ các đỉnh cuối cùng: chúng sẽ chỉ về mỗi phía bên kia.

data Node = Node Road Road | EndNode Road
data Road = Road Int Node

Một đỉnh trong đồ thị hoặc là đỉnh thông thường chứa thông tin về con đường ngang dẫn đến đường chính bên kia và đường chính dẫn đến đỉnh tiếp theo (hoặc đỉnh cuối, ở đỉnh này thì chỉ có thông tin về đường ngang qua bên phía bên kia). Một con đường thì chứa thông tin về độ dài (thời gian đi) và đỉnh nào nó chỉ tới. Chẳng hạn, phần thứ nhất của con đường trên đường chính A sẽ là Road 50 a1 trong đó a1 sẽ là một đỉnh Node x y, trong đó xy là các đường chỉ tới B1A2.

Một cách khác là dùng Maybe cho những đoạn đường hướng thẳng tiến. Mỗi đỉnh có một đoạn đường chỉ đến đường bên kia, nhưng phải là đỉnh không phải cuối cùng thì mới có đoạn đường tiến thẳng.

data Node = Node Road (Maybe Road)
data Road = Road Int Node

Đây cũng là cách tạm được để biểu diễn hệ thống đường trong Haskell và ta dĩ nhiên là giải được bài toán theo cách này, nhưng có thể ta đã tìm được cách nào đó đơn giản hơn chăng? Nếu ta nghĩ lại về lời giải thủ công, thì ta sẽ luôn chỉ cần kiểm tra độ dài của ba đoạn đường cùng lúc: đoạn đường trên tuyến A road, đoạn đường đối diện với nó trên tuyến B và đoạn đường ngang C nối giữa hai tuyến. Khi tìm đường ngắn nhất tới A1B1, ta chỉ phải xét đến độ dài của ba đoạn đầu tiên, tức là 50, 10 và 30. Ta sẽ gọi đó là một khúc. [Để cho rõ ràng, từ nay ta gọi khúc đường gồm có ba đoạn đường kể trên.] Như vậy ở ví dụ này, hệ thống đường đang xét có thể dễ dàng biểu diễn được theo 4 khúc: 50, 10, 30, 5, 90, 20, 40, 2, 25, và 10, 8, 0.

Ta luôn nên giữ cho kiểu dữ liệu càng đơn giản càng tốt, mặc dù không nên đơn giản hơn!

data Section = Section { getA :: Int, getB :: Int, getC :: Int } deriving (Show)
type RoadSystem = [Section]

Như thế này là gần hoàn hảo rồi! Làm đến đâu thấy đơn giản đến đó, tôi có cảm tưởng rằng cách này sẽ áp dụng tốt để viết chương trình giải. Section là một kiểu dữ liệu đại số đơn giản, biểu diễn cho một khúc đường; nó chứa ba số nguyên biểu thị độ dài của ba đoạn đường. Ta cũng giới thiệu một kiểu tương đồng, để chỉ ra rằng RoadSystem là một danh sách các khúc.

Ta cũng có thể dùng một bộ ba (Int, Int, Int) để biểu diễn một khúc đường. Bằng cách dùng bộ thay vì tự lập nên kiểu dữ liệu đại số riêng thì cũng được trong những trường hợp nhỏ lẻ, nhưng thường sẽ tốt hơn khi ta tạo một kiểu dữ liệu mới dành cho những dữ liệu kiểu thế này. Nó cung cấp cho hệ thống kiểu thêm những thông tin. Ta có thể dùng (Int, Int, Int) để cùng biểu diễn khúc đường và véc-tơ trong không gian ba chiều, và có thể thực hiện phép toán với chúng, nhưng việc được phép làm như vậy sẽ khiến cho mọi thứ xáo trộn. Còn nếu dùng các kiểu dữ liệu SectionVector, thì ta không thể cộng nhầm véc-tơ với một khúc đường.

Ở đây, hệ thống đường từ Heathrow tới London có thể được biểu diễn như sau:

heathrowToLondon :: RoadSystem
heathrowToLondon = [Section 50 10 30, Section 5 90 20, Section 40 2 25, Section 10 8 0]

Bây giờ, tất cả những gì ta cần làm là viết chương trình Haskell để giải theo ý tưởng đã thảo luận ở trên. Lời khai báo kiểu cho hàm tính toán ra đường ngắn nhất đối với hệ thống đường cho trước bất kì sẽ nên là gì đây nhỉ? Hàm này cần nhận tham số là hệ thống đường rồi trả lại một con đường. Ta cũng sẽ biểu diễn một con đường dưới dạng danh sách. Hãy giới thiệu một kiểu Label vốn chỉ là dạng liệt kê, gồm A, B hoặc C. Ta cũng lập một kiểu tương đồng: Path.

data Label = A | B | C deriving (Show)
type Path = [(Label, Int)]

Theo đó, hàm ta lập ở đây với tên gọi optimalPath cần có lời khai báo kiểu là optimalPath :: RoadSystem -> Path. Nếu được gọi với hệ thống đường heathrowToLondon, nó sẽ phải trả lại con đường sau:

[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8)]

Ta sắp sửa duyệt theo danh sách những khúc đường từ phía trái qua phải và giữ lại con đường tối ưu theo A và tối ưu theo B trong quá trình duyệt. Ta sẽ tích luỹ đường tốt nhất trong quá trình duyệt từ trái qua phải. Điều đó gợi cho ta khái niệm gì? Vâng, bạn trả lời đi? Phải rồi! một PHÉP GẤP TRÁI!

Khi giải bài toán bằng tay, đã có một bước mà ta lặp đi lặp lại. Nó bao gồm việc kiểm tra những con đường tối ưu theo A và B cho đến giờ cùng với khúc hiện tại để tìm ra những con đường tối ưu mới theo A và B. Chẳng hạn, lúc đầu, các con đường tối ưu tới A và B lần lượt là [][]. Ta đã kiểm tra khúc Section 50 10 30 và kết luận rằng đường tối ưu tới A1[(B,10),(C,30)] còn đường tối ưu tới B1[(B,10)]. Nếu bạn coi thao tác ở bước này như là một hàm thì hàm này nhận một cặp đường đi và một khúc để tạo ra một cặp đường đi mới. Kiểu dữ liệu là (Path, Path) -> Section -> (Path, Path). Hãy tiếp tục lập hàm này, vì nó hẳn sẽ rất hữu dụng.

Gợi ý: nó sẽ có ích vì (Path, Path) -> Section -> (Path, Path) có thể được dùng như hàm hai ngôi trong phép gấp trái, để làm như vậy thì hàm cần phải có kiểu a -> b -> a
roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (pathA, pathB) (Section a b c) = 
    let priceA = sum $ map snd pathA
        priceB = sum $ map snd pathB
        forwardPriceToA = priceA + a
        crossPriceToA = priceB + b + c
        forwardPriceToB = priceB + b
        crossPriceToB = priceA + a + c
        newPathToA = if forwardPriceToA <= crossPriceToA
                        then (A,a):pathA
                        else (C,c):(B,b):pathB
        newPathToB = if forwardPriceToB <= crossPriceToB
                        then (B,b):pathB
                        else (C,c):(A,a):pathA
    in  (newPathToA, newPathToB)

this is you

Điều gì đang diễn ra ở đây thế? Trước hết là đi tính thời gian (chi phí, “price”) theo đường A, dựa trên thời gian ngắn nhất cho đến giờ đi theo A, và tính toán tương tự đối với B. Ta viết sum $ map snd pathA, nghĩa là nếu pathA là, chẳng hạn, [(A,100),(C,20)], thì priceA sẽ là 120. forwardPriceToA là thời gian cần thiết nếu muốn đến điểm giao cắt tiếp theo trên A nếu ta đi thẳng đến đó từ điểm giao cắt trước cũng trên A. Nó sẽ bằng thời gian tối ưu đến điểm giao cắt trước trên A, cộng với chiều dài của phần đường trên A thuộc khúc hiện tại. crossPriceToA là thời gian sẽ phải mất nếu ta đến điểm giao cắt tiếp theo trên A bằng cách đi thẳng từ điểm trước trên B rồi rẽ ngang. Nó sẽ bằng thời gian tối ưu đến điểm trước trên B cộng với thời gian đi trên đoạn B của khúc hiện tại cộng với thời gian đi trên đoạn C của khúc hiện tại. Ta cũng xác định forwardPriceToBcrossPriceToB theo cách tương tự.

Bây giờ khi ta đã biết rằng đường đi tối ưu tới A và tới B là gì rồi, thì ta chỉ cần lập những đường đi mới tới A và B dựa trên các con đường tối ưu trên. Nếu tới A nhanh hơn bằng cách đi thẳng thì ta đặt newPathToA bằng (A,a):pathA. Về cơ bản, ta đã đặt Label có tên A và chiều dài khúc, a và trước con đường tối ưu theo A cho đến giờ. Về cơ bản, ta đã nói rằng đường tốt nhất đến điểm giao cắt tiếp theo trên A là con đường đến điểm giao cắt trước đó trên A và rồi một đoạn đi thẳng dọc theo A. Hãy nhớ rằng, A chỉ là một nhãn, còn a có kiểu là Int. Tại sao ta lại đặt trước thay vì thực hiện pathA ++ [(A,a)]? À, thêm một phần tử vào đầu danh sách (còn gọi là thao tác “cons”) sẽ nhanh hơn nhiều so với thêm vào từ phía cuối. Điều này nghĩa là con đường này sẽ là sai một khi ta gấp qua danh sách bằng hàm này, nhưng sau này ta sẽ dễ dàng lật ngược lại danh sách. Nếu ta có thể đi đến điểm giao cắt trên đường A một cách nhanh hơn bằng việc đi thẳng theo B trước rồi mới rẽ ngang, thì newPathToA sẽ bằng đường tối ưu đến B trước đó rồi thẳng tiến và rẽ ngang qua A. Ta làm điều tương tự với newPathToB, chỉ khác là đảo lại mọi thứ.

Sau cùng, ta trả lại một cặp gồm có newPathToAnewPathToB.

Ta hãy chạy hàm này cho khúc đầu tiên của heathrowToLondon. Vì nó là khúc đầu tiên nên tham số là các con đường tối ưu theo A và B sẽ là một cặp danh sách rỗng.

ghci> roadStep ([], []) (head heathrowToLondon)
([(C,30),(B,10)],[(B,10)])

Hãy nhớ rằng, các con đường được viết theo thứ tự đảo ngược, vì vậy cần đọc từ phải qua trái. Từ đây ta có thể đọc ra đường tối ưu đến điểm A tiếp theo là bắt đầu đi từ B rồi rẽ ngang qua A, và đường tốt nhất đi tới điểm B tiếp theo là chỉ cần đi thẳng từ điểm xuất phát trên B.

Mẹo nhỏ trong tối ưu: khi ta viết priceA = sum $ map snd pathA, ta đang đi tính thời gian đi những con đường ở mỗi bước. Ta sẽ không phải làm như vậy nếu đã viết roadStep là một hàm (Path, Path, Int, Int) -> Section -> (Path, Path, Int, Int) trong đó các số nguyên biểu diễn cho thời gian ngắn nhất đi trên A và B.

Bây giờ khi đã có một hàm nhận một cặp đường đi và mọt khúc rồi trả lại một đường đi tối ưu mới, ta có thể dễ dàng thực hiện gấp trái đối với danh sách những khúc đường. roadStep được gọi với ([],[]) và khúc thứ nhất rồi trả lại một cặp đường tối ưu ứng với đoạn đó. Tiếp theo, hàm này được gọi với cặp đường đi mới tìm được và khúc kế tiếp, rồi cứ như vậy. Khi ta đã duyệt qua tất cả những khúc đường, ta sẽ giữ lại một cặp đường đi tối ưu và đường ngắn hơn sẽ là đáp án. Với nhận định này, ta có thể lập optimalPath như sau.

optimalPath :: RoadSystem -> Path
optimalPath roadSystem =
    let (bestAPath, bestBPath) = foldl roadStep ([],[]) roadSystem
    in  if sum (map snd bestAPath) <= sum (map snd bestBPath)
            then reverse bestAPath
            else reverse bestBPath

Ta gấp trái qua roadSystem (hãy nhớ rằng đó là một danh sách các khúc) với biến tích luỹ đầu tiên là một cặp đường đi rỗng. Kết quả của phép gấp đó là một cặp đường đi, vì vậy ta khớp mẫu với cặp đường đi này để lấy được từng con đường riêng lẻ. Sau đó, ta kiểm tra xem đường nào đi nhanh hơn rồi trả lại kết quả là đường đi đó, nhưng cần lật ngược trước khi trả lại, bởi những đường đi tối ưu cho đến giờ đều được viết ngược để dễ thao tác bằng phép toán đặt trước (“cons”) thay vì đặt sau (“append”).

Let’s test this!

ghci> optimalPath heathrowToLondon
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]

Đây là kết quả mà ta cần thu được! Thật tuyệt! Nó khác một chút so với kết quả trông đợi vì có thêm một bước (C,0) ở cuối, có nghĩa là ta rẽ ngang đường một lần khi đã đến London rồi, nhưng bởi vì việc này chẳng mất thêm thời gian gì, nên kết quả vẫn đúng.

Ta có hàm tìm ra đường tối ưu rồi, bây giờ ta chỉ việc đọc, từ thiết bị đầu vào chuẩn, một hình thức biểu diễn văn bản của một hệ thống đường, rồi chuyển nó thành kiểu RoadSystem, lấy nó chạy cho hàm optimalPath ta vừa lập rồi in ra đường đi nhanh nhất.

Trước hết, ta hãy tạo một hàm nhận vào một danh sách rồi chia nó thành các nhóm có cùng kích thước. Ta sẽ đặt tên cho hàm này là groupsOf. Đối với tham số là [1..10], groupsOf 3 cần phải trả lại [[1,2,3],[4,5,6],[7,8,9],[10]].

groupsOf :: Int -> [a] -> [[a]]
groupsOf 0 _ = undefined
groupsOf _ [] = []
groupsOf n xs = take n xs : groupsOf n (drop n xs)

Một hàm đệ quy chuẩn mực. Đối với xs bằng [1..10]n bằng 3, một lần áp dụng hàm sẽ cho ra [1,2,3] : groupsOf 3 [4,5,6,7,8,9,10]. Khi kết thúc đệ quy, ta nhận được danh sách theo các nhóm từng ba số một. Và sau đây là hàm main, để làm nhiệm vụ đọc vào từ thiết bị đầu vào chuẩn, từ đó tạo ra một RoadSystem rồi in ra con đường ngắn nhất:

import Data.List

main = do
    contents <- getContents
    let threes = groupsOf 3 (map read $ lines contents)
        roadSystem = map (\[a,b,c] -> Section a b c) threes
        path = optimalPath roadSystem
        pathString = concat $ map (show . fst) path
        pathPrice = sum $ map snd path
    putStrLn $ "The best path to take is: " ++ pathString
    putStrLn $ "The price is: " ++ show pathPrice

Đầu tiên là ta lấy toàn bộ số liệu từ đầu vào chuẩn. Sau đó, ta gọi lines với số liệu đó để chuyển đổi những thứ như "50\n10\n30\n... thành ["50","10","30".. rồi sau đó ánh xạ read lên danh sách này để chuyển đổi thành một danh sách số. Ta gọi groupsOf 3 đối với danh sách số để biến nó thành một danh sách gồm các danh sách 3 phần tử. Ta ánh xạ hàm lambda (\[a,b,c] -> Section a b c) lên danh sách chứa các danh sách đó. Như bạn thấy đấy, hàm lambda này chỉ nhận một danh sách 3 phần tử rồi biến nó thành một khúc đường. Vì vậy bây giờ roadSystem là hệ thống đường ta có trong tay và nó thậm chí còn có đúng kiểu dữ liệu là RoadSystem (hoặc [Section]). Ta gọi optimalPath với hệ thống đường này và rồi thu được đường tối ưu cùng với tổng thời gian đi đường, dưới hình thức biểu diễn thích hợp; sau đó in kết quả này ra.

Ta lưu đoạn văn bản chữ sau

50
10
30
5
90
20
40
2
25
10
8
0

vào một tập tin có tên paths.txt rồi đưa nó vào chương trình vừa viết.

$ cat paths.txt | runhaskell heathrow.hs
The best path to take is: BCACBBC
The price is: 75

Chạy thật mê ly! Bạn có thể dùng kiến thức thu được từ module Data.Random để phát sinh một hệ thống đường dài hơn, và rồi đưa vào chương trình vừa viết. Nếu gặp lỗi tràn ngăn xếp bộ nhớ, hãy thử dùng foldl' thay vì foldl, vì foldl' là dạng hàm chặt chẽ.

2 phản hồi

Filed under Haskell

2 responses to “Chương 10: Giải bài toán theo phong cách lập trình hàm

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

Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s