Chương 13: Bổ sung về Monad

Trở về Mục lục 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ì!

there are two kinds of people in the world, my friend. those who learn them a haskell and those who have the job of coding java

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.")

when you have to poop, poop, don't talk

Đế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

Đến lúc này bạn hãy chắc chắn là đã nắm được các monoid!

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')

when you have to poop, poop, don't talk

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ư ""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})

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

cactuses

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, fg 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!

bang youre dead

Trong chương nói về các áp dụng (applicative), 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)(+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)(+10) cho 3, kết quả là 613. Sau đó, nó gọi (+) với 613 để 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)(+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

don't jest with texas

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, 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.

Phép gán, trong hầu hết những ngôn ngữ lập trình khác, có thể được coi như là đại lượng trạng thái. Chẳng hạn, khi ta viết x = 5 trong một ngôn ngữ mệnh lệnh, nó sẽ thường đưa giá trị 5 cho biến x và bản thân đại lượng này cũng có giá trị 5 như 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: poppush. 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.

im a cop

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ì poppush đề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 38 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ì stackManipstackStuff 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à getput. Đố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ĩ: LeftRight. 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ư filterfoldl. Ta hãy xem chúng là gì nhé!

liftM cùng bạn bè

im a cop too

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ể FunctorMonad 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 purereturn 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 <$><*> để á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 purereturn<*>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 fmapliftM.

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, liftM4liftM5.

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ể FunctorApplicative, 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 21 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 21 đượ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

im a cop too as well also

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 foldlfoldM. Nếu bạn còn nhớ những phép gấp từ mục này, 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

i've found yellow!

Khi giải bài toán thiết lập máy tính RPN, 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[1.0,2.0]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, 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

kewl

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, 59 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 59, 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 59 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''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''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:

probs

Đâ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 []

ride em cowboy

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
* 1%5)
bằng với (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.

Advertisements

3 phản hồi

Filed under Haskell

3 responses to “Chương 13: Bổ sung về Monad

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

  2. Tuấ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.

Trả lời

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

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com 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