markdown:
Trở về
[Mục lục](https://quangchien.wordpress.com/2012/04/16/ch1-learn-haskell/#toc) cuốn sách
Ta đã thấy các monad có thể được dùng để nhận giá trị kèm ngữ cảnh và cách áp dụng chúng cho hàm ra sao, đồng thời cách dùng
>>= hoặc khối lệnh
do cho phép tập trung vào bản thân các giá trị và không cần lo lắng đến ngữ cảnh như thế nào.
Ta đã gặp monad
Maybe và thấy được cách nó thêm vào giá trị một ngữ cảnh về khả năng thất bại. Ta đã học monad danh sách và thấy cách nó giúp ta dễ dàng giới thiệu đại lượng không tất định vào trong chương trình. Ta cũng học được cách làm việc trong monad
IO, ngay cả trước khi ta biết monad là gì!
Trong chương này, ta sẽ học thêm một số monad nữa. Ta sẽ thấy cách chúng có thể giúp cho chương trình trở nên rõ ràng hơn bằng cách cho phép ta coi tất cả các loại giá trị như là giá trị monad. Việc khám phá thêm một số các monad cũng sẽ củng cố trực giác của ta về monad.
Những monad mà ta sẽ tìm hiểu đều thuộc về gói
mtl. Trong Haskell, một gói là một tập hợp các module. Gói
mtl đi cùng với Haskell Platform, vì vậy nhiều khả năng là bạn đã có nó rồi. Để kiểm tra điều này, hãy gõ vào
ghc-pkg list từ dòng lệnh. Máy sẽ hiển thị những những gói Haskell nào mà bạn đã cài và một trong số đó sẽ là
mtl, theo sau là số phiên bản.
### Writer? Tôi hầu như chẳng biết gì về nó!
Ta đã được trang bị monad
Maybe, monad danh sách và monad
IO. Bây giờ ta hãy đặt monad
Writer lên bệ phóng và xem điều gì sẽ xảy ra khi ta khai hỏa!
Nếu như
Maybe được dành cho các giá trị kèm theo ngữ cảnh thất bại, và monad danh sách dành cho các giá trị không tất định, thì monad
Writer lại dành cho những giá trị có giá trị khác gắn vào và đóng vai trò như một dạng giá trị để ghi chép.
Writer cho phép ta thực hiện tính toán trong khi vẫn yên tâm rằng các giá trị ghi chép lại đã được kết hợp làm một và giá trị này sau đó được gắn vào với kết quả.
Chẳng hạn, ta có thể muốn trang bị cho các giá trị hiện có thêm các chuỗi kí tự giải thích xem điều gì đang diễn ra, đặc biệt là đối với mục đích gỡ lỗi. Xét một hàm nhận vào một số tên cướp trong băng đảng và báo cho ta biết xem băng cướp đó có lớn hay không. Đây là một hàm rất đơn giản:
isBigGang :: Int -> Bool isBigGang x = x > 9
Bây giờ, sẽ ra sao nếu thay vì chỉ có kết quả là giá trị
True hoặc
False, ta muốn hàm này cũng trả lại một chuỗi ghi chép về những việc nó đã làm? Ồ, ta có thể chỉ cần tự tạo chuỗi đó rồi trả lại cùng với giá trị
Bool đang xét:
isBigGang :: Int -> (Bool, String) isBigGang x = (x > 9, "Compared gang size to 9.")
Như vậy bây giờ, thay vì chỉ trả lại một
Bool, ta trả lại một bộ trong đó phần tử thứ nhất của bộ là giá trị thực còn phần tử thứ hai là chuỗi đi kèm giá trị đó. Bây giờ đã có thêm một ngữ cảnh nhất định được bổ sung. Ta hãy thử cách làm này:
ghci> isBigGang 3 (False,"Compared gang size to 9.") ghci> isBigGang 30 (True,"Compared gang size to 9.")
Đến giờ mọi việc đều ổn cả.
isBigGang nhận một giá trị thường rồi trả lại một giá trị kèm ngữ cảnh. Như ta đã thấy, việc đưa một giá trị thông thường vào hàm không thành vấn đề. Bây giờ sẽ thế nào nếu ta đã có một giá trị kèm theo chuỗi ghi chép gắn với nó, như
(3, "Smallish gang."), và ta muốn đưa nó vào trong hàm
isBigGang? Dường như một lần nữa, ta phải đối diện với câu hỏi: nếu đã có một hàm vốn nhận giá trị thường và trả lại giá trị kèm ngữ cảnh, làm thế nào để ta lấy giá trị kèm ngữ cảnh và đưa nó vào trong hàm này?
Khi khám phá monad
Maybe, ta đã lập nên hàm
applyMaybe, vốn lấy một giá trị
Maybe a và một hàm thuộc kiểu
a -> Maybe b rồi đưa giá trị
Maybe a đó vào trong hàm, ngay cả khi hàm nhận một
a thông thường thay vì
Maybe a. Hàm làm được việc này qua việc để ý ngữ cảnh đi kèm theo các giá trị
Maybe a, vốn là những giá trị có khả năng thất bại. Nhưng bên trong hàm
a -> Maybe b, ta có quyền coi giá trị đó như giá trị thông thường, vì
applyMaybe (mà sau này là
>>=) đã đảm nhiệm việc kiểm tra xem liệu nó có phải là giá trị
Nothing hoặc
Just.
Cũng theo tinh thần này, ta hãy lập một hàm nhận vào một giá trị với ghi chép gắn kèm, nghĩa là giá trị
(a,String) và một hàm thuộc kiểu
a -> (b,String) rồi đưa giá trị đó vào hàm. Ta sẽ gọi nó là
applyLog. Nhưng vì một giá trị
(a,String) không mang theo ngữ cảnh với khả năng thất bại, nhưng thay vì một ngữ cảnh của giá trị ghi chép bổ sung,
applyLog sẽ đảm bảo rằng ghi chép của giá trị ban đầu không mất đi, mà được nối với ghi chép thuộc giá trị kết quả của hàm. Sau đây là nội dung của
applyLog:
applyLog :: (a,String) -> (a -> (b,String)) -> (b,String) applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog)
Khi ta có một giá trị với một ngữ cảnh và muốn đưa nó vào một hàm, thường ta sẽ cố gắng tách giá trị thực khỏi ngữ cảnh rồi áp dụng hàm lên giá trị và thấy Haskell tự lo được cho ngữ cảnh. Trong monad
Maybe, ta đã kiểm tra xem liệu giá trị có phải là
Just x không, và nếu vậy, thì lấy cái
x đó để áp dụng hàm lên. Trong trường hợp này, rất dễ tìm ra giá trị thực, vì ta đang xét đến một đôi trong đó một phần tử là giá trị còn phần tử kia là nội dung ghi chép. Vì vậy đầu tiên ta chỉ việc lấy giá trị, vốn là
x rồi áp dụng hàm
f lên nó. Ta nhận được một đôi
(y,newLog), trong đó
y là kết quả mới và
newLog là nội dung ghi chép mới. Nhưng nếu ta trả lại kết quả mới này, thì nội dung ghi chép cũ sẽ không được bao gồm trong đó, vì vậy ta cần trả lại một đôi
(y,log ++ newLog). Ta dùng
++ để bổ sung nội dung ghi chép mới tiếp theo ghi chép cũ.
Sau đây là hoạt động của
applyLog.
ghci> (3, "Smallish gang.") `applyLog` isBigGang (False,"Smallish gang.Compared gang size to 9") ghci> (30, "A freaking platoon.") `applyLog` isBigGang (True,"A freaking platoon.Compared gang size to 9")
Kết quả cũng tương tự trước kia, chỉ khác là bây giờ số người trong băng cướp đã có nội dung ghi chép đi kèm với nó, và nội dung này được bao gồm trong kết quả ghi chép. Sau đây là một số ví dụ nữa về cách dùng
applyLog:
ghci> ("Tobin","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length.")) (5,"Got outlaw name.Applied length.") ghci> ("Bathcat","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length")) (7,"Got outlaw name.Applied length")
Bạn đã thấy rằng bên trong lambda,
x chỉ là một chuỗi thường mà không phải là một bộ, và
applyLog đã đảm nhiệm việc bổ sung nội dung ghi chép như thế nào.
#### Monoid đến cứu giúp
[monoid](functors-applicative-functors-and-monoids#monoids)!
Ngay bây giờ,
applyLog nhận các giá trị thuộc kiểu
(a,String), nhưng lý do gì bắt buộc nội dung ghi chép phải là
String? Nó dùng
++ để bổ sung các ghi chép, như vậy sẽ phải hoạt động được với bất kì kiểu danh sách nào chứ không riêng gì danh sách kí tự chứ? Hẳn nhiên rồi. Ta có thể tư nhiên thay đổi kiểu dữ liệu của nó như sau:
applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c])
Bây giờ, nội dung ghi chép là danh sách. Kiểu của các giá trị chứa trong danh sách phải giống như ở danh sách ban đầu, cũng như danh sách được hàm trả lại, nếu không thì ta đã chẳng dùng được
++ để gắn chúng lại với nhau.
Vậy liệu cách này có áp dụng được với các chuỗi byte không nhỉ? Chẳng có lý do gì mà không được. Tuy nhiên, kiểu mà ta đang có trong tay chỉ hoạt động với danh sách. Dường như ta phải lập một
applyLog riêng nữa cho những chuỗi bye. Nhưng khoan đã! Cả danh sách và chuỗi byte đều là những monoid. Vì vậy, chúng đều là thực thể của lớp
Monoid, có nghĩa là chúng đều cho phép dùng hàm
mappend. Và đối với danh sách cũng như chuỗi byte,
mappend được dùng để bổ sung. Hãy xem này:
ghci> [1,2,3] `mappend` [4,5,6] [1,2,3,4,5,6] ghci> B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97] Chunk "chi" (Chunk "huahua" Empty)
Hay đấy! Bây giờ
applyLog của ta có thể hoạt động được với bất kì monoid nào. Ta phải thay đổi kiểu dữ liệu để phản ánh điều đó, cũng như cách tạo lập hàm này, mà cụ thể là thay
++ bằng
mappend:
applyLog :: (Monoid m) => (a,m) -> (a -> (b,m)) -> (b,m) applyLog (x,log) f = let (y,newLog) = f x in (y,log `mappend` newLog)
Vì giá trị đi kèm giờ có thể là bất cứ giá trị monoid nào, nên ta không còn phải hình dung từng bộ như là một giá trị và một ghi chép, mà bây giờ ta có thể hình dung nó như là một giá trị kèm theo một giá trị monoid. Chẳng hạn, ta có thể có một bộ trong đó chứa tên món hàng và giá bán của nó như là giá trị monoid. Ta chỉ việc dùng kiểu newtype tên là
Sum để đảm bảo chắc chắn rằng giá cả được cộng thêm vào khi chọn các món hàng khác nhau. Dưới đây là một hàm để cộng tiền đồ uống vào với tiền bữa ăn mà người cao bồi phải trả:
import Data.Monoid type Food = String type Price = Sum Int addDrink :: Food -> (Food,Price) addDrink "beans" = ("milk", Sum 25) addDrink "jerky" = ("whiskey", Sum 99) addDrink _ = ("beer", Sum 30)
Ta dùng chuỗi kí tự để biểu diễn cho thức ăn và một
Int trong một vỏ bọc
newtype tên
Sum để theo dõi xem từng đồ uống giá bao nhiêu xu. Hãy nhớ lại rằng, việc dùng
mappend với
Sum sẽ trả lại kết quả là những giá trị trong gói bọc được cộng lại với nhau:
ghci> Sum 3 `mappend` Sum 9 Sum {getSum = 12}
Hàm
addDrink rất đơn giản. Nếu ta chọn ăn đỗ, thì nó sẽ trả lại
"milk" cùng với
Sum 25, nghĩa là giá tiền 25 xu được gói trong
Sum. Nếu ta ăn thịt bò khi thì uống rượu uýt-xki và nếu ta ăn bất kì thứ gì khác thì uống bia. Chỉ cần áp dụng hàm này một cách bình thường với đồ ăn thì bây giờ không có gì là hay cả, nhưng dùng
applyLog để đưa tên thức ăn kèm theo giá tiền vào trong hàm này thì rất hay:
ghci> ("beans", Sum 10) `applyLog` addDrink ("milk",Sum {getSum = 35}) ghci> ("jerky", Sum 25) `applyLog` addDrink ("whiskey",Sum {getSum = 124}) ghci> ("dogmeat", Sum 5) `applyLog` addDrink ("beer",Sum {getSum = 35})
Giá của sữa là
25 xu, nhưng nếu ta dùng nó với đỗ có giá
10 xu, thì tổng số tiền phải trả là
35 xu. Bây giờ đã rõ rằng giá trị đi kèm theo không nhất thiết phải là dạng ghi chép, mà có thể là bất cứ giá trị monoid nào và bạn thấy được hai giá trị được kết hợp làm một lại phụ thuộc vào monoid thế nào. Khi ta thao tác với ghi chép, thì chúng được bổ sung thêm, nhưng giờ đây, đối với các số, thì chúng được cộng vào.
Vì giá trị mà
addDrink trả lại là một bộ có kiểu
(Food,Price), nên ta có thể đưa kết quả này vào lại
addDrink, để hàm này báo cho ta rằng nên uống gì kèm theo, và giá tiền sẽ là bao nhiêu. Ta hãy thử xem sao:
ghci> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink ("beer",Sum {getSum = 65})
Việc thêm đồ uống kèm theo món thịt chó sẽ ra là “bia” cùng với
30 xu nữa, tức là
("beer", Sum 35). Và nếu ta dùng
applyLog để đưa kết quả này vào
addDrink, ta thu được bia khác và lần này kết quả là
("beer", Sum 65).
#### Kiểu Writer
Bây giờ khi đã thấy một giá trị kèm theo một monoid đóng vai trò như một giá trị monad, ta hãy kiểm tra thực thể
Monad đối với kiểu của những giá trị như vậy. Module
Control.Monad.Writer có xuất khẩu kiểu
Writer w a cùng với thực thể
Monad của nó và một số hàm hữu ích để thao tác với những giá trị thuộc kiểu này.
Trước hết, ta hãy kiểm tra bản thân kiểu dữ liệu này. Để gắn một monoid vào với một giá trị, ta chỉ việc đặt chúng cùng vào trong một bộ. Kiểu dữ liệu
Writer w a chỉ là một bao gói
newtype cho giá trị này. Định nghĩa của nó rất đơn giản:
newtype Writer w a = Writer { runWriter :: (a, w) }
Nó được gói trong một
newtype do vậy có thể là thực thể của
Monad và cũng vì vậy kiểu của nó được phân biệt hẳn so với một bộ bình thường. Tham số kiểu
a biểu diễn cho kiểu của giá trị còn tham số kiểu
w biểu diễn cho kiểu của giá trị monoid kèm theo.
Thực thể
Monad của nó được định nghĩa như sau:
instance (Monoid w) => Monad (Writer w) where return x = Writer (x, mempty) (Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')
Trước hết, ta hãy kiểm tra
>>=. Cách tạo lập của nó rất giống với
applyLog, chỉ khác là bây giờ bộ đang xét đến được gói trong
newtype
Writer , ta phải tháo gỡ nó ra khi thực hiện khớp mẫu. Ta lấy giá trị
x rồi áp dụng hàm \
f lên nó. Việc làm này cho ta một giá trị
Writer w a và ta dùng một biểu thức
let để khớp mẫu với nó. Ta biểu diễn
y là kết quả mới và dùng
mappend để kết hợp giá trị monoid cũ với cái mới. Ta ghép nó với giá trị kết quả vào trong một bộ rồi gói bộ này bằng constructor
Writer để cho kết quả là một giá trị
Writer thay vì đơn thuần chỉ là một bộ đã được tháo gỡ.
Vậy còn
return thì sao? Nó phải nhận một giá trị rồi đặt giá trị này vào trong một ngữ cảnh tối thiểu mặc định mà vẫn biểu diễn được giá trị đó làm kết quả. Thế một ngữ cảnh như vậy đối với các giá trị
Writer là gì? Nếu muốn giá trị monoid đi kèm càng ít ảnh hưởng đến các giá trị monoid khác càng tốt, thì ta nên dùng
mempty.
mempty được dùng để biểu diễn những giá trị monoid là phần tử trung hòa, như
"" và
Sum 0 hay những chuỗi byte rỗng. Bất kì khi nào dùng
mappend giữa
mempty và một giá trị monoid nào khác, thì kết quả sẽ là giá trị monoid khác đó. Vì vậy, nếu ta dùng
return để tạo một giá trị
Writer rồi dùng
>>= để đưa giá trị đó vào trong một hàm, thì giá trị monoid thu được sẽ chỉ là thứ mà hàm trả lại. Ta hãy dùng
return với số
3 nhiều lần, chỉ có điều là mỗi lần thì xếp nó cặp đôi với một monoid riêng biệt:
ghci> runWriter (return 3 :: Writer String Int) (3,"") ghci> runWriter (return 3 :: Writer (Sum Int) Int) (3,Sum {getSum = 0}) ghci> runWriter (return 3 :: Writer (Product Int) Int) (3,Product {getProduct = 1})
Vì
Writer không có một thực thể
Show, nên ta phải dùng
runWriter để chuyển từ các giá trị
Writer đang xét sang những bộ dữ liệu bình thường, để có thể hiển thị được. Đối với
String, giá trị monoid là chuỗi rỗng. Với
Sum, đó là
0, vì nếu ta cộng 0 với bất kì số nào thì kết quả vẫn không đổi. Đối với
Product, phần tử trung hòa là
1.
Thực thể
Writer không bao gồm cách tạo lập
fail, vì vậy nếu có mẫu cần khớp bị thất bại trong khối lệnh
do, thì
error sẽ được gọi đến.
#### Dùng khối lệnh “do” với Writer
Bây giờ khi đã có thực thể
Monad, ta có thể tự nhiên dùng khối lệnh
do cho các giá trị
Writer. Sẽ rất tiện trong trường hợp ta có một số giá trị
Writer và muốn thao tác chúng. Cũng như với các monad khác, ta có thể coi chúng như những giá trị thường và ngữ cảnh sẽ tự lo cho ta. Trong trường hợp này, tất cả những giá trị monoid đi kèm theo đều được
mappend và do đó được phản ánh trong kết quả cuối cùng. Sau đây là một ví dụ đơn giản của việc sử dụng khối lệnh
do với
Writer để nhân hai số:
import Control.Monad.Writer logNumber :: Int -> Writer [String] Int logNumber x = Writer (x, ["Got number: " ++ show x]) multWithLog :: Writer [String] Int multWithLog = do a <- logNumber 3 b <- logNumber 5 return (a*b)
logNumber nhận một con số rồi tạo nên một giá trị
Writer từ nó. Đối với monoid, ta dùng một danh sách các chuỗi và ta trang bị con số với một chuỗi đơn phần tử chỉ để báo rằng ta có con số như vậy.
multWithLog là một giá trị
Writer mà nhân
3 với
5 rồi đảm bảo rằng những ghi chép kèm theo hai con số này được bao gồm trong ghi chép cuối cùng. Ta dùng
return để biểu thị kết quả
a*b. Vì
return chỉ nhận thứ gì đó rồi đặt nó vào trong ngữ cảnh tối thiểu, nên ta có thể chắc rằng nó không cộng gì thêm vào bản ghi chép. Sau đây là thứ mà ta thấy được khi chạy mã lệnh này:
ghci> runWriter multWithLog (15,["Got number: 3","Got number: 5"])
Đôi khi ta chỉ muốn giá trị monoid nào đó được kèm theo tại một điểm nhất định. Với mục đích này, hàm
tell sẽ hữu dụng. Nó thuộc về lớp
MonadWriter và trong trường hợp
Writer nó nhận một giá trị monoid, như
["This is going on"] và tạo ra một giá trị
Writer để biểu diễn cho giá trị đại diện
() đóng vai trò kết quả, nhưng lại có giá trị monoid gắn kèm theo. Khi ta có một giá trị monad mang kết quả
(), ta không gắn nó vào một biến. Sau đây là
multWithLog nhưng có kèm theo báo cáo phụ thêm:
multWithLog :: Writer [String] Int multWithLog = do a <- logNumber 3 b <- logNumber 5 tell ["Gonna multiply these two"] return (a*b)
Điều quan trọng là để
return (a*b) ở dòng dưới cùng, vì kết quả của dòng lệnh cuối trong khối lệnh
do là kết quả của toàn bộ biểu thức
do này. Nếu ta đưa
tell xuống cuối trong trường hợp này, thì
() sẽ là kết quả của biểu thức
do. Như vậy ta mất đi kết quả của phép nhân. Tuy nhiên khi đó nội dung ghi chép vẫn như vậy. Sau đây là kết quả khi chạy mã lệnh trên:
ghci> runWriter multWithLog (15,["Got number: 3","Got number: 5","Gonna multiply these two"])
#### Bổ sung ghi chép vào trong chương trình
Thuật toán Euclid nhận vào hai con số rồi tìm ước số chung lớn nhất của chúng; nghĩa là số lớn nhất mà hai số ban đầu cùng chia hết. Haskell đã có sẵn hàm
gcd, thực hiện chính xác việc này, nhưng ta hãy tự tay viết hàm đồng thời trang bị cho nó khả năng ghi chép. Sau đây là thuật toán thông thường:
gcd' :: Int -> Int -> Int gcd' a b | b == 0 = a | otherwise = gcd' b (a `mod` b)
Thuật toán này rất đơn giản. Ban đầu, nó kiểm tra xem liệu số thứ hai có bằng 0 hay không. Nếu đúng, kết quả sẽ là số thứ nhất. Nếu không, thì kết quả sẽ là ước số chung lớn nhất của số thứ hai và số dư của phép chia số thứ nhất cho số thứ hai. Chẳng hạn, nếu muốn biết ước số chung lớn nhất giữa 8 và 3 là gì, ta chỉ việc theo thuật toán đã phác thảo ở trên. Vì 3 khác 0, nên ta phải đi tìm ước số chung lớn nhất giữa 3 và 2 (nếu ta chia 8 cho 3 thì số dư sẽ là 2). Tiếp theo, ta tính ước số chung lớn nhất giữa 3 và 2. Vì 2 vẫn chưa bằng 0, nên bây giờ ta có 2 và 1. Số thứ hai chưa bằng 0 nên ta lại thực hiện thuật toán với 1 và 0, vì 2 chia 1 dư 0. Và cuối cùng, khi bây giờ số thứ hai đã bằng 0 rồi, thì kết quả cuối cùng là 1. Ta hãy xem liệu mã lệnh chạy ra có cho kết quả giống như vậy:
ghci> gcd' 8 3 1
Đúng. Rất tốt! Bây giờ, ta muốn trang bị cho kết quả của ta một ngữ cảnh, và ngữ cảnh này là một giá trị monoid đóng vai trò như bản ghi chép. Cũng giống như trước đây, ta sẽ dùng danh sách những chuỗi kí tự làm monoid. Khi đó kiểu của hàm
gcd' mới sẽ là:
gcd' :: Int -> Int -> Writer [String] Int
Việc còn lại là trang bị cho hàm này những giá trị ghi chép. Sau đây là mã lệnh:
import Control.Monad.Writer gcd' :: Int -> Int -> Writer [String] Int gcd' a b | b == 0 = do tell ["Finished with " ++ show a] return a | otherwise = do tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)] gcd' b (a `mod` b)
Hàm này nhận hai giá trị
Int bình thường rồi trả lại một
Writer [String] Int, nghĩa là một
Int kèm theo một ngữ cảnh ghi chép. Trong trường hợp
b bằng
0, thay vì việc chỉ đưa kết quả là
a, ta dùng một biểu thức
do để kết hợp một giá trị
Writer làm kết quả. Đầu tiên, ta dùng
tell để báo rằng ta đã xong và rồi dùng
return để biểu diễn
a là kết quả của khối lệnh
do. Thay vì biểu thức
do này, ta cũng có thể viết như sau:
Writer (a, ["Finished with " ++ show a])
Tuy vậy, tôi nghĩ rằng biểu thức
do thì dễ đọc hơn. Tiếp theo, ta có tình huống khi
b khác
0. Trong trường hợp nay, ta ghi lại rằng ta dùng
mod để tính ra số dư trong phép chia của
a cho
b. Sau đó, dòng lệnh thứ hai trong biểu thức
do chỉ việc gọi
gcd' một cách đệ quy. Hãy nhớ rằng, bây giờ
gcd' cuối cùng đã trả lại một giá trị
Writer, nên hoàn toàn đúng khi viết dòng lệnh
gcd' b (a `mod` b) bên trong một biểu thức
do.
Nếu như tự tay dò theo việc thực thi của hàm mới
gcd' này để xem các ghi chép được bổ sung thế nào là một điều có ích, thì tôi nghĩ rằng sâu xa hơn, ta nên nhìn vào bức tranh tổng thể và coi những ghi chép này là các giá trị với một ngữ cảnh, rồi từ đó hiểu thêm là kết quả cuối cùng sẽ ra sao.
Ta hãy thử với hàm
gcd' mới. Kết quả của nó là một giá trị
Writer [String] Int và nếu ta tháo gỡ giá trị đó khỏi
newtype của nó, ta sẽ thu được một bộ dữ liệu. Phần thứ nhất của bộ là kết quả. Ta hãy xem liệu có ổn không:
ghci> fst $ runWriter (gcd' 8 3) 1
Tốt! Thế còn phần ghi chép? Vì nội dung ghi chép là một danh sách các chuỗi kí tự, nên ta hãy dùng
mapM_ putStrLn để in chúng ra màn hình:
ghci> mapM_ putStrLn $ snd $ runWriter (gcd' 8 3) 8 mod 3 = 2 3 mod 2 = 1 2 mod 1 = 0 Finished with 1
Tôi nghĩ rằng thật tuyệt vời khi ta có thể sửa đổi thuật toán thông dụng thành một thuật toán có khả năng báo cáo quá trình hoạt động của nó, chỉ bằng cách thay đổi những giá trị thường thành giá trị monad và để cho
>>= của
Writer đảm nhiệm nội dung ghi chép cho ta. Có thể thêm cơ chế ghi chép gần như cho hàm nào cũng được. Ta chỉ việc thay thể các giá trị thông thường bằng những giá trị
Writer khi cần và thay cách áp dụng hàm thông thường bằng
>>= (hoặc các biểu thức
do nếu cách này dễ đọc hơn).
#### Cách không hiệu quả để tạo dựng danh sách
Khi dùng monad
Writer, bạn phải cẩn thận trong việc dùng monoid nào, vì việc dùng danh sách đôi khi có thể trở nên rất chậm chạp. Đó là bởi danh sách dùng đến
++ để
mappend, mà việc dùng
++ để bổ sung phần tử vào phía cuối danh sách sẽ chậm nếu danh sách rất dài.
Trong hàm
gcd', việc ghi chép được thực hiện rất nhanh vì cách bổ sung danh sách rút cục sẽ như sau:
a ++ (b ++ (c ++ (d ++ (e ++ f))))
Danh sách là loại cấu trúc dữ liệu được tạo dựng từ trái sang phải, và cách làm trên là hiệu quả, vì ban đầu ta hoàn thành việc tạo dựng phần bên trái của danh sách rồi sau đó mới bổ sung một danh sách dài hơn từ bên phía phải. Nhưng nếu ta không cẩn thận, việc dùng monad
Writer có thể sẽ tạo ra phép bổ sung danh sách trông như sau:
((((a ++ b) ++ c) ++ d) ++ e) ++ f
Cách tính toán này kết hợp về bên phía trái thay vì về phía phải. Đây là cách không hiệu quả vfi mỗi lần muốn nối phần bên phải vào phần bên trái, thì phần bên trái danh sách lại phải được tạo dựng từ đầu!
Hàm sau đây hoạt động giống như
gcd', chỉ khác là nó ghi chép các thứ theo chiều đảo ngược. Trước hết, nó tạo ra ghi chép cho phần còn lại của thủ tục rồi bổ sung vào cuối bản ghi chép.
import Control.Monad.Writer gcdReverse :: Int -> Int -> Writer [String] Int gcdReverse a b | b == 0 = do tell ["Finished with " ++ show a] return a | otherwise = do result <- gcdReverse b (a `mod` b) tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)] return result
Trước hết, việc đệ quy được thực hiện, và giá trị kết quả được gắn với
result. Tiếp theo là bổ sung bước hiện hành vào bản ghi, nhưng bước hiện hành sẽ đưa vào cuối ghi chép tạo bởi đệ quy. Sau cùng, kết quả của đệ quy được hiển thị như là kết quả cuối cùng. Sau đây là hoạt động của hàm mới viết:
ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3) Finished with 1 2 mod 1 = 0 3 mod 2 = 1 8 mod 3 = 2
Nó rất kém hiệu quả vì kết cục là phải dùng
++ theo hướng kết hợp trái thay vì kết hợp phải.
#### Danh sách hiệu
Vì đôi lúc danh sách có thể kém hiệu quả khi được liên tiếp bổ sung theo cách nói trước, nên tốt nhất là ta dùng một cấu trúc dữ liệu luôn cho phép bổ sung một cách hiệu quả. Một cấu trúc dữ liệu như vậy là danh sách hiệu. Một danh sách hiệu cũng giống như danh sách, chỉ hơn ở chỗ nó là một hàm nhận một danh sách rồi gắn liền một danh sách khác về phía trước nó. Tương ứng với một dánh sách như
[1,2,3], danh sách hiệu sẽ là hàm
\xs -> [1,2,3] ++ xs. Một danh sách rỗng thông thường là
[], còn danh sách hiệu rỗng sẽ là hàm
\xs -> [] ++ xs.
Điều hay ở danh sách hiệu là ở chỗ chúng cho phép bổ sung một cách hiệu quả. Khi ta bổ sung hai danh sách thông thường với
++, máy sẽ phải thực hiện duyệt từ đầu đến cuối của danh sách bên trái dấu
++ rồi mới gắn danh sách còn lại tiếp vào đó. Nhưng sẽ ra sao nếu ta thực hiện cách danh sách hiệu rồi biểu diễn các danh sách được xét dưới dạng các hàm? À, khi đó việc kết nối hai danh sách hiệu sẽ được thực hiện như sau:
f `append` g = \xs -> f (g xs)
Hãy nhớ rằng,
f và
g là những hàm nhận các danh sách và rồi chèn thêm nội dung nào đó vào trước những danh sách này. Chẳng hạn, nếu
f là hàm
("dog"++) (chỉ là một cách viết khác cho
\xs -> "dog" ++ xs) và
g là hàm
("meat"++), thì
f `append` g tạo nên một hàm mới tương đương với hàm sau đây:
\xs -> "dog" ++ ("meat" ++ xs)
Ta đã nối liền hai danh sách hiệu với nhau, đơn giản chỉ bằng cách tạo một hàm mới để áp dụng một danh sách hiệu với một danh sách nào đó, tiếp đến là danh sách còn lại.
Ta hãy tạo một vỏ bọc
newtype cho danh sách hiệu, để có thể dễ dàng chuyển những thực thể monoid đến những danh sách này:
newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }
Kiểu dữ liệu mà ta bọc là
[a] -> [a] vì một danh sách hiệu chỉ đơn giản là một hàm nhận vào một danh sách rồi trả lại một danh sách khác. Thật dễ chuyển đổi qua lại giữa danh sách thông thường và danh sách hiệu:
toDiffList :: [a] -> DiffList a toDiffList xs = DiffList (xs++) fromDiffList :: DiffList a -> [a] fromDiffList (DiffList f) = f []
Để biến một danh sách thường thanh danh sách hiệu, ta chỉ cần thực hiện việc mà ta đã làm trước đây rồi biến nó thành hàm để đặt danh sách lên đầu của danh sách khác.Vì một danh sách hiệu là một hàm để đặt một thứ nào đó lên phía đầu của một danh sách khác, nên nếu ta muốn thứ nêu trên, thì cần phải áp dụng hàm đối với một danh sách rỗng!
Sau đây là thực thể
Monoid:
instance Monoid (DiffList a) where mempty = DiffList (\xs -> [] ++ xs) (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))
Lưu ý rằng đối với danh sách,
mempty đơn giản là hàm
id còn
mappend thực ra chính là phép hàm hợp. Ta hãy xem nó hoạt động ra sao:
ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3]) [1,2,3,4,1,2,3]
Đỉnh thật! Bây giờ ta có thể tăng hiệu quả của hàm
gcdReverse vừa viết bằng cách dùng danh sách hiệu thay vì danh sách thường:
import Control.Monad.Writer gcd' :: Int -> Int -> Writer (DiffList String) Int gcd' a b | b == 0 = do tell (toDiffList ["Finished with " ++ show a]) return a | otherwise = do result <- gcd' b (a `mod` b) tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]) return result
Ta chỉ phải thay đổi kiểu của monoid từ
[String] sang thành
DiffList String rồi sau đó khi dùng
tell, thì chuyển đổi danh sách thường thành danh sách hiệu bằng
toDiffList. Hãy xem liệu bản ghi chép có được hợp lại trọn vẹn hay không:
ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34 Finished with 2 8 mod 2 = 0 34 mod 8 = 2 110 mod 34 = 8
Ta viết
gcdReverse 110 34, sau đó dùng
runWriter để tháo gỡ nó khỏi
newtype, rồi áp dụng
snd cho kết quả chỉ để lấy nội dung ghi chép, tiếp theo áp dụng
fromDiffList để chuyển đổi nó thành một danh sách thông thường và cuối cùng là in toàn bộ ra màn hình.
#### So sánh hiệu năng
Để hình dung được danh sách hiệu giúp nâng cao hiệu năng chạy chương trình thêm bao nhiêu, ta hãy xét hàm sau, chỉ đơn thuần là đếm ngược từ một số về 0, nhưng tạo ra bản ghi theo chiều ngược lại, giống như
gcdReverse, như vậy các con số trong nội dung ghi chép sẽ được đếm tăng dần:
finalCountDown :: Int -> Writer (DiffList String) () finalCountDown 0 = do tell (toDiffList ["0"]) finalCountDown x = do finalCountDown (x-1) tell (toDiffList [show x])
Nếu ta đưa vào hàm này số
0, thì nó sẽ ghi lại chính số đó. Với bất kì số nào khác, ban đầu nó sẽ đếm các số trước, từ
0 và bổ sung những số đó vào nội dung ghi chép. Vì vậy, nếu ta áp dụng
finalCountDown đối với
100, thì chuỗi
"100" sẽ đứng cuối cùng trong nội dung ghi chép.
Dù sao, nếu bạn tải hàm này trong GHCi rồi áp dụng nó cho một số lớn, như
500000, bạn sẽ thấy nó nhanh chóng đếm từ
0 trở lên:
ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000 0 1 2 ...
Tuy nhiên, nếu bạn thay danh sách hiệu bằng danh sách thường, như sau:
finalCountDown :: Int -> Writer [String] () finalCountDown 0 = do tell ["0"] finalCountDown x = do finalCountDown (x-1) tell [show x]
Rồi bảo GHCi bắt đầu đếm:
ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000
Thì bạn sẽ thấy rằng việc đếm thực sự rất chậm.
Dĩ nhiên, đây không phải là cách đúng đắn và khoa học để kiểm tra xem chương trình đang xét chạy nhanh bao nhiêu, nhưng qua ví dụ này, ta có thể thấy được rằng việc dùng danh sách hiệu bắt đầu cho ra kết quả tức khắc, còn danh sách thường sẽ quá lâu.
Ồ, mà bây giờ thì bài hát Final Countdown do ban nhạc Europe trình diễn đã để lại dấu ấn trong tâm trí bạn rồi!
### Reader? Hừ, đùng đùa thế nữa!
Trong
[chương nói về các áp dụng (applicative)](functors-applicative-functors-and-monoids), ta đã thấy rằng kiểu hàm,
(->) r là một thực thể của
Functor. Việc ánh xạ một hàm
f lên một hàm
g sẽ tạo ra một hàm nhận vào thứ mà
g nhận vào, rồi áp dụng
g đối với nó, tiếp theo áp dụng
f đối với kết quả thu được. Như vậy về cơ bản là ta đang tạo một hàm mới giống như
g, chỉ khác là trước khi trả lại kết quả, thì lại cho
f áp dụng lên kết quả đó. Chẳng hạn:
ghci> let f = (*5) ghci> let g = (+3) ghci> (fmap f g) 8 55
Ta cũng đã thấy rằng các hàm là các functor áp dụng. Nó cho phép ta thao tác trên kết quả cuối cùng của các hàm, như thể ta đã có trong tay kết quả đó rồi. Sau đây là một ví dụ:
ghci> let f = (+) <$> (*2) <*> (+10) ghci> f 3 19
Biểu thức
(+) <$> (*2) <*> (+10) tạo lập một hàm để nhận vào một số, đưa số đó cho
(*2) và
(+10) rồi cộng các kết quả lại. Chẳng hạn, nếu ta áp dụng hàm này cho
3, nó sẽ áp dụng cả
(*2) và
(+10) cho
3, kết quả là
6 và
13. Sau đó, nó gọi
(+) với
6 và
13 để có được kết quả
19.
Kiểu hàm
(->) r không chỉ là một functor và functor áp dụng, mà nó còn là một monad. Cũng như các giá trị monad khác mà ta đã bắt gặp, một hàm cũng có thể được coi là giá trị kèm theo ngữ cảnh. Ngữ cảnh của hàm thể hiện ở chỗ giá trị đó vẫn chưa xuất hiện và ta phải áp dụng hàm này đối với thứ gì đó để thu được giá trị kết quả.
Vì đã quen với cách mà hàm hoạt động như những functor và functor áp dụng, nên ta hãy đi thẳng vảo vấn đề và xem thực thể
Monad của chúng trông ra sao. Thực thể này nằm ở
Control.Monad.Instances và nó trông như sau:
instance Monad ((->) r) where return x = \_ -> x h >>= f = \w -> f (h w) w
Ta đã thấy cách tạo lập
pure đối với các hàm, và
return khá giống với
pure như thế nào. Nó nhận một giá trị rồi đặt nó vào trong ngữ cảnh tối thiểu mà luôn có kết quả là giá trị này. Và cách làm duy nhất khiến cho hàm luôn có kết quả là một giá trị nhất định, đó làm khiến cho hàm này phớt lờ các tham số được cung cấp.
Cách tạo lập
>>= có vẻ khá bí hiểm, song thực ra chưa đến nỗi như vậy. Khi ta dùng
>>= để đưa một giá trị monad vào trong một hàm, thì kết quả luôn là một giá trị monad. Như vậy trong trường hợp này, khi ta đưa một hàm vào cho hàm khác, thì kết quả cũng là một hàm. Điều này giải thích tại sao mà kết quả xuất hiện là lambda. Tất cả phần thiết lập
>>= tới giờ đều có sự phân tách nhất định giữa kết quả và giá trị monad, sau đó áp dụng hàm
f đối với kết quả đó. Ở đây điều tương tự cũng diễn ra. Để lấy được kết quả từ một hàm, ta phải áp dụng hàm này cho một thứ gì đó, và đó là nguyên nhân mà ta đã viết
(h w) để lấy kết quả từ hàm rồi áp dụng
f đối với kết quả này.
f trả lại một giá trị monad, trong trường hợp này là một hàm, vì vậy ta cũng cáp dụng nó cho
w.
Nếu đến giờ bạn vẫn chưa nắm được cách hoạt động của
>>=, thì đừng lo, vì bằng những ví dụ chúng ta sẽ thấy được đây là một monad đơn giản chừng nào. Sau đây là một biểu thức
do trong đó tận dụng monad này:
import Control.Monad.Instances addStuff :: Int -> Int addStuff = do a <- (*2) b <- (+10) return (a+b)
Cách này cũng giống như biểu thức áp dụng mà ta đã viết trước đây, chỉ khác là bây giờ nó dựa trên các hàm monad. Một biểu thức
do luôn cho kết quả là một giá trị monad, và với biểu thức này cũng chẳng khác gì. Kết quả của giá trị monad này là một hàm. Điều xảy ra ở đây là hàm này nhận một số rồi cho
(*2) áp dụng với số đó và kết quả là
a.
(+10) cũng được áp dụng với số ban đầu (mà ta áp dụng
(*2) với), lần này kết quả là
b.
return, cũng như ở các monad khác, không có hiệu ứng gì khác ngoài việc khiến cho một giá trị monad biểu diễn một kết quả nào đó. Nó biểu diễn
a+b là kết quả của hàm đang xét. Nếu chạy thử, ta thu được kết quả giống như trước:
ghci> addStuff 3 19
Trong trường hợp này, cả hai
(*2) và
(+10) đều được áp dụng đối với số
3.
return (a+b) cũng làm vậy, nhưng nó phớt lờ đi và luôn biểu diễn kết quả là
a+b. Bởi thế, monad hàm còn được gọi là monad đọc (reader). Tất cả các hàm loại này đều đọc từ một nguồn dữ liệu chung. Để minh họa điều này rõ hơn, ta có thể viết lại
addStuff như sau:
addStuff :: Int -> Int addStuff x = let a = (*2) x b = (+10) x in a+b
Ta thấy rằng monad đọc cho phép coi các hàm như là những giá trị kèm theo ngữ cảnh. Ta có thể giả như đã biết rằng các hàm đó trả lại thứ gì rồi. Nó làm được điều này bằng cách kết dính các hàm lại làm một rồi đưa tham số của hàm đó tất tất cả những hàm dính cùng. Như vậy, nếu ta có nhiều hàm cùng khuyết mất một tham số và cùng phải được áp dụng với một giá trị, thì ta có thể dùng monad đọc để kết xuất các giá trị tương lai từ những hàm này và cách tạo lập của
>>= sẽ đảm bảo rằng mọi việc được thực hiện đúng.
### Các đại lượng mang trạng thái
Haskell là một ngôn ngữ lập trình thuần túy và bởi vậy, chương trình ta viết ra được cấu thành từ các hàm mà không thể thay đổi trạng thái toàn cục, hoặc thay đổi các biến, chúng chỉ có thể thực hiện những phép tính và trả lại kết quả. Mặt hạn chế này thực ra lại khiến cho việc tư duy về chương trình trở nên dễ dàng hơn, vì nó cho phép ta khỏi phải lo lắng về giá trị của từng biến tại một thời điểm nhất định. Tuy nhiên, một số bài toán bản thân chúng đã mang tính trạng thái, theo nghĩa là chúng dựa trên một trạng thái nào đó vốn thay đổi theo thời gian. Dù đó không phải là khó khăn đáng kể đối với Haskell, nhưng vẫn có thể gây nhàm chán khi phải lập mô hình. Vì vậy, Haskell có một tính năng gọi tên là monad trạng thái, khiến cho việc xử lý các bài toán trạng thái trở nên nhẹ nhàng trong khi vẫn giữ được nét đẹp và thuần túy trong lập trình.
[Khi xử lý các số ngẫu nhiên](input-and-output#randomness), ta đã làm việc với những hàm nhận tham số là bộ phát sinh số ngẫu nhiên rồi trả lại một số ngẫu nhiên cùng bộ phát sinh mới. Nếu ta muốn phát sinh nhiều số ngẫu nhiên, ta luôn phải dùng bộ phát sinh ngẫu nhiên mà hàm trước đó đã trả lại cùng với kết quả. Khi lập một hàm nhận một
StdGen rồi mô phỏng việc tung đồng xu ba lần dựa theo bộ phát sinh đó, thì ta đã phải viết mã lệnh sau:
threeCoins :: StdGen -> (Bool, Bool, Bool) threeCoins gen = let (firstCoin, newGen) = random gen (secondCoin, newGen') = random newGen (thirdCoin, newGen'') = random newGen' in (firstCoin, secondCoin, thirdCoin)
Hàm này nhận một bộ phát sinh
gen rồi
random gen trả lại một giá trị
Bool đi cùng với một bộ phát sinh mới. Để tung đồng xu thứ hai, ta đã dùng một bộ phát sinh mới, và cứ như vậy. Trong đa số các ngôn ngữ lập trình khác, ta đã chẳng phải trả lại một bộ phát sinh mới đi cùng số ngẫu nhiên. Ta chỉ việc sửa lại bộ phát sinh hiện có! Nhưng vì Haskell mang tính thuần túy, nên ta không thể làm điều đó, vì thế ta đã phải lấy trạng thái nào đó, tạo ra một kết quả và một trạng thái mới, rồi dùng trạng thái mới để phát sinh những kết quả mới.
Bạn có thể đã nghĩ rằng để tự tránh khỏi những tính toán với trạng thái theo cách làm này, thì ta phải từ bỏ tính thuần khiết của Haskell. À, không nhất thiết vậy, vì vẫn có một monad đặc biệt, gọi là monad trạng thái để giúp ta đảm nhiệm tất cả những trạng thái mà không xâm phạm đến tính thuần khiết và vì vậy lập trình Haskell rất tuyệt.
Như vậy, để giúp ta hiểu rõ hơn khái niệm về đại lượng có trạng thái, hãy tiến thêm một bước nữa bằng cách cho những đại lượng này một kiểu dữ liệu. Ta sẽ nói rằng một đại lượng có trạng thái là một hàm nhận vào một trạng thái nào đó rồi trả lại một giá trị cùng với một trạng thái mới. Hàm đó sẽ phải có kiểu sau đây:
s -> (a,s)
s là kiểu của trạng thái còn
a là kết quả của những phép tính có trạng thái.
x = 5trong một ngôn ngữ mệnh lệnh, nó sẽ thường đưa giá trị
5cho biến
xvà bản thân đại lượng này cũng có giá trị
5như một biểu thức. Nếu bạn xét trên quan điểm lập trình hàm, thì bạn có thể coi phép gán như một hàm nhận vào một trạng thái (nghĩa là, tất cả những biến đã được gán trước đó) rồi trả lại một kết quả (trong trường hợp này là
5) và một trạng thái mới, vốn là tất cả những ánh xạ đến biến trước đó, và thêm vào biến mới gán.
Đại lượng trạng thái này, một hàm nhận vào một trạng thái và trả lại một kết quả cùng một trạng thái mới, cũng có thể được coi là một giá trị kèm ngữ cảnh. Giá trị này là kết quả, còn ngữ cảnh là thứ mà ta phải cung cấp cho một trạng thái ban đầu mới thu được kết quả đó, và ngoài việc có được kết quả ta cũng có một trạng thái mới.
#### Ngăn xếp và những khối đá
Giả dụ ta cần phải mô phỏng một ngăn xếp. Bạn có ngăn xếp với các thứ chồng lên nhau mà có thể chất từng thứ lên đỉnh ngăn xếp hoặc lấy từng thứ khỏi đỉnh ngăn xếp. Khi bạn chất một thứ lên đỉnh ngăn xếp thì ta gọi là “đẩy” (push) vào ngăn xếp, còn khi lấy một thứ khỏi đỉnh ngăn xếp thì gọi là “bung” (pop). Nếu muốn lấy được thứ ở đáy ngăn xếp, bạn phải bung tất cả các thứ bên trên nó.
Ta sẽ dùng một danh sách để biểu diễn cho ngăn xếp và phần tử đầu danh sách sẽ là đỉnh của ngăn xếp. Để giúp giải quyết nhiệm vụ sắp tới, ta sẽ lập hai hàm:
pop và
push.
pop sẽ lấy một ngăn xếp, bung ra một phần tử và trả lại kết quả là phần tử này cùng với một ngăn xếp mới khuyết mất phần tử đó.
push sẽ nhận một phần tử và một ngăn xếp rồi đẩy phần tử đó vào ngăn xếp. Hàm này sẽ trả lại kết quả là
() và một ngăn xếp mới. Xem này:
type Stack = [Int] pop :: Stack -> (Int,Stack) pop (x:xs) = (x,xs) push :: Int -> Stack -> ((),Stack) push a xs = ((),a:xs)
Ta đã để kết quả là
() khi đẩy vào ngăn xếp, bởi vì việc đẩy phần tử vào danh sách thì không có một giá trị kết quả quan trọng nào, nhiệm vụ chính của nó là làm thay đổi ngăn xếp. Lưu ý cách mà ta chỉ việc áp dụng tham số thứ nhất của
push, ta có một đại lượng trạng thái.
pop thì đã sẵn là một đại lượng trạng thái, căn cứ vào kiểu của nó.
Ta hãy dùng các hàm này để viết một đoạn mã lệnh ngắn để mô phỏng một ngăn xếp. Ta sẽ lấy một ngăn xếp, đẩy
3 vào, rồi bung hai phần tử ra, chỉ để thử cho vui. Sau đây là mã lệnh:
stackManip :: Stack -> (Int, Stack) stackManip stack = let ((),newStack1) = push 3 stack (a ,newStack2) = pop newStack1 in pop newStack2
Ta lấy một
stack rồi thực hiện
push 3 stack, kết quả thu được là một bộ. Phần đầu của bộ là một
() còn phần thứ hai là một ngăn xếp mới mà ta gọi là
newStack1. Sau đó, ta bung một con số từ
newStack1, kết quả là một số
a (chính là
3) mà ta vừa đẩy vào, cùng một ngăn xếp mới mà ta gọi là
newStack2. Sau đó, ta bung một con số khỏi
newStack2 và nhận được một số tên là
b cùng một
newStack3. Ta trả lại một bộ chứa số đó và ngăn xếp mới. Hãy thử chạy mã lệnh xem:
ghci> stackManip [5,8,2,1] (5,[8,2,1])
Tuyệt, kết quả là
5 còn ngăn xếp mới là
[8,2,1]. Lưu ý rằng
stackManip bản thân nó là một đại lượng trạng thái ra sao. Ta đã lấy một loạt những đại lượng trạng thái rồi kết dính chúng với nhau. Hừm, nghe có vẻ quen quen.
Đoạn mã lệnh
stackManip trên phần nào thật tẻ nhạt vì ta phải tự đưa trạng thái vòa cho mỗi đại lượng trạng thái, và lưu chúng lại rồi đưa nó vào đại lượng trạng thái tiếp theo. Chẳng phải sẽ hay hơn nếu, thay vì phải đưa ngăn xếp vào cho từng hàm, ta có thể viết như sau:
stackManip = do push 3 a <- pop pop
À, dùng monad trạng thái sẽ cho phép ta thực hiện đúng điều này. Với monad trạng thái, ta sẽ có thể nhận các đại lượng trạng thái, như ở đây, và dùng chúng mà không phải tự quản lý trạng thái.
#### Monad State
Module
Control.Monad.State cung cấp một
newtype để bọc các đại lượng trạng thái. Sau đây là lời định nghĩa của nó:
newtype State s a = State { runState :: s -> (a,s) }
State s a là một đại lượng trạng thái để thao tác trên trjangthasi thuộc kiểu
s và có một kết quả thuộc kiểu
a.
Bây giờ, khi đã thấy được các đại lượng trạng thái là gì rồi, và chúng thậm chí có thể được hình dung như giá trị kèm ngữ cảnh ra sao, ta hãy kiểm tra thực thể
Monad của chúng:
instance Monad (State s) where return x = State $ \s -> (x,s) (State h) >>= f = State $ \s -> let (a, newState) = h s (State g) = f a in g newState
Trước hết ta hãy xét
return. Mục đích của ta khi dùng
return là nhận một giá trị rồi tạo một đại lượng trạng thái luôn có kết quả là giá trị này. Đó là lý do mà ta lập một lambda
\s -> (x,s). Ta luôn biểu diễn
x như là kết quả của đại lượng trạng thái và trạng thái này luôn được giữ không đổi, vì
return phải đặt một giá trị vào trong một ngữ cảnh tối thiểu. Vì vậy
return sẽ làm cho một đại lượng trạng thái vốn biểu diễn cho một giá trị nhất định làm kết quả và giữ cho trạng thái không thay đổi.
Thế còn về
>>=? À, kết quả của việc đưa một đại lượng trạng thái vào một hàm bằng
>>= thì phải là một đại lượng trạng thái, nhỉ? Vậy ta hãy bắt đầu bằng gói bọc
newtype
State rồi viết tiếp một lambda. Cái lambda này sẽ là đại lượng trạng thái mới của ta. Nhưng điều gì đang diễn ra trong nó? À, bằng cách nào đó ta phải kết xuất giá trị kết quả từ đại lượng trạng thái thứ nhất. Vì ta hiện giờ đang ở trong một đại lượng trạng thái, nên ta có thể cho đại lượng trạng thái
h một đại lượng trạng thái
s của ta, và điều này dẫn đến một cặp gồm kết quả và một trạng thái mới:
(a, newState). Đến giờ, mỗi lần khi lập ra
>>=, một khi đã kết xuất được kết quả từ giá trị monad thì ta áp dụng hàm
f đối với nó để thu được giá trị monad mới. Trong
Writer, sau khi làm điều này và thu được giá trị monad mới, ta vẫn phải đảm bảo rằng ngữ cảnh được để ý đến bằng cách
mappend giá trị monoid cũ với cái mới. Ở đây, ta viết
f a và thu được một đại lượng trạng thái mới là
g. Bây giờ khi đã có một đại lượng trạng thái mới và một trạng thái mới (có tên
newState), ta chỉ việc áp dụng đại lượng trạng thái
g đó cho
newState. Kết quả là một bộ gồm kết quả cuối cùng và trạng thái cuối cùng!
Như vậy với
>>=, ta đã dính liền hai đại lượng với nhau, chỉ có điều là đại lượng thứ hai được giấu trong một hàm có nhiệm vụ nhận kết quả từ đại lượng thứ nhất. Vì
pop và
push đều đã là các đại lượng trạng thái, nên ta dễ dàng gói chúng vào trong một vỏ bọc
State. Xem này:
import Control.Monad.State pop :: State Stack Int pop = State $ \(x:xs) -> (x,xs) push :: Int -> State Stack () push a = State $ \xs -> ((),a:xs)
pop đã là một đại lượng trạng thái còn
push nhận một
Int rồi trả lại một đại lượng trạng thái. Bây giờ ta có thể viết lại ví dụ trước, trong đó đẩy
3 vào ngăn xếp rồi bung ra hai con số, như sau:
import Control.Monad.State stackManip :: State Stack Int stackManip = do push 3 a <- pop pop
Bạn đã thấy việc ta dính liền một phép đẩy và hai phép bung vào cùng một đại lượng trạng thái chưa? Khi tháo gỡ nó từ vỏ bọc
newtype ta thu được một hàm mà có thể cung cấp cho nó một trạng thái ban đầu nào đó:
ghci> runState stackManip [5,8,2,1] (5,[8,2,1])
Ta không phải buộc cái
pop thứ hai vào cho
a vì không hề sử dụng cái
a đó chút nào. Vì vậy ta đã có thể viết lại mã lệnh như sau:
stackManip :: State Stack Int stackManip = do push 3 pop pop
Khá hay. Nhưng sẽ ra sao nếu ta muốn làm thế này: bung một số ra khỏi ngăn xếp rồi xem liệu số đó có bằng
5, nếu đúng thì đẩy trở lại ngăn xếp và dừng chương trình; còn nếu không phải
5, thì đẩy
3 và
8 trở lại? Ồ, đây là đoạn mã lệnh:
stackStuff :: State Stack () stackStuff = do a <- pop if a == 5 then push 5 else do push 3 push 8
Cách này khá trực tiếp. Ta hãy chạy nó với một ngăn xếp ban đầu.
ghci> runState stackStuff [9,0,2,1,0] ((),[8,3,0,2,1,0])
Hãy nhớ rằng, các biểu thức
do cho kết quả là những giá trị monad và với monad
State, thì một biểu thức
do cũng là một hàm trạng thái. Vì
stackManip và
stackStuff là các đại lượng trạng thái thông thường, nên ta có thể gắn chúng lại để tạo thành những đại lượng trạng thái tiếp theo.
moreStack :: State Stack () moreStack = do a <- stackManip if a == 100 then stackStuff else return ()
Nếu như kết quả của
stackManip trên ngăn xếp hiện thời bằng
100, thì ta chạy
stackStuff, còn nếu không thì ta không làm gì cả.
return () chỉ để giữ nguyên trạng thái và không làm gì cả.
Module
Control.Monad.State cung cấp một lớp có tên
MonadState; lớp này có hai hàm hữu ích là
get và
put. Đối với
State, hàm
get được thiết lập như sau:
get = State $ \s -> (s,s)
Như vậy nó chỉ lấy trạng thái hiện thời rồi thể hiện nó dưới dạng kết quả. Hàm
put nhận một trạng thái nào đó rồi lập một hàm trạng thái để thay thế trạng thái hiện thời:
put newState = State $ \s -> ((),newState)
Như vậy bằng những hàm này, ta có thể xem ngăn xếp hiện thời gồm có gì hoặc có thể thay thế nó bằng cả một ngăn xếp khác. Chẳng hạn:
stackyStack :: State Stack () stackyStack = do stackNow <- get if stackNow == [1,2,3] then put [8,3,1] else put [9,2,1]
Cũng cần phải kiểm tra xem kiểu dữ liệu của
>>= sẽ là gì nếu nó chỉ làm việc đối với các giá trị
State:
(>>=) :: State s a -> (a -> State s b) -> State s b
Bạn đã thấy rằng kiểu của trạng thái
s vẫn giữ nguyên trong khi kiểu của kết quả thì thay đổi từ
a sang
b rồi chứ? Điều này có nghĩa rằng ta có thể gắn nhiều đại lượng trạng thái có kết quả thuộc những kiểu khác nhau nhưng kiểu của trạng thái phải giữ nguyên. Tại sao phải vậy? Ồ, chẳng hạn, đối với
Maybe, thì
>>= có kiểu sau:
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Việc bản thân monad,
Maybe, không thay đổi là có lý. Sẽ không có lý gì khi dùng
>>= giữa hai monad riêng biệt. Ồ, đối với monad trạng thái, thì thực ra monad này là
State s, vì vậy nếu
s khác đi, thì ta đã dùng
>>= giữa hai monad riêng biệt.
#### Sự ngẫu nhiên monad trạng thái
Ở phần đầu của mục này, ta đã thấy được việc phát sinh các số có thể rất lủng củng vì mỗi hàm ngẫu nhiên nhận một generator rồi trả lại một số ngẫu nhiên kèm theo một bộ phát sinh mới, vốn sau đó dược dùng thay cho bộ cũ nếu ta muốn phát sinh một số ngẫu nhiên khác. The monad trạng thái giúp cho việc xử lý dễ hơn nhiều.
Hàm
random trong
System.Random có kiểu dữ liệu sau:
random :: (RandomGen g, Random a) => g -> (a, g)
Điều này có nghĩa là nó nhận một bộ phát sinh ngẫu nhiên rồi tạo ra một số ngẫu nhiên cùng một bộ phát sinh mới. Ta có thể thấy rằng nó là một đại lượng trạng thái, vì vậy có thể bọc nó vào trong constructor
newtype
State rồi dùng nó như một giá trị monad, theo đó việc truyền trạng thái được thực hiện giúp ta:
import System.Random import Control.Monad.State randomSt :: (RandomGen g, Random a) => State g a randomSt = State random
Như vậy nếu bây giờ ta muốn tung ba đồng xu (
True là sấp,
False là ngửa) ta chỉ cần viết như sau:
import System.Random import Control.Monad.State threeCoins :: State StdGen (Bool,Bool,Bool) threeCoins = do a <- randomSt b <- randomSt c <- randomSt return (a,b,c)
Bây giờ
threeCoins là một đại lượng trạng thái và sau khi nhận một bộ phát sinh ngẫu nhiên ban đầu, hàm đó truyền bộ phát này cho
randomSt đầu tiên, đến lượt nó lại tạo ra một số cùng một bộ phát sinh mới, vốn được truyền đến hàm tiếp theo, rồi cứ như vậy. Ta dùng
return (a,b,c) để biểu diễn
(a,b,c) làm kết quả mà không thay đổi bộ phát sinh gần nhất. Hãy thử chạy mã lệnh này:
ghci> runState threeCoins (mkStdGen 33) ((True,False,True),680029187 2103410263)
Hay rồi. Thực hiện những việc kiểu như thế này luôn yêu cầu phải giữ một rạng thái nào đó giữa các bước thao tác đã trở nên đỡ phiền toái hơn!
### Lỗi sai
Đến giờ ta đã biết rằng
Maybe được dùng để thêm vào các giá trị một ngữ cảnh chứa thất bại khả dĩ. Một giá trị có thể là
Just something hoặc
Nothing. Dù chúng có ích, nhưng khi ta có
Nothing, thì tất cả những gì ta biết được là có lỗi nào đó đã xảy ra, nhưng không còn cách nào để moi thêm thông tin gì về loại lỗi đó là gì, hoặc tại sao tính toán lại thất bại.
Ngược lại, kiểu
Either e a cho phép ta kèm thêm vào trong các giá trị hiện có, một ngữ cảnh chứa thất bại có thể xảy ra, trong khi vẫn có thể gắn những giá trị vào trong thất bại này, để chúng có thể mô tả được nguyên nhân hỏng hóc hoặc cung cấp những thông tin khác về thất bại này. Một giá trị
Either e a có thể hoặc là một giá trị
Right, để chỉ đáp số đúng hay sự thành công, hoặc một giá trị
Left, để chỉ thất bại. Chẳng hạn:
ghci> :t Right 4 Right 4 :: (Num t) => Either a t ghci> :t Left "out of cheese error" Left "out of cheese error" :: Either [Char] b
Đây gần như là một dạng
Maybe được cải tiến, vì vậy để nó là một monad thật hợp lý, vì cũng có thể coi nó như một giá trị với ngữ cảnh kèm theo để chỉ thất bại khả dĩ, chỉ khác là bây giờ có một giá trị cùng với cả lỗi nữa.
Thực thể
Monad của nó thì giống như với
Maybe và bạn có thể tìm thấy nó trong
Control.Monad.Error:
instance (Error e) => Monad (Either e) where return x = Right x Right x >>= f = f x Left err >>= f = Left err fail msg = Left (strMsg msg)
return, như thường lệ, nhận một giá trị rồi đặt nó vào trong một ngữ cảnh tối thiểu mặc định. Nó bọc giá trị đang xét vào trong constructor
Right vì ta đang dùng
Right để biểu diễn một đại lượng tính toán thành công trong đó có một kết quả. Điều này rất giống với
return của
Maybe.
Phép
>>= kiểm tra hai trường hợp khả dĩ:
Left và
Right. Trong trường hợp
Right, hàm
f được áp dụng cho giá trị bên trong nó, cũng giống như cách làm trong trường hợp với
Just, hàm được áp dụng ngay cho nội dung của nó. Trong trường hợp có lỗi, giá trị
Left được giữ lại, cùng với nội dung của nó, để mô tả sự thất bại.
Thực thể
Monad của
Either e tạo nên một yêu cầu phụ thêm, đó là kiểu của giá trị chứa trong
Left, cái mà được đánh chỉ số bằng tham số kiểu
e, phải là một thực thể của lớp
Error. Lớp
Error được dành cho những kiểu mà các giá trị có thể đóng vai trò thông báo lỗi. Lớp này định nghĩa hàm
strMsg, vốn nhận một lỗi dưới dạng chuỗi rồi trả lại một giá trị như vậy. Một ví dụ điển hình cho một thực thể
Error là, a hèm, kiểu
String! Trong trường hợp với
String, hàm
strMsg chỉ việc trả lại chuỗi mà nó nhận vào:
ghci> :t strMsg strMsg :: (Error a) => String -> a ghci> strMsg "boom!" :: String "boom!"
Nhưng vì ta thường dùng
String để mô tả lỗi khi dùng
Either, nên ta sẽ không cần quá lo lắng về điều này. Khi việc khớp mẫu thất bại trong khối lệnh
do, thì một giá trị
Left được dùng để chỉ sự thất bại này.
Dù sao, ta hãy xem một vài ví dụ áp dụng:
ghci> Left "boom" >>= \x -> return (x+1) Left "boom" ghci> Right 100 >>= \x -> Left "no way!" Left "no way!"
Khi ta dùng
>>= để đưa một giá trị
Left vào một hàm, thì hàm này sẽ bị phớt lờ đi và một giá trị
Left giống hệt nó sẽ được trả lại. Khi ta đưa một giá trị
Right vào một hàm, thì hàm này sẽ áp dụng cho thứ nằm bên trong nó, nhưng trong trường hợp như vậy hàm đó vẫn sẽ tạo ra một giá trị
Left!
Khi ta thử đưa một giá trị
Right vào một hàm tính toán thành công, ta sẽ mắc phải một loại lỗi rất riêng! Hừm.
ghci> Right 3 >>= \x -> return (x + 100) <interactive>:1:0: Ambiguous type variable `a' in the constraints: `Error a' arising from a use of `it' at <interactive>:1:0-33 `Show a' arising from a use of `print' at <interactive>:1:0-33 Probable fix: add a type signature that fixes these type variable(s)
Haskell nói rằng nó khong biết chọn kiểu dữ liệu gì cho phần
e của giá trị mang kiểu
Either e a đang xét, ngay cả khi ta chỉ cần in phần
Right. Điều này là do ràng buộc
Error e trong thực thể
Monad. Như vậy nếu bạn nhận được các lỗi kiểu, như lỗi này khi dùng
Either làm monad, thì chỉ cần thêm hẳn một dấu ấn kiểu:
ghci> Right 3 >>= \x -> return (x + 100) :: Either String Int Right 103
Ổn rồi, bây giờ mã lệnh đã hoạt động!
Trừ vướng mắc nhỏ này ra thì việc dùng monad này rất giống với việc dùng
Maybe làm monad. Ở chương trước, ta đã dùng những khía cạnh monad của
Maybe để mô phỏng những con chim đậu trên cây sào thăng bằng của người đi trên dây. Bạn hãy thử làm bài tập này: viết lại chương trình đó có dùng đến monad lỗi để cho khi người đi dây mất thăng bằng và ngã, thì ta còn nhớ lại được có bao nhiêu con chim đậu trên hai đầu cây sào lúc đó.
### Một số hàm monad hữu ích
Trong mục này, ta sẽ tìm hiểu một số hàm hoạt động trên các giá trị monad hoặc trả lại kết quả là giá trị monad (hoặc là cả hai điều này!). Những hàm như vậy thường được gọ là hàm monad. Trong khi một số hàm kiểu này là mới toanh, một số khác thì lại là những dạng monad tương ứng của các hàm ta đã biết, như
filter và
foldl. Ta hãy xem chúng là gì nhé!
#### liftM cùng bạn bè
Khi ta mới khởi đầu chuyến leo lên đỉnh núi Monad Mountain, ta đã nhình đến các functor, vốn được dùng cho những thứ có thể được ánh xạ lên. Sau đó, ta đã học về các functor cải tiến, gọi là functor áp dụng, vốn cho phép ta áp dụng những functor thường đối vói một số giá trị áp dụng, cũng như lấy một giá trị thường rồi đặt nó vao trong một ngữ cảnh mặc định nào đó. Cuối cùng, ta giới thiệu monad như những functor áp dụng cải tiến, trong đó có bổ sung khả năng giúp những giá trị trên kèm ngữ cảnh được đưa vào các hàm thông thường.
Như vậy mỗi monad cũng là một functor áp dụng và mỗi functor áp dụng là một functor. Lớp
Applicative có một ráng buộc lớp, theo đó kiểu đang xét phải là một thực thể của
Functor trước khi ta có thể khiến nó làm thực thể của
Applicative. Mặc dù
Monad phải có cùng ràng buộc này đối với
Applicative, với lý do là mỗi monad cũng là một functor áp dụng, thì sự thật lại không phải, vì lớp
Monad được giới thiệu ở Haskell trước cả
Applicative.
Nhưng ngay cả khi mỗi monad là một functor, ta cũng không phải dựa vào việc nó có một thực thể
Functor vì đã có hàm
liftM. Hàm này nhận một hàm khác một giá trị monad rồi ánh xạ hàm mới nhận lên giá trị monad. Như vậy nó khá giống với
fmap! Sau đây là kiểu của
liftM:
liftM :: (Monad m) => (a -> b) -> m a -> m b
Và sau đây là kiểu của
fmap:
fmap :: (Functor f) => (a -> b) -> f a -> f b
Nếu các thực thể
Functor và
Monad của một kiểu dữ liệu đều tuân theo các định luật functor và monad, thì hai thứ này sẽ tương đương nhau (và tất cả những monad mà ta đã gặp đến giờ đều tuân theo cả hai nhóm định luật). Điều này khá giống như việc
pure và
return cùng làm một việc, chỉ khác là cái này có ràng buộc lớp
Applicative còn cái kia có ràng buộc lớp
Monad Ta hãy thử
liftM xem:
ghci> liftM (*3) (Just 8) Just 24 ghci> fmap (*3) (Just 8) Just 24 ghci> runWriter $ liftM not $ Writer (True, "chickpeas") (False,"chickpeas") ghci> runWriter $ fmap not $ Writer (True, "chickpeas") (False,"chickpeas") ghci> runState (liftM (+100) pop) [1,2,3,4] (101,[2,3,4]) ghci> runState (fmap (+100) pop) [1,2,3,4] (101,[2,3,4])
Ta đã biết khá rõ rằng
fmap thao tác trên các giá trị
Maybe như thế nào. Và
liftM làm điều tương tự. Với các giá trị
Writer, hàm đang xét sẽ được ánh xạ lên thành phần thứ nhất của bộ, vốn là kết quả. Trong quá trình
fmap hoặc
liftM lên một đại lượng trạng thái để cho ra kết quả là một đại lượng trạng thái khác, chỉ có kết quả cuối cùng mới bị thay đổi bởi hàm kèm theo. Nếu trong trường hợp này, ta đã không ánh xạ
(+100) lên
pop trước khi chạy nó, thì kết quả trả lại đã là
(1,[2,3,4]).
Đây là cách mà
liftM đã được tạo lập:
liftM :: (Monad m) => (a -> b) -> m a -> m b liftM f m = m >>= (\x -> return (f x))
Hoặc với khối lệnh
do:
liftM :: (Monad m) => (a -> b) -> m a -> m b liftM f m = do x <- m return (f x)
Ta đưa giá trị monad
m vào hàm rồi áp dụng hàm
f lên kết quả thu được, trước khi đặt nó vào lại ngữ cảnh mặc định. Các định luật monad đảm bảo rằng việc làm này không làm thay đổi ngữ cảnh, chỉ thay đổi kết quả mà giá trị monad biểu diễn. Ta thấy rằng
liftM được thiết lập mà không hề tham chiếu tới lớp
Functor. Điều này có nghĩa là ta có thể thiết lập
fmap (hoặc
liftM, bạn muốn gọi bằng tên gì cũng được) chỉ bằng cách dùng những ưu điểm mà monad có. Từ đây, ta có thể kết luận rằng monad thì mạnh hơn những functor thông thường mà ta đã gặp.
Kiểu
Applicative cho phép ta áp dụng các hàm lên những giá trị kèm ngữ cảnh, như thể chúng là những giá trị thông thường. Ví dụ:
ghci> (+) <$> Just 3 <*> Just 5 Just 8 ghci> (+) <$> Just 3 <*> Nothing Nothing
Dùng cách lập trình áp dụng như vậy làm mọi thứ trở nên đơn giản.
<$> chỉ là
fmap còn
<*> là một hàm trong lớp
Applicative có kiểu như sau:
(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
Như vậy, nó giống với
fmap, chỉ có điều là bản thân hàm cũng nằm trong một ngữ cảnh. Bằng cách nào đó, ta phải tách lấy hàm khỏi ngữ cảnh rồi ánh xạ nó lên giá trị
f a, tiếp theo là lắp ghép lại ngữ cảnh. Vì theo mặc định, cách hàm trong Haskell đều có tính “curry” nên ta có thể dùng tổ hợp của
<$> và
<*> để áp dụng các hàm nhận vào nhiều tham số lên các giá trị áp dụng.
Dù sao, hoá ra là cũng giống như
fmap,
<*> cũng có thể thiết lập được chỉ bằng cách dùng những gì mà lớp
Monad cho ta. Hàm
ap về cơ bản là
<*>, chỉ khác là nó có một ràng buộc
Monad thay vì ràng buộc
Applicative. Sau đây là lời định nghĩa hàm này:
ap :: (Monad m) => m (a -> b) -> m a -> m b ap mf m = do f <- mf x <- m return (f x)
mf là một giá trị monad mà kết quả của nó là một hàm. Vì hàm này nằm trong một ngữ cảnh, cũng như giá trị, nên ta lấy hàm ra khỏi ngữ cảnh rồi gọi nó là
f, sau đó lấy giá trị rồi gọi nó là
x, và cuối cùng đem áp dụng hàm này lên giá trị và biểu diễn kết quả. Sau đây là ví dụ ngắn gọn:
ghci> Just (+3) <*> Just 4 Just 7 ghci> Just (+3) `ap` Just 4 Just 7 ghci> [(+1),(+2),(+3)] <*> [10,11] [11,12,12,13,13,14] ghci> [(+1),(+2),(+3)] `ap` [10,11] [11,12,12,13,13,14]
Bây giờ ta đã thấy được rằng các monad cũng mạnh hơn các đối tượng áp dụng (applicative), vì ta có thể dùng các hàm trong
Monad để thiết lập những hàm của
Applicative. Thực ra, nhiều khi một kiểu dữ liệu được coi là monad, đầu tiên người ta thường viết ra một thực thể
Monad rồi sau đó lập thực thể
Applicative chỉ bằng việc khẳng định rằng
pure là
return và
<*> là
ap. Tương tự, nếu bạn đã có một thực thể
Monad của một đối tượng nào đó, bạn có thể cho nó một thực thể
Functor chỉ bằng cách nói rằng
fmap là
liftM.
Hàm
liftA2 là một hàm tiện lợi để áp dụng một hàm lên hai giá trị áp dụng. Nó được định nghĩa đơn giản như sau:
liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c liftA2 f x y = f <$> x <*> y
Hàm
liftM2 làm điều tương tự, chỉ khác là nó có một ràng buộc
Monad. Cũng có các hàm
liftM3,
liftM4 và
liftM5.
Ta đã thấy bằng cách nào mà monad mạnh hơn các đối tượng áp dụng cùng các functor và việc mặc dù mọi monad đều là functor và functor áp dụng, nhưng chúng không nhất thiết có các thực thể
Functor và
Applicative, nên ta đã kiểm tra các dạng monad tương đương của các hàm mà functor và functor áp dụng dùng đến.
#### Hàm “join”
Sau đây là một số điều cần suy ngẫm: nếu kết quả của một giá trị monad lại là một giá trị monad khác, nghĩa là nếu một giá trị monad được lồng vào trong giá trị kia, liệu bạn có thể duỗi thẳng chúng ra thành một giá trị monad thông thường chứ? Chẳng hạn, nếu có
Just (Just 9), ta có thể biến nó thành
Just 9 không? Hóa ra rằng bất kì giá trị monad lồng ghép nào cũng có thể duỗi thẳng được, và đây thực ra là một thuộc tính riêng của monad. Để làm việc này, đã có hàm
join. Kiểu của nó như sau:
join :: (Monad m) => m (m a) -> m a
Như vậy hàm nhận một giá trị monad nằm trong một giá trị monad rồi cho ta một giá trị monad, như vậy đại loại là nó đã thực hiện việc duỗi thẳng. Sau đây là cách dùng hàm với một số giá trị
Maybe:
ghci> join (Just (Just 9)) Just 9 ghci> join (Just Nothing) Nothing ghci> join Nothing Nothing
Dòng đầu tiên có một đại lượng tính toán thành công, là kết quả của một đại lượng thành công khác, vậy chúng đơn giản là được ghép nối lại thành một đại lượng thành công lớn hơn. Dòng lệnh thứ hai có
Nothing là kết quả của một giá trị
Just. Trước đây, mỗi khi ta xử lý các giá trị
Maybe và muốn kết hợp nhiều giá trị này lại làm một, bất kể nó là
<*> hoặc
>>=, chúng đều phải là
Just thì kết quả mới là một giá trị
Just. Nếu bất kì thất bại nào đó xảy ra trong quá trình tính, thì kết quả sẽ là thất bại, và điều tương tự cũng diễn ra ở đây. Trong dòng lệnh thứ ba, ta đã thử duỗi thẳng thứ mà khởi nguồn là một thất bại, nên kết quả cũng là thất bại.
Việc duỗi thẳng danh sách khá là trực quan:
ghci> join [[1,2,3],[4,5,6]] [1,2,3,4,5,6]
Bạn thấy đấy, với danh sách,
join chỉ là
concat. Để duỗi thẳng một giá trị
Writer mà kết quả cũng là một giá trị
Writer khác, ta phải thực hiện
mappend với giá trị monoid.
ghci> runWriter $ join (Writer (Writer (1,"aaa"),"bbb")) (1,"bbbaaa")
Giá trị monoid ở ngoài,
"bbb" được xử lý trước và tiếp theo
"aaa" được nối vào. Xét theo trực giác, khi bạn muốn kiểm tra xem giá trị của
Writer là gì, trước hết bạn phải viết giá trị monoid của nó vào nội dung ghi chép rồi mới kiểm tra được xem bên trong có gì.
Việc duỗi thẳng những giá trị
Either rất giống với việc duỗi thẳng các giá trị
Maybe:
ghci> join (Right (Right 9)) :: Either String Int Right 9 ghci> join (Right (Left "error")) :: Either String Int Left "error" ghci> join (Left "error") :: Either String Int Left "error"
Nếu ta áp dụng
join lên một đại lượng trạng thái với kết quả là một đại lượng trạng thái, thì kết quả sẽ là một đại lượng trạng thái mà trước hết hoạt động với đại lượng trạng thái bên ngoài tiếp theo là đại lượng kết quả. Xem này:
ghci> runState (join (State $ \s -> (push 10,1:2:s))) [0,0,0] ((),[10,1,2,0,0,0])
Ở đây lambda nhận một trạng thái rồi đặt
2 và
1 lên ngăn xếp rồi biểu diễn
push 10 làm kết quả. Như vậy khi toàn bộ cái này được duỗi thẳng bằng
join và rồi chạy, thì trước hết
2 và
1 được đặt lên ngăn xếp rồi
push 10 được thực thi, đẩy số
10 lên đỉnh ngăn xếp.
Cách thiết lập
join như sau:
join :: (Monad m) => m (m a) -> m a join mm = do m <- mm m
Vì kết quả của
mm là một giá trị monad, ta đem lấy giá trị đó rồi chỉ việc đặt vào một dòng lệnh riêng vì nó là một giá trị monad. Mẹo ở đây là khi ta viết
m <- mm, ngữ cảnh của monad mà ta đang xét sẽ được theo dõi. Điều này giải thích tại sao, chẳng hạn, các giá trị
Maybe cho kết quả là các giá trị
Just chỉ khi các giá trị ngoài và trong đều là những giá trị
Just. Điều này sẽ được cho thấy như sau đây, nếu giá trị
mm được gán trước là
Just (Just 8):
joinedMaybes :: Maybe Int joinedMaybes = do m <- Just (Just 8) m
Có lẽ điều hay nhất ở
join là đối với mỗi monad, việc đưa một giá trị monad vào một hàm bằng
>>= cũng giống như chỉ việc ánh xạ hàm đó lên giá trị rồi dùng
join để duỗi thẳng giá trị monad lồng ghép thu được! Nói cách khác,
m >>= f luôn giống như
join (fmap f m)! Nếu suy nghĩ, bạn sẽ thấy điều này hoàn toàn có lý. Bằng
>>=, ta luôn nghĩ về cách đưa một giá trị monad vào cho một hàm nhận giá trị thường nhưng trả lại một giá trị monad. Nếu ta chỉ ánh xạ hàm đó lên giá trị monad, ta sẽ có một giá trị monad bên trong một giá trị monad khác. Chẳng hạn, giả dụ ta có
Just 9 và hàm là
\x -> Just (x+1). Nếu ánh xạ hàm này lên
Just 9, ta thu được
Just (Just 10).
Việc
m >>= f luôn bằng
join (fmap f m) rất có ích nếu ta tự lập nên thực thể
Monad của một kiểu dữ liệu nào đó, vì thường sẽ dễ hơn nếu ta hình dung cách duỗi thẳng một giá trị monad lồng ghép hơn là việc hình dung ra cách lập
>>=.
#### filterM
Hàm
filter chính là một phần cốt lõi của lập trình Haskell (
map là một phần cốt lõi khác). Hàm này nhận một vị từ cùng một danh sách cần lọc rồi trả lại một danh sách mới trong đó chỉ còn lại những phần tử thỏa mãn vị từ. Kiểu của hàm như sau:
filter :: (a -> Bool) -> [a] -> [a]
Vị từ nhận vào một phần tử thuộc danh sách rồi trả lại một giá trị
Bool . Bây giờ, sẽ ra sao nếu giá trị
Bool mà nó trả lại là một giá trị monad? Ôi! Nghĩa là, nếu nó đi cùng với một ngữ cảnh? Liệu chương trình có hoạt động không? Chẳng hạn, sẽ ra sao nếu mỗi giá trị
True hoặc
False mà vị từ tạo ra cũng có một giá trị monoid tương ứng, như
["Accepted the number 5"] hoặc
["3 is too small"]? Nghe có vẻ cũng hoạt động được đấy. Nếu như vậy, thì ta sẽ trông đợi danh sách kết quả cũng gồm có nội dung ghi chép chứa tất cả những giá trị ghi chép được tạo ra trong quá trình thực hiện. Như vậy, nếu giá trị
Bool mà vị trừ trả lại đi cùng với một ngữ cảnh, thì ta trông đợi rằng danh sách kết quả cuối cùng cũng sẽ có một ngữ cảnh gắn kèm, nếu không thì ngữ cảnh đi theo từng
Bool sẽ mất đi.
Hàm
filterM trong
Control.Monad
thực hiện đúng điều ta mong muốn! Hàm này có kiểu như sau:
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
Vị từ trả lại một giá trị monad có kết quả là một
Bool, nhưng vì nó là một giá trị monad, nên ngữ cảnh có thể là bất kì điều gì, từ thất bại có thể xảy ra, đến giá trị không tất định, và còn hơn thế nữa! Để đảm bảo rằng ngữ cảnh được phản ánh trong kết quả cuối cùng, thì kết quả này cũng phải là một giá trị monad.
Ta hãy lấy một danh sách rồi chỉ giữ lại những giá trị nào nhỏ hơn 4. Ta sẽ bắt đầu bằng việc chỉ dùng hàm
filter thông thường:
ghci> filter (\x -> x < 4) [9,1,5,2,10,3] [1,2,3]
Thật khá dễ. Bây giờ, ta hãy lập một vị từ sao cho, ngoài việc biểu diễn kết quả
True hoặc
False, còn đưa ra nội dung ghi chép những gì nó thực hiện được. Đương nhiên, ta sẽ dùng monad
Writer vào việc này:
keepSmall :: Int -> Writer [String] Bool keepSmall x | x < 4 = do tell ["Keeping " ++ show x] return True | otherwise = do tell [show x ++ " is too large, throwing it away"] return False
Thay vì có “just” và trả lại một
Bool, hàm này trả lại một
Writer [String] Bool. Đó là một vị từ monad. Nghe hay đấy nhỉ? Nếu như con số nhỏ hơn
4 thì máy báo rằng sẽ giữ số đó lại rồi
return True.
Bây giờ hãy đưa kết quả thu được vào
filterM cùng với một danh sách. Bởi vị từ đang xét trả lại một giá trị
Writer, nên danh sách thu được cũng sẽ là một giá trị
Writer.
ghci> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3] [1,2,3]
Kiểm tra lại kết quả của giá trị
Writer thu được, ta thấy mọi thứ đều ổn. Bây giờ, hãy in ra nội dung ghi chép và xem ta nhận được những gì nào:
ghci> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3] 9 is too large, throwing it away Keeping 1 5 is too large, throwing it away Keeping 2 10 is too large, throwing it away Keeping 3
Tuyệt. Như vậy chỉ bằng việc cung cấp một vị từ monad cho
filterM, ta đã có thể lọc một danh sách trong khi vẫn tận dụng được ngữ cảnh monad mà ta đã dùng.
Một mẹo rất hay trong Haskell là cách dùng
filterM để thu được tập lũy thừa của một danh sách (nếu ta tạm coi danh sách là tập hợp). Với một tập hợp bất kì, tập lũy thừa của nó là một tập hợp chứa tất cả những tập con của tập hợp ban đầu. Như vậy nếu ta có một tập hợp chẳng hạn
[1,2,3], thì tập lũy thừa của nó sẽ chứa những tập hợp sau:
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []
Nói cách khác, việc lấy một tập lũy thừa cũng như lấy tất cả những tổ hợp của việc giữ và vứt bỏ các phần tử thuộc một tập hợp cho trước.
[2,3] cũng giống như tập hợp ban đầu, chỉ có điều là ta đã loại bỏ con số
1.
Để lập một hàm có nhiệm vụ trả lại tập lũy thừa của một danh sách cho trước, ta sẽ dựa vào sự không tất định. Ta lấy danh sách
[1,2,3] rồi xét phần tử thứ nhất, tức là
1, rồi tự hỏi: nên giữ lại hay bỏ nó đi? À, thực ra thì ta muốn làm cả hai việc. Như vậy, ta sẽ lọc một danh sách và dùng một vị từ để vừa giữ lại, vừa bỏ đi từng phần tử một khỏi danh sách, theo nghĩa không tất định. Sau đây là hàm
powerset được lập ra:
powerset :: [a] -> [[a]] powerset xs = filterM (\x -> [True, False]) xs
Đợi đã, phải nó không vậy? Đúng. Ta chọn cách bỏ và giữ từng phần tử một, bất kể đó là phần tử gì. Ta có một vị từ không tất định, vì vậy danh sách thu được cũng sẽ là một giá trị không tất định và do vậy sẽ là một danh sách chứa các danh sách. Hãy thử hàm này xem:
ghci> powerset [1,2,3] [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
Cần tư duy một chút để hiểu được kết quả trên, nhưng nếu bạn chỉ cần coi danh sách như là giá trị không tất định với kết quả có thể là mọi thứ cùng lúc, thì sẽ dễ hơn.
#### foldM
Dạng monad của
foldl là
foldM. Nếu bạn còn nhớ những phép gấp từ
[mục này](folds), thì bạn đã biết rằng
foldl nhận vào một hàm hai ngôi, một biến tích lũy khởi đầu và một danh sách để gấp lại, từ phía trái bằng hàm đã cho, thành một giá trị.
foldM cũng thực hiện điều tương tự, chỉ khác là nó nhận hàm hai ngôi với nhiệm vụ tạo ra một giá trị monad rồi gấp danh sách lại bằng hàm đó. Không ngạc nhiên gì khi biết rằng kết quả cũng có tính monad. Kiểu của
foldl là như sau:
foldl :: (a -> b -> a) -> a -> [b] -> a
Còn
foldM có kiểu như sau:
foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
Giá trị mà hàm hai ngôi này trả lại có tính monad và vì vậy kết quả của toàn bộ phép gấp cũng có tính monad. Ta hãy lấy tổng một danh sách các số bằng phép gấp:
ghci> foldl (\acc x -> acc + x) 0 [2,8,3,1] 14
Biến tích lũy khởi đầu là
0 và rồi
2 được cộng thêm vào biến tích lũy, nên biến có giá trị mới bằng
2.
8 được cộng thêm vào biến tích lũy này khiến cho giá trị mới bằng
10 và cứ thế đến cuối cùng, và kết quả là biến tích lũy lúc đó.
Bây giờ sẽ ra sao nếu ta muốn tính tổng một danh sách số nhưng thêm điều kiện là nếu có bất cứ số nào lớn hơn
9 có trong danh sách thì toàn bộ quá trình tính toán bị thất bại? Sẽ hợp lý nếu ta dùng một hàm hai ngôi để kiểm tra xem liệu số đang xét có lớn hơn
9 hay không và nếu đúng, thì tính toán được cho là thất bại; còn nếu không, thì vui vẻ tiếp tục. Vì khả năng thất bại mới được bổ sung này, ta hãy làm cho hàm hai ngôi đang xét trả lại một biến tích lũy
Maybe thay vì kiểu thông thường. Sau đây là hàm hai ngôi:
binSmalls :: Int -> Int -> Maybe Int binSmalls acc x | x > 9 = Nothing | otherwise = Just (acc + x)
Vì hàm hai ngôi đang xét bây giờ là một hàm monad, ta không thể dùng nó với hàm
foldl thông thường, mà phải dùng đến
foldM, như sau:
ghci> foldM binSmalls 0 [2,8,3,1] Just 14 ghci> foldM binSmalls 0 [2,11,3,1] Nothing
Rất tốt! Vì có một số trong danh sách lớn hơn
9, nên toàn bộ trở thành
Nothing. Việc gấp với một hàm hai ngôi trả lại một giá trị
Writer cũng rất hay vì khi đó bạn ghi chép được tất cả những thứ gì mong muốn trong quá trình gấp.
#### Lập nên một chiếc mấy tính RPN an toàn
Khi giải bài toán
[thiết lập máy tính RPN](reverse-polish-notation-calculator), ta đã lưu ý rằng nó luôn hoạt động tốt, miễn là dữ liệu đầu vào phải có nghĩa. Nhưng nếu có gì sai sót, thì toàn bộ chương trình sẽ đổ vỡ. Bây giờ khi ta đã biết cách lấy một đoạn mã ta có và biến nó trở thành monad rồi, ta hãy thêm tính năng xử lý lỗi cho máy tính RPN hiện có, bằng cách tận dụng monad
Maybe.
Ta thiết lập máy tính RPN bằng cách lấy một chuỗi kí tự như
"1 3 + 2 *", phá vỡ nó thành từng “từ” riêng lẻ như
["1","3","+","2","*"] rồi thực hiện gấp danh sách này cùng với một ngăn xếp rỗng rồi dùng một hàm gấp hai ngôi để thêm các số vào ngăn xếp hoặc thao tác với những con số ở đỉnh ngăn xếp thông qua phép cộng, trừ, nhân, chia.
Đây là phần thân của hàm này:
import Data.List solveRPN :: String -> Double solveRPN = head . foldl foldingFunction [] . words
Ta đã biến đổi biểu thức thành một danh sách các chuỗi kí tự, xử lý nó bằng hàm gấp và rồi nhận được một phần tử duy nhất trong ngăn xếp, ta trả lại phần tử này làm kết quả. Sau đây là hàm gấp:
foldingFunction :: [Double] -> String -> [Double] 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
Biến tích lũy của phép gấp là một ngăn xếp, mà ta biểu diễn bằng một danh sách các giá trị
Double. Trong khi hàm gấp duyệt qua biểu thức RPN, nếu phần tử được xét là một toán tử, thì hàm này lấy hai phần tử ra khỏi đỉnh ngăn xếp, áp dụng toán tửu lên chúng rồi đặt kết quả trở lại vào ngăn xếp. Nếu phần tử được xét là một chuỗi kí tự biểu diễn cho một con số, thì hàm sẽ quy đổi chuỗi đó thành số rồi trả lại một ngăn xếp mới giống ngăn xếp cũ, nhưng có thêm số vừa rồi được đẩy lên đỉnh ngăn xếp.
Trước hết, ta hãy làm cho hàm gấp có khả năng xử lý thât bại một cách đẹp mắt. Kiểu của hàm này sẽ thay đổi sang thành như sau:
foldingFunction :: [Double] -> String -> Maybe [Double]
Như vậy nó sẽ hoặc là trả lại
Just với một ngăn xếp mới hoặc sẽ thất bại với
Nothing.
Hàm
reads cũng giống như
read, chỉ khác là nó trả lại một danh sách với một phần tử trong trường hợp đọc thành công. Nếu thất bại, không đọc được gì thì nó sẽ trả lại một danh sach rỗng. Ngoại trừ việc trả lại giá trị đã đọc, nó cũng trả lại phần chuỗi không dùng đến. Ta sẽ nói rằng để hoạt động bình thường, hàm này luôn phải dùng đến toàn bộ dữ liệu đầu vào rồi chuyển thành một hàm
readMaybe, để cho tiện. Sau đây là hàm này:
readMaybe :: (Read a) => String -> Maybe a readMaybe st = case reads st of [(x,"")] -> Just x _ -> Nothing
Hãy thử dùng nó:
ghci> readMaybe "1" :: Maybe Int Just 1 ghci> readMaybe "GO TO HELL" :: Maybe Int Nothing
Được rồi, có vẻ nó đã hoạt động. Vì vậy, hãy làm cho hàm gấp trong tay ta trở thành một hàm monad mà có thể thất bại:
foldingFunction :: [Double] -> String -> Maybe [Double] foldingFunction (x:y:ys) "*" = return ((x * y):ys) foldingFunction (x:y:ys) "+" = return ((x + y):ys) foldingFunction (x:y:ys) "-" = return ((y - x):ys) foldingFunction xs numberString = liftM (:xs) (readMaybe numberString)
Ba trường hợp đầu cũng giống như trước đây, chỉ khác rằng ngăn xếp mới được bọc vào trong một
Just (ở đây ta đã dùng
return để làm việc này, nhưng cũng có thể viết
Just). Trong trường hợp sau cùng, ta viết
readMaybe numberString rồi ánh xạ
(:xs) lên nó. Như vậy nếu ngăn xếp
xs là
[1.0,2.0] và
readMaybe numberString có kết quả là
Just 3.0, thì kết quả là
Just [3.0,1.0,2.0]. Nếu
readMaybe numberString cho kết quả là
Nothing thì kết quả là
Nothing. Ta hãy thử hàm gấp này:
ghci> foldingFunction [3,2] "*" Just [6.0] ghci> foldingFunction [3,2] "-" Just [-1.0] ghci> foldingFunction [] "*" Nothing ghci> foldingFunction [] "1" Just [1.0] ghci> foldingFunction [] "1 wawawawa" Nothing
Dường như nó đã hoạt động đúng! Và bây giờ là lúc dành cho hàm
solveRPN mới cải tiến. Xin quý vị hãy xem!
import Data.List solveRPN :: String -> Maybe Double solveRPN st = do [result] <- foldM foldingFunction [] (words st) return result
Cũng như trước đây, ta lấy chuỗi kí tự rồi biến nó thành một danh sách các từ. Sau đó, ta thực hiện phép gấp, bắt đầu với một ngăn xếp rỗng, chỉ khác là thay vì thực hiện một
foldl thông thường, ta thực hiện
foldM. Kết quả của việc dùng
foldM sẽ là một giá trị
Maybe có chứa một danh sách (chính là ngăn xếp cuối cùng thu được) và danh sách đó phải có đúng một giá trị. Ta dùng một biểu thức
do để lấy giá trị đó rồi gọi nó là
result. Trong trường hợp
foldM trả lại một
Nothing, tất cả sẽ thành
Nothing, vì đó chính là cách hoạt động của
Maybe. Cũng lưu ý rằng ta khớp mẫu trong biểu thức
do, vì vậy nếu danh sách có nhiều giá trị hoặc không có giá trị nào, thì việc khớp mẫu sẽ thất bại và tạo ra một giá trị
Nothing. Ở dòng lệnh cuối cùng, ta chỉ việc viết
return result để biểu diễn kết quả của phép tính RPN làm kết quả cuối cùng của giá trị
Maybe.
Ta hãy thử nó:
ghci> solveRPN "1 2 * 4 +" Just 6.0 ghci> solveRPN "1 2 * 4 + 5 *" Just 30.0 ghci> solveRPN "1 2 * 4" Nothing ghci> solveRPN "1 8 wharglbllargh" Nothing
Sự thất bại đầu tiên xảy ra vì ngăn xếp cuối cùng không phải là một danh sách chỉ chứa một phần tử, dẫn đến việc khớp mẫu trong biểu thức
do bị thất bại. Sự thất bại thứ hai xảy ra vì
readMaybe trả lại một
Nothing.
#### Hợp các hàm monad
Khi học về các định luật monad, ta đã nói rằng hàm
<=< đơn giản là giống như phép hợp các hàm, chỉ khác là thay vì những hàm thông thường như
a -> b, nó làm việc với các hàm monad như
a -> m b. Chẳng hạn:
ghci> let f = (+1) . (*100) ghci> f 4 401 ghci> let g = (\x -> return (x+1)) <=< (\x -> return (x*100)) ghci> Just 4 >>= g Just 401
Ở ví dụ này đầu tiên là ta hợp hai hàm thường, rồi áp dụng hàm thu được đối với
4, sau đó hợp hai hàm monad rồi đưa
Just 4 vào hàm kết quả bằng
>>=.
Nếu ta có một loạt các hàm trong một danh sách, ta có thể hợp tất cả chúng thành một hàm lớn bằng cách đơn giản là dùng
id làm biến tích lũy ban đầu và hàm
. đóng vai trò của hàm hai ngôi. Sau đây là một ví dụ:
ghci> let f = foldr (.) id [(+1),(*100),(+1)] ghci> f 1 201
Hàm
f nhận một con số rồi cộng
1 vào nó, đem nhân kết quả với
100 rồi cộng
1 vào kết quả thu được. Dù sao đi nữa, ta cũng có thể hợp các hàm monad theo cách này, chỉ khác là thay vì phép hợp thông thường, ta dùng
<=< và thay vì
id, ta dùng
return. Ta không cần phải dùng
foldM thay cho
foldr hay những gì như vậy, vì hàm
<=< đảm bảo rằng phép hợp được tiến hành theo cách monad.
Khi bắt đầu làm quen với danh sách monad trong
[chương trước](a-fistful-of-monads#the-list-monad), ta đã dùng nó để chỉ ra cách một quân Mã đi từ ô này sang ô khác trên bàn cờ sau ba nước. Ta đã có một hàm tên là
moveKnight nhận vào ô xuất phát của quân Mã trên bàn cờ rồi trả lại tất cả những nước đi nó có thể thực hiện được. Tiếp theo, để phát sinh tất cả những vị trí quân Mã có thể đứng sau ba nước, ta đã lập nên những hàm sau:
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight
Và để kiểm tra xem nó có thể đi từ ô
start đến ô
end sau ba nước hay không, ta làm như sau:
canReachIn3 :: KnightPos -> KnightPos -> Bool canReachIn3 start end = end `elem` in3 start
Bằng cách dùng hàm hợp monad, ta có thể lập nên một hàm như
in3, nhưng thay vì phát sinh tất cả những ô mà quân Mã có thể đến sau ba nước, thì giải quyết trường hợp với số nước đi bất kì. Nếu nhìn vào
in3, ta thấy rằng mình đã sử dụng
moveKnight ba lần và trong mỗi lần đã sử dụng
>>= để đưa vào hàm này tất cả những vị trí quân Mã có thể đứng lúc trước. Như vậy, bây giờ ta hãy làm cho hàm này tổng quát hơn. Sau đây là cách làm:
import Data.List inMany :: Int -> KnightPos -> [KnightPos] inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)
Trước tiên, ta dùng
replicate để lập nên danh sách có chứa
x bản sao của hàm
moveKnight. Sau đó, ta hợp, theo cách monad, tất cả những hàm này làm một; điều này cho ta một hàm nhận vào ô xuất phát và di chuyển quân Mã một cách không tất định
x lần. Tiếp theo, ta chỉ việc biến ô xuất phát thành một danh sách một phần tử bằng lệnh
return rồi đưa nó vào hàm.
Bây giờ, ta cũng có thể thay đổi hàm
canReachIn3 để cho được tổng quát hơn:
canReachIn :: Int -> KnightPos -> KnightPos -> Bool canReachIn x start end = end `elem` inMany x start
### Lập ra các monad
Trong mục này, ta sẽ xét một ví dụ về cách tạo ra một kiểu dữ liệu, nhận diện nó như một mand rồi gán cho thực thể
Monad phù hợp. Ta không thường xuyên tạo lập một monad chỉ để cho có; mà với mục đích để mô hình hóa một khía cạnh của vấn đề rồi sau đó nếu thấy rằng kiểu dữ liệu được xét biểu diễn cho một giá trị kèm ngữ cảnh và có thể đóng vai trò như monad, thì gán cho nó một thực thể
Monad.
Như đã thấy, các danh sách được dùng để biểu diễn cho giá trị không tất định. Một danh sách như
[3,5,9] có thể được coi là một giá trị không tất định mà bản thân nó không tự quyết được sẽ là gì. Khi ta đưa một danh sách vào một hàm bằng
>>=, chương trình sẽ thực hiện tất cả những lựa chọn có thể cho việc lấy một phần tử khỏi danh sách rồi áp dụng hàm lên nó, sau đó biểu diễn những kết quả đó cũng dưới dạng danh sách.
Nếu ta coi danh sách
[3,5,9] như những con số
3,
5 và
9 xuất hiện cùng lúc, ta có thể nhận thấy rằng không có thông tin gì về xác suất xuất hiện của chúng. Sẽ ra sao nếu ta muốn mô phỏng một giá trị không tất định nhưng
[3,5,9], nhưng muốn chỉ định rằng
3 có 50% khả năng xuát hiện còn
5 và
9, mỗi số có 25% khả năng xuất hiện? Ta hãy thử làm điều này!
Giả sử rằng mỗi phần tử trong danh sách đều kèm theo một giá trị khác, một con số xác suất xuất hiện. Thế thì việc biểu diễn nó như sau là hợp lý:
[(3,0.5),(5,0.25),(9,0.25)]
Về mặt toán học, xác suất không thường được biểu diễn dưới dạng số phần trăm, mà là những số thực từ 0 đến 1. Số 0 nghĩa là không có cơ hội để điều gì có thể xảy ra, còn 1 nghĩa là chắc chắn điều đó sẽ xảy đến. Các số với dấu chấm động trong quá trình tính toán sẽ nhanh chóng mất đi độ chính xác, vì vậy Haskell cho ta một kiểu dữ diệu riêng cho các phân số mà độ chính xác của chúng không bị mất đi. Kiểu dữ liệu này có tên
Rational và nó tồn tại trong
Data.Ratio. Để tạo nên một
Rational, ta viết nó dưới dạng như một phân số. Tử số và mẫu số được phân cách bởi một dấu
%. Sau đây là vài ví dụ:
ghci> 1%4 1 % 4 ghci> 1%2 + 1%2 1 % 1 ghci> 1%3 + 5%4 19 % 12
Dòng đầu tiên đơn giản chỉ là một phần tư. Ở dòng thứ hai, ta cộng hai nửa lại để thu được số một, và dòng thứ ba ta cộng một phần ba với năm phần tư để được 19 phần 12. Vậy ta hãy vứt bỏ các dấu phẩy động đi và dùng
Rational để biểu diễn xác suất:
ghci> [(3,1%2),(5,1%4),(9,1%4)] [(3,1 % 2),(5,1 % 4),(9,1 % 4)]
Được rồi, như vậy là
3 có khả năng xuất hiện một lần trong hai lượt, còn
5 và
9 sẽ xuất hiện một lần trong khoảng bốn lượt. Rất gọn gàng.
Ta chọn lấy danh sách rồi bổ sung thêm ngữ cảnh cho chúng, như vậy nó sẽ biểu thị các giá trị kèm với ngữ cảnh. Trước khi đi tiếp, ta hãy gói những thứ này vào trong một
newtype vì có điều gì đó mách bảo tôi rằng chúng ta sẽ cần lập nên một số thực thể.
import Data.Ratio newtype Prob a = Prob { getProb :: [(a,Rational)] } deriving Show
Được rồi. Đây là một functor à? A hèm, danh sách là một functor, vì vậy thứ này có lẽ cũng là một functor, vì ta vừa mới bổ sung thêm gì đó vào danh sách. Khi ánh xạ một hàm lên một danh sách, ta áp dụng nó cho từng phần tử. Ở đây, ta cũng sẽ áp dụng nó cho từng phần tử, nhưng có điều là giữ nguyên các xác suất. Ta hãy lập một thực thể:
instance Functor Prob where fmap f (Prob xs) = Prob $ map (\(x,p) -> (f x,p)) xs
Ta gỡ vỏ bọc khỏi
newtype bằng cách khớp mẫu, áp dụng hàm
f cho các giá trị trong khi vẫn giữ nguyên các xác suất rồi lại bọc nó trở lại. Hãy thử xem liệu nó có hoạt động không:
ghci> fmap negate (Prob [(3,1%2),(5,1%4),(9,1%4)]) Prob {getProb = [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)]}
Một điều khác cần lưu ý là những xác suất luôn phải có tổng bằng
1. Nếu sự việc chỉ có ngần ấy khả năng xảy ra, thì sẽ chẳng có lý gì mà những xác suất của chúng cộng lại không bằng
1. Có lẽ phải đến một thế giới khác mới thấy được đồng xu nào lật ngửa 75% mà lại sấp 50% trong tổng số các lần gieo.
Bây giờ câu hỏi lớn là, liệu đây có phải là monad không? Ta đã biết danh sách là một monad rồi, thì thứ này lý ra cũng phải là một monad. Trước hết, hãy nghĩ về
return. Nó hoạt động ra sao với các danh sách? Nó lấy một giá trị rồi đặt vào danh sách một phần tử. Ở đây thì sao? Ồ, vì nó phải là một ngữ cảnh tối thiểu mặc định, nên nó cũng là một danh sách một phần tử. Thế còn về xác suất? Ừm,
return x phải tạo ra một giá trị monad sao cho luôn biểu thị
x làm kết quả, cho nên xác suất không có lý gì mà bằng
0 được. Nếu nó luôn phải biểu thị giá trị làm kết quả, thì xác suất phải là
1!
Thế còn về
>>=? Có vẻ rất mẹo mực, vì vậy ta hãy tận dụng thông tin là đối với các monad,
m >>= f luôn bằng
join (fmap f m), rồi nghĩ cách duỗi thẳng một danh sách xác suất chứa những danh sách xác suất khác. Chẳng hạn, ta hãy xét danh sách trong đó có 25% khả năng xuất hiện đúng một chữ
'a' hoặc
'b'. Cả hai
'a' và
'b' đều cùng khả năng xuất hiện. Ngoài ra cũng có 75% khả năng là có đúng một chữ
'c' hoặc
'd' xuất hiện.
'c' và
'd' cũng có cùng khả năng có mặt. Sau đây là một hình ảnh về danh sách xác suất để mô phỏng cho trường hợp này:
Đâu là các khả năng xuất hiện của từng chữ cái này? Nếu ta phải phân chia những thứ ở đây thành bốn hộp, mỗi hộp có một xác suất, thì những xác suất đó sẽ bằng bao nhiêu? Để tính được các xác suất này, việc ta cần làm chỉ là đem nhân từng xác suất với tất cả những xác suất mà nó bao gồm.
'a' sẽ xảy ra một lần trong số tám lượt, và
'b' cũng vậy, vì nếu ta nhân một nửa với một phần tư thì sẽ được một phần tám.
'c' sẽ xảy ra ba lần trong tám lượt vì ba phần tư nhân với một nửa thì bằng ba phần tám.
'd' cũng sẽ xảy ra ba lần trong tám lượt. Nếu ta cộng tất cả xác suất lại thì sẽ được kết quả bằng một.
Sau đây là tình huống hiện giờ được biểu diễn dưới dạng danh sách xác suất:
thisSituation :: Prob (Prob Char) thisSituation = Prob [( Prob [('a',1%2),('b',1%2)] , 1%4 ) ,( Prob [('c',1%2),('d',1%2)] , 3%4) ]
Lưu ý rằng kiểu của nó là
Prob (Prob Char). Vậy bây giờ, khi đã hình dung được cách duỗi thẳng một danh sách xác suất lồng ghép rồi, thì tất cả những gì ta cần làm là viết ra mã lệnh rồi sau đó ta có thể dùng
>>= đơn giản như là
join (fmap f m) và ta sẽ có trong tay một monad! Sau đây là
flatten; ta sẽ dùng tên gọi này vì cái tên
join đã bị chọn trước rồi:
flatten :: Prob (Prob a) -> Prob a flatten (Prob xs) = Prob $ concat $ map multAll xs where multAll (Prob innerxs,p) = map (\(x,r) -> (x,p*r)) innerxs
Hàm
multAll nhận một bộ các danh sách xác suất và một xác suất
p đi kèm theo rồi nhân mỗi xác suất bên trong với
p, trả lại kết quả là một danh sách các cặp phần tử kèm theo xác suất. Ta ánh xạ
multAll lên từng cặp trong danh sách xác suất lồng ghép rồi sau đó chỉ việc duỗi thẳng danh sách lồng ghép thu được.
Bây giờ khi đã sẵn có tất cả những thứ cần thiết, ta có thể viết nên thực thể
Monad!
instance Monad Prob where return x = Prob [(x,1%1)] m >>= f = flatten (fmap f m) fail _ = Prob []
Vì ta đã làm tất cả phần việc nặng nhọc rồi, nên thực thể sẽ rất đơn giản. Ta cũng đã định nghĩa hàm
fail, vốn giống như ở trường hợp danh sách, vì vậy nếu có một thất bại trong việc khớp mẫu ở một biểu thức
do, thì sẽ có thất bại xảy ra trong ngữ cảnh của danh sách xác suất.
Một việc cũng quan trọng là kiểm tra xem liệu monad mới lập nên có thỏa mãn các định luật monad hay không. Định luật đầu tiên phát biểu rằng
return x >>= f phải bằng với
f x. Để chứng minh chặt chẽ ở đây thì rất nhàm chán, nhưng ta có thể thấy rằng nếu đặt một giá trị vào trong một ngữ cảnh mặc định bằng
return vào sau đó
fmap một hàm lên nó rồi duỗi thẳng danh sách xác suất thu được, thì mỗi xác suất thu được từ hàm sẽ được nhân lên với
1%1 xác suất mà ta đã lập bằng
return, vì vậy sẽ không ảnh hưởng đến ngữ cảnh. Lý do mà
m >>= return chỉ bằng với
m thật đơn giản. Định luật thứ ba phát biểu rằng
f <=< (g <=< h) phải giống như
(f <=< g) <=< h. Điều này cũng thỏa mãn, vì định luật thỏa mãn với những monad danh sách tạo nên cơ sở của monad xác suất và vì phép nhân có tính kết hợp.
1%2 * (1%3 bằng với
* 1%5)
(1%2 * 1%3) * 1%5.
Bây giờ khi đã có monad, ta có thể làm gì với nó? À, nó có thể giúp ta tính toán với những xác suất. Ta có thể coi những biến cố xác suất như các giá trị kèm theo ngữ cảnh và monad xác suất sẽ đảm bảo rằng những xác suất này sẽ được phản ánh trong xác suất ở kết quả cuối cùng.
Chẳng hạn ta có hai đồng xu đều đặn và một đồng xu được chế tạo gian lận mà khi tung sẽ sấp đến chín lần và ngửa một lần trong số mười lượt. Nếu ta tung cả hai đồng xu một lúc, thì khả năng để chúng cùng sấp là bao nhiêu? Trước hết, hãy tính giá trị xác suất của đồng xu thường và đồng xu gian lận:
data Coin = Heads | Tails deriving (Show, Eq) coin :: Prob Coin coin = Prob [(Heads,1%2),(Tails,1%2)] loadedCoin :: Prob Coin loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]
Và cuối cùng là hành động gieo đồng xu:
import Data.List (all) flipThree :: Prob Bool flipThree = do a <- coin b <- coin c <- loadedCoin return (all (==Tails) [a,b,c])
Chạy thử mã lệnh này, ta thấy rằng khả năng cả ba đồng xu cùng sấp không lớn như đã tưởng tượng, dù rằng đã có cả một đồng xu gian:
ghci> getProb flipThree [(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40), (False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]
Cả ba đồng xu này sẽ đều sấp chín lần trong số 40 lượt, tức là ít hơn 25%. Ta thấy rằng monad ở đây không biết cách cộng lại làm một tất cả những kết quả
False trong những có đồng xu ngửa. Điều này cũng không quan trọng lắm, vì việc viết một hàm để thu những trường hợp như vậy làm một thì khá dễ dàng; đây chính là bài tập dành cho độc giả (là bạn đấy!)
Trong mục này, ta đã đi từ việc đặt một câu hỏi (điều gì sẽ xảy ra nếu danh sách cũng mang thông tin về xác suất?) đến việc lập một kiểu dữ liệu, tiếp nhận một monad, rồi cuối cùng là lập một thực thể và thao tác với nó. Tôi nghĩ rằng điều này thật là hấp dẫn! Đến giờ, ta hẳn đã nắm vững được monad rồi.
## 3 responses to “
Chương 13: Bổ sung về Monad”
Pingback: Tự học lấy Haskell | Blog của Chiến
cho mình file tự học lấy haswell full offline với ,mình muốn tự học và tìm hiểu offline,nếu được xin gửi file vào hòm thư tranquoctuan.member@hotmail.com.
Chân thành cảm ơn
Bạn có thể ấn nút Print Friendly cuối mỗi bài Post để xuất ra file PDF cho từng chương rồi gộp lại. MÌnh thì copy từ trang web rồi paste trực tiếp vào trình LibreOffice rồi xuất ra file pdf, sẽ gửi bạn file.

Link: <http://wp.me/p1kFN-jG>; rel=shortlink