Haskell #17: Monad (kế)
Trong phần này, ta sẽ tìm hiểu thêm một số Monad nữa. Việc khám phá các Monad sẽ củng cố trực giác của ta về Monad.
17.7. Writer
Monad Writer 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 debug. 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.
isBigGang :: Int -> Bool
isBigGang x = x > 9
Bây giờ, thay vì kết quả là True hoặc False, ta muốn hàm này trả về một chuỗi:
isBigGang :: Int -> (Bool, String)
isBigGang x = (x > 9, "Compared gang size to 9.")
Như vậy bây giờ, thay vì chỉ trả về Bool, ta trả về một tuple trong đó phần tử thứ nhất là giá trị thực còn phần tử thứ hai là chuỗi đi kèm giá trị đó. isBigGang nhận một giá trị thường rồi trả về một giá trị kèm ngữ cảnh. Như đã thấy, việc đưa một giá trị 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ị và trả về 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á Maybe, ta đã tạo applyMaybe, nhận một Maybe a và hàm $f$ kiểu a -> Maybe b. applyMaybe lấy giá trị trong ngữ cảnh đi kèm và đưa vào $f$. Bên trong $f$, ta có quyền coi a là giá trị thông thường, vì applyMaybe (hay >>=) đã đảm nhiệm việc kiểm tra Maybe a là Nothing hoặc Just.
Cũng theo tinh thần này, ta tạo một hàm nhận vào một giá trị với ghi chép gắn kèm, kiểu (a, String) và hàm $f$ kiểu a -> (b, String) rồi đưa giá trị đó vào hàm. Ta sẽ gọi nó là applyLog.
applyLog :: (a, String) -> (a -> (b, String)) -> (b, String)
applyLog (x, log) f = let (y, newLog) = f x in (y, log ++ newLog)
Khi có giá trị $x$ với ngữ cảnh $log$, và muốn đưa nó vào hàm $f$, ta sẽ cố gắng tách $x$ ra rồi ánh xạ $f$ lên $x$. Ta nhận được pair (y, newLog), trong đó y là kết quả mới và newLog là nội dung ghi chép mới. ++ sẽ được sử dụng để nối nội dung ghi chép mới vào ghi chép cũ.
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")
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")
17.8. Kết hợp Monoid
applyLog nhận các giá trị kiểu (a, String) nhưng chúng ta còn có thể mở rộng kiểu dữ liệu phần log:
applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c])
Bây giờ, log là list và kiểu của các log phải giống nhau để chúng ta có thể sử dụng hàm ++ giữa chúng.
Chúng ta mở rộng thêm một cấp nữa khi xác định rằng log có thể là kiểu dữ liệu bất kỳ mà là Monoid. Việc này giúp chúng ta trừu tượng hóa hàm ++, việc nối các log với nhau sẽ được thực thi bằng hàm 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)
Chẳng hạn, ta có thể có một tuple trong đó chứa tên món hàng và giá bán tương ứng, là Monoid. Ta chỉ việc dùng newtype là Sum để đảm bảo chắc chắn rằng giá sẽ được cộng thêm vào khi chọn các món hàng khác nhau.
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)
Hãy nhớ lại rằng, việc dùng mappend với Sum sẽ trả về kết quả là những giá trị được gói lại:
ghci> Sum 3 `mappend` Sum 9
Sum {getSum = 12}
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})
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ó trả về ("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).
17.9. Kiểu Writer
Một giá trị kết hợp với một Monoid có thể là Monad, và kiểu dữ liệu này được gói trong Module Control.Monad.Writer. Đị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 nó được phân biệt so với tuple. Tham số a biểu diễn cho kiểu của giá trị còn tham số w biểu diễn cho kiểu của Monoid kèm theo.
Monad Writer đượ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')
>>= rất giống với hàm applyLog ta đã gặp trước đây, chỉ khác là khi sử dụng newtype Writer, ta phải gỡ gói, lấy giá trị $x$ rồi áp dụng hàm $f$ lên nó. Quá trình này trả về một Writer w a. Ta gọi $y$ là kết quả mới và dùng mappend để kết hợp Monoid cũ và mới. Ta ghép hai thứ lại với nhau bằng constructor Writer để cho kết quả là Writer thay vì đơn thuần là tuple.
return nhận một giá trị rồi đặt giá trị này vào ngữ cảnh tối thiểu, ngữ cảnh ở đây là giá trị Monoid càng ít ảnh hưởng đến các giá trị Monoid khác càng tốt nên mempty được sử dụng. Khi dùng return để tạo một Writer $w$ rồi dùng >>= để đưa $w$ vào hàm thì giá trị Monoid trả về chỉ là thứ mà hàm trả về.
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})
runWriter là hàm chuyển Writer sang tuple, để có thể hiển thị được.
17.9.1. do trong Writer
Vì Write là Monan nên dĩ nhiên ta có thể sử dụng do cho các Writer. Sau đây là một ví dụ đơn giản:
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 giá trị kiểu Int rồi tạo một Writer. Đối với Monoid, ta dùng list String chỉ để báo rằng ta có con số như vậy. multWithLog là một Writer thực hiện phép 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 tích lại 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.
ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5"])
Hàm tell sẽ gán một Monoid vào Monad:
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 cuối trong khối do là kết quả của toàn bộ biểu thức do. Nếu ta đưa tell xuống cuối trong trường hợp này, thì () sẽ là kết quả. 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"])
17.9.2. Logging system
Thuật toán Euclid nhận vào $a$, $b$ rồi tìm UCLN $gcd(a,b)$. 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à UCLN của số thứ hai và số dư của phép chia số thứ nhất cho số thứ hai.
ghci> gcd' 8 3
1
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 list String làm Monoid. Khi đó kiểu của hàm gcd' mới sẽ là:
gcd' :: Int -> Int -> Writer [String] Int
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ả về Writer [String] Int. Trong trường hợp b bằng 0, thay vì việc chỉ đưa kết quả là $a$, ta dùng 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ả. Thay vì dùng do này, ta cũng có thể viết như sau:
Writer (a, ["Finished with " ++ show a])
Tiếp theo, khi b khác 0, ta ghi lại rằng ta dùng mod để tính $a$ % $b$. Sau đó, thực thi bằng cách gọi gcd'. gcd' cuối cùng trả về một giá trị Writer, nên hoàn toàn đúng khi viết gcd' b (a mod b) trong do.
ghci> fst $ runWriter (gcd' 8 3)
1
Vì nội dung ghi chép là list String, nên phải dùng hàm 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
Thuật toán mới giờ đây có khả năng báo cáo quá trình tính toán chỉ bằng cách sử dụng Monad và để >>= của Writer đảm nhiệm việc ghi chép. Có thể thêm cơ chế ghi chép gần như cho hàm nào cũng được.
17.9.3. Cơ chế dùng Monoid
Khi dùng Monad Writer, bạn phải cẩn thận trong việc dùng Monoid nào, vì list đôi khi có thể trở nên rất chậm chạp. Đó là bởi list dùng đến ++ để mappend, mà việc dùng ++ để nối phần tử vào cuối list sẽ chậm nếu list rất dài.
Trong hàm gcd', việc ghi chép được thực hiện rất nhanh vì cách nối list như sau:
a ++ (b ++ (c ++ (d ++ (e ++ f))))
List là CTDL được khởi tạo 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 khởi tạo phần bên trái của list rồi sau đó mới nối một list 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 nối list như sau:
((((a ++ b) ++ c) ++ d) ++ e) ++ f
Cách tính toán này kết trái thay vì kết phải. Đây là cách không hiệu quả vì 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 phải được khởi tạo từ đầu.
Hàm sau đây hoạt động giống như gcd', chỉ khác là nó ghi chép theo chiều đảo ngược.
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
ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)
Finished with 1
2 mod 1 = 0
3 mod 2 = 1
8 mod 3 = 2
Xét về độ hiệu quả, nó rất kém ++ đã thực thi theo kết phải.
17.9.4. Difference list
Vì đôi lúc list có thể kém hiệu quả nên tốt nhất là ta dùng một CTDL luôn cho phép nối một cách hiệu quả. Một CTDL tiêu biểu là difference list. Một difference list cũng giống như list, chỉ hơn ở chỗ nó là một hàm nhận list rồi nối list khác về phía trước nó. Tương ứng với list như [1,2,3], difference list sẽ là hàm \xs -> [1,2,3] ++ xs. Với [], difference list sẽ là hàm \xs -> [] ++ xs.
Khi ta nối hai list thông thường với ++, chương trình sẽ phải thực hiện duyệt từ đầu đến cuối list bên trái rồi mới gán list còn lại kế vào đó. Trong khi nối hai difference list 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 list và rồi chèn thêm nội dung nào đó vào trước những list này. Chẳng hạn, nếu $f$ là \xs -> "dog" ++ xs và $g$ là hàm \xs -> "meat"++ xs, thì f `append` g tương đương:
\xs -> "dog" ++ ("meat" ++ xs)
Khi muốn áp dụng khái niệm Monoid, ta sử dụng newtype để bọc difference list lại:
newtype Difflist a = Difflist {
getDifflist :: [a] -> [a]
}
Kiểu dữ liệu mà ta bọc là [a] -> [a] vì difference list đơn giản là hàm nhận vào list rồi trả về một list khác. Thật dễ chuyển đổi qua lại giữa list thông thường và difference list:
toDifflist :: [a] -> Difflist a
toDifflist xs = Difflist (xs++)
fromDifflist :: Difflist a -> [a]
fromDifflist (Difflist f) = f []
Để biến list thường thành difference list, ta đơn giản là biến nó thành hàm.
Khi Diff là 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 list, mempty đơn giản là hàm id còn mappend thực ra chính là phép hợp.
ghci> fromDifflist (toDifflist [1,2,3,4] `mappend` toDifflist [1,2,3])
[1,2,3,4,1,2,3]
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 Monoid từ [String] sang thành Difflist String rồi sau đó khi dùng tell, thì chuyển đổi list thường thành difference list bằng toDifflist.
ghci> mapM_ putStrLn . fromDifflist . snd . runWriter $ gcdReverse 110 34
Finished with 2
8 mod 2 = 0
34 mod 8 = 2
110 mod 34 = 8
runWriter sẽ gỡ bọc newtype, sau đó ánh xạ snd cho kết quả để lấy nội dung ghi chép, tiếp theo ánh xạ fromDifflist để chuyển đổi nó thành một list thông thường và cuối cùng là in toàn bộ ra màn hình.
17.9.5. So sánh hiệu nămg
Để hình dung difference list 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, 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])
Với bất kì số nào khác, ban đầu nó sẽ đếm các số trước, từ 0 và nối những số đó vào nội dung ghi chép.
ghci> mapM_ putStrLn . fromDifflist . snd . runWriter $ finalCountDown 500000
0
1
2
...
Tuy nhiên, nếu bạn thay difference list bằng list thường:
finalCountDown :: Int -> Writer [String] ()
finalCountDown 0 = do
tell ["0"]
finalCountDown x = do
finalCountDown (x-1)
tell [show x]
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.
17.10. Monad $(\rightarrow) r$
Trong chương nói về Applicative, ta đã thấy rằng kiểu hàm, $(\rightarrow) r$ là một Functor. Việc ánh xạ hàm $f$ lên hàm $g$ sẽ tạo ra một hàm nhận vào thứ mà $g$ nhận vào, rồi ánh xạ nó lên $g$, tiếp theo ánh xạ kết quả lên $f$. 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ả về kết quả, thì $f$ tác độ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 hàm là Applicative. 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 thành 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.
Kiểu hàm $(\rightarrow) r$ không chỉ là Functor và Applicative, mà còn là một Monad. Hàm 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 ánh xạ hàm lên thứ gì đó để thu được giá trị kết quả.
$(\rightarrow) r$ được định nghĩa ở module Control.Monad.Instances và nó trông như sau:
instance Monad ((->) r) where
return x = \_ -> x
h >>= f = \w -> f (h w) w
return nhận một giá trị rồi đặt nó vào trong ngữ cảnh tối thiểu, là hàm hằng luôn trả về một giá trị nhất định.
>>= có vẻ khá khó hiểu, khi dùng >>= để đưa một Monad vào trong hàm, thì kết quả luôn là Monad. Như vậy trong trường hợp này, khi ta đưa hàm $h$ vào hàm $f$, kết quả phải là hàm. Để tách $h$ ra khởi ngữ cảnh, ta phải ánh xạ $h$ lên thứ gì đó (trong trường hợp này là $w$), $f$ khi ánh xạ lên $(h\;w)$ trả về một Monad, trong trường hợp này là một hàm, vì vậy ta tiếp tục ánh xạ $f\;(h\;w)$ lên $w$.
17.11. Đại lượng trạng thái
Haskell không cho phép 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ả về kết quả. Mặt hạn chế này thực ra lại cho phép ta khỏ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, 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. Do đó, Haskell có một định nghĩa gọi là Monad State.
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ộ sinh số ngẫu nhiên rồi trả về 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ả về cùng với kết quả.
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 bộ sinh gen, random gen trả về Boolean cùng một bộ sinh mới. Để tung đồng xu thứ hai, ta đã dùng một bộ sinh mới, và cứ như vậy. Vì Haskell mang tính thuần túy, nên ta không thể thay đổi biến lưu trữ bộ sinh hiện có.
Nếu muốn hàm sinh nhiều số ngẫu nhiên cùng lúc đơn giản hơn, chúng ta có một cách mà không phải từ bỏ tính thuần khiết của Haskell. Đó là sử dụng Monad State.
Trước đó, ta sẽ nói rằng đại lượng có trạng thái là hàm nhận vào trạng thái nào đó rồi trả về giá trị cùng với trạng thái mới.
s -> (a,s)
$s$ là kiểu của trạng thái và $a$ là kết quả của phép tính có trạng thái.
Phép gán trong lập trình hàm được xem như hàm nhận vào một trạng thái (biến đã được gán trước đó) rồi trả về một kết quả (trong trường hợp này là 5) và một trạng thái mới.
Đại lượng trạng thái cũng có thể coi là một giá trị được gói trong 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 trạng thái ban đầu để 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.
Chúng ta sẽ xét một CTDL phổ biển là Stack, Stack sẽ có hai hàm cơ bản là push (đẩy giá trị vào) và pop (lấy giá trị ra) và có tính chất FILO (first in last out), tức là phần tử được thêm vào càng sớm sẽ được lấy ra càng muộn.
Ta sẽ dùng list để định nghĩa Stack, head của list sẽ là đỉnh Stack. pop sẽ lấy một giá trị trên đỉnh Stack và trả về kết quả là phần tử này cùng với Stack mới. push sẽ nhận một giá trị và một Stack rồi đẩy phần tử đó vào Stack, hàm này sẽ trả về kết quả là () và một Stack 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 sẽ lấy một Stack, đẩy 3 vào, rồi lấy hai phần tử ra:
stackManip :: Stack -> (Int, Stack)
stackManip stack = let
((),newStack1) = push 3 stack
(a ,newStack2) = pop newStack1
in pop newStack2
ghci> stackManip [5,8,2,1]
(5,[8,2,1])
Tuyệt, kết quả là 5 còn Stack mới là [8,2,1]. Lưu ý rằng stackManip là một đại lượng trạng thái. Ta đã lấy một loạt những đại lượng trạng thái rồi kết chúng với nhau.
Trong hàm stackManip, ta lưu trạng thái 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 Stack vào cho từng hàm, ta có thể viết như sau:
stackManip = do
push 3
a <- pop
pop
Monad State sẽ cho phép ta thực hiện đúng điều này. Với Monad State, 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.
17.12. Monad State
Module Control.Monad.State cung cấp newtype để bọc các đại lượng trạng thái.
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 trạng thái s và có một kết quả a.
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 hãy xét return. Mục đích của 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.
Còn về >>=, ta bắt đầu bằng gói bằng newtype State rồi viết tiếp một lambda. Lambda này là đại lượng trạng thái mới của ta. Đầu tiên ánh xạ đại lượng trạng thái s lên h, trả về kết quả và một trạng thái mới: (a, newState). Sau đó f a trả về đại lượng trạng thái mới g. Ánh xạ đại lượng trạng thái g lên newState sẽ nhận được kết quả cuối cùng và trạng thái cuối cùng!
Như vậy với >>=, ta đã kết hai đại lượng với nhau, chỉ có điều là đại lượng thứ hai được giấu trong hàm. 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 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 Int rồi trả về một đại lượng trạng thái.
import Control.Monad.State
stackManip :: State Stack Int
stackManip = do
push 3
pop
pop
Bạn đã thấy việc ta kết push và hai lần pop vào cùng một đại lượng trạng thái chưa.
ghci> runState stackManip [5,8,2,1]
(5,[8,2,1])
Nâng cấp hơn một chút, ta sẽ kiểm tra giá trị pop với 5, nếu đúng thì push trở lại Stack và dừng chương trình, ngược lại thì push 3 và push 8.
stackStuff :: State Stack ()
stackStuff = do
a <- pop
if a == 5
then push 5
else do
push 3
push 8
ghci> runState stackStuff [9,0,2,1,0]
((),[8,3,0,2,1,0])
Nhớ rằng, do cho kết quả là Monad và với Monad State, thì biểu thức do 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ể kết chúng lại để tạo thành những đại lượng trạng thái mới.
moreStack :: State Stack ()
moreStack = do
a <- stackManip
if a == 100
then stackStuff
else return ()
return () chỉ để giữ nguyên trạng thái và không làm gì cả.
Module Control.Monad.State còn cho chúng ta hai hàm là get và put. Đối với State:
get = State $ \s -> (s,s)
Nó 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 tạo một hàm trạng thái để thay thế trạng thái hiện thời:
put newState = State $ \s -> ((),newState)
stackyStack :: State Stack ()
stackyStack = do
stackNow <- get
if stackNow == [1,2,3]
then put [8,3,1]
else put [9,2,1]
Trong khi đó, kiểu của >>= với State:
(>>=) :: State s a -> (a -> State s b) -> State s b
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. Đố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ý vì >>= chỉ được sử dụng giữa hai Monad giống nhau. Đối với Monad State, thì thực ra Monad là State s.
17.12.1. Random Monad State
Ở phần đầu của mục này, ta đã thấy được việc sinh số ngẫu nhiên rất lủng củng vì hàm random nhận một bộ sinh rồi trả về một số ngẫu nhiên kèm theo bộ sinh mới, vốn sau đó bộ sinh tiếp tục được loại bỏ và thay mới. Monad State giúp cho việc này đơn giản hơn nhiều.
Hàm random trong System.Random có kiểu sau:
random :: (RandomGen g, Random a) => g -> (a, g)
Ta có thể thấy rằng (a, g) 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ó dưới dạng Monad.
import System.Random
import Control.Monad.State
randomSt :: (RandomGen g, Random a) => State g a
randomSt = State random
Khi muốn sinh 3 số ngẫu nhiên liên tiếp:
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)
threeCoins là một đại lượng trạng thái và sau khi nhận bộ sinh ngẫu nhiên ban đầu, hàm đó truyền bộ sinh này cho hàm randomSt đầu tiên, đến lượt nó lại tạo ra một số cùng một bộ sinh mới, rồi cứ như vậy. Ta dùng return (a,b,c) để biểu diễn (a,b,c) là kết quả mà không thay đổi bộ phát sinh gần nhất.
ghci> runState threeCoins (mkStdGen 33)
((True,False,True),680029187 2103410263)
Tác giả
Vũ Tuấn Hải - Monadotory