Haskell #17: Monad (kế)

Haskell #17: Monad

17.13. Monad Either

Ta đã biết rằng kiểu Either e a cho phép ta kèm thêm thông báo lỗi vào giá trị hiện có khi ngữ cảnh là tính toán thất bại, chúng có thể mô tả được nguyên nhân hoặc cung cấp những thông tin khác về quá trình tính toán này. Either e a có thể là Right, chỉ thành công hoặc Left, chỉ thất bại.

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

Vì Either là giá trị được gói trong ngữ cảnh nên nó cũng là một Monad.

Monad Either được gói trong module 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 gói giá trị đang xét vào trong constructor Right vì ta đang dùng Right để biểu diễn quá trình tính toán thành công, trong đó có một kết quả.

Phép >>= kiểm tra hai trường hợp khả dĩ: Left và Right. Trong trường hợp Right, $f$ được ánh xạ lên giá trị $x$ bên trong. Trong trường hợp error, giá trị Left được giữ lại cùng nội dung mô tả lỗi.

Monad Either e yêu cầu kiểu của Left phải thuộc 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. Một ví dụ điển hình cho một kiểu thuộc lớp Error là String. Trong trường hợp với String, hàm strMsg chỉ việc trả về String mà nó nhận vào:

ghci> :t strMsg
strMsg :: (Error a) => String -> a
ghci> strMsg "boom!" :: String
"boom!"

Một số ví dụ:

ghci> Left "boom" >>= \x -> return (x + 1)
Left "boom"
ghci> Right 3 >>= \x -> return (x + 100)
Right 103
ghci> Right 100 >>= \x -> Left "no way!"
Left "no way!"

Khi dùng >>= để đưa một giá trị Left vào một hàm, thì giá trị Left giống hệt nó sẽ được trả về. Khi ta đưa một giá trị Right vào một hàm, thì hàm này ánh xạ giá trị bên trong Right.

17.14. Monad functions

Trong mục này, ta sẽ tìm hiểu một số hàm Monad.

17.14.1. Liftm

Lớp Applicative có một ràng buộc, theo đó kiểu phải là Functor. Mặc dù Monad phải có cùng ràng buộc này đối với Applicative, với lý do là Monad cũng là Applicative, thì sự thật lại không phải, vì lớp Monad tồn tại một số hàm tương ứng với fmap, như liftM:

liftM :: (Monad m) => (a -> b) -> m a -> m b

fmap :: (Functor f) => (a -> b) -> f a -> f b

Nếu Functor và Monad của một kiểu dữ liệu đều tuân theo tất cả định luật Functor và Monad, thì hai thứ này sẽ tương đương nhau. Điều này khá giống như pure và return cùng đặt giá trị vào ngữ cảnh tối thiểu, chỉ khác là ràng buộc lớp khác nhau:

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

Rõ ràng fmap và liftM tương tự nhau.

Đâ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 lệnh do:

liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = do
    x <- m
    return (f x)

Ta đưa Monad $m$ vào hàm rồi ánh xạ $f$ lên trước khi đặt kết quả vào lại ngữ cảnh tối thiểu. 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 không tham chiếu tới Functor. Điều này có nghĩa là Monad mạnh hơn những Functor thông thường mà ta đã gặp.

Kiểu Applicative cho phép ta ánh xạ 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

<$> chính 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

Trường hợp này, bản thân hàm cũng được gói trong một ngữ cảnh. Bằng cách nào đó, ta phải lấy hàm ra khỏi ngữ cảnh rồi ánh xạ nó lên giá trị được gói trong ngữ cảnh f a, tiếp theo lại gói kết quả vào ngữ cảnh. Hàm đều có tính curry nên ta có thể dùng tổ hợp của <$> và <*> để ánh xạ các hàm nhiều tham số lên các Applicative.

Trong Monad, <*> được định nghĩa tương đương với hàm ap, chỉ khác về ràng buộc lớp.

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap mf m = do
    f <- mf
    x <- m
    return (f x)

mf là Monad chứa hàm. Vì hàm này nằm trong ngữ cảnh nên ta có thể lấy hàm ra khỏi ngữ cảnh và gọi nó là $f$, sau đó lấy giá trị ra khỏi ngữ cảnh rồi gọi nó là $x$, và cuối cùng đem ánh xạ $f$ lên $x$ và gói kết quả vào ngữ cảnh tối thiểu bằng return.

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]

Như vậy, Monad cũng mạnh hơn Applicative. Mặc dù mọi Monad đều là Functor và Applicative, nhưng chúng không nhất thiết phải có các instance Functor và Applicative tương ứng.

17.14.2. LiftA-x

liftA2 là một hàm dùng để ánh xạ một hàm lên hai Applicative. 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 cũng tương tự, chỉ khác là nó có một ràng buộc lớp Monad. Ngoài ra cũng có các hàm liftM3, liftM4 và liftM5.

17.14.3. Join

Nếu kết quả của một Monad lại là một Monad khác, nghĩa là nếu một Monad được lồng vào trong Monad kia chẳng hạn Just (Just 9), thì hàm join sẽ ép phẳng Monad lồng thành Monad đơn giản hơn:

join :: (Monad m) => m (m a) -> m a

ghci> join (Just (Just 9))
Just 9
ghci> join (Just Nothing)
Nothing
ghci> join Nothing
Nothing

Việc ép phẳng list khá trực quan, với list thì join tương đương với concat:

ghci> join [[1,2,3],[4,5,6]]
[1,2,3,4,5,6]

Để ép phẳng Writer, ta phải mappend giữa các Monoid.

ghci> runWriter $ join (Writer (Writer (1,"aaa"),"bbb"))
(1,"bbbaaa")

Việc ép phẳng Either giống như ép phẳng 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 ánh xạ join lên đại lượng trạng thái với kết quả là một đại lượng trạng thái, thì kết quả sẽ là một đại lượng trạng thái mà trước hết hoạt động với đại lượng trạng thái bên ngoài, tiếp theo là đại lượng kết quả. Xem này:

ghci> runState (join (State $ \s -> (push 10,1:2:s))) [0,0,0]
((),[10,1,2,0,0,0])

Ở đây lambda nhận một trạng thái rồi đặt 2 và 1 lên Stack rồi lấy push 10 làm kết quả (tuple rỗng). Như vậy khi toàn bộ được ép phẳng bằng join thì trước hết 2 và 1 được đặt lên Stack rồi push 10 được thực thi, đẩy số 10 lên đỉnh Stack.

join được viết như sau:

join :: (Monad m) => m (m a) -> m a
join mm = do
    m <- mm
    m

Vì mm là một Monad gói một Monad khác, nên ta chỉ cần dùng m <- mm để lấy Monad bên trong ra ngoài, 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à Just chỉ khi các giá trị ngoài và trong đều là Just. Ví dụ, nếu mm là Just (Just 8):

joinedMaybes :: Maybe Int
joinedMaybes = do
    m <- Just (Just 8)
    m

Điều hay ở join là đối với mỗi Monad, m >>= f tương đương join (fmap f m). Bằng >>=, ta sẽ đưa một Monad vào một hàm nhận giá trị thường nhưng trả về Monad. Nếu ta chỉ ánh xạ hàm đó lên Monad, ta sẽ có một Monad bị gói trong Monad khác. Ví dụ (\x -> Just (x+1)) Just 9 trả về Just (Just 10).

17.14.4. filterM

Hàm filter chính là một trong những cốt lõi của. Hàm này nhận một hàm (vị từ) và list rồi trả về một list mới mà những phần tử trong đó thỏa mãn vị từ.

filter :: (a -> Bool) -> [a] -> [a]

ghci> filter (\x -> x < 4) [9,1,5,2,10,3]
[1,2,3]

Vị từ nhận vào một phần tử kiểu list rồi trả về Boolean. Bây giờ, ta sẽ thay thể Boolean bằng Monad và tạo ra một hàm mới có tên filterM, filterM được gói trong module Control.Monad.

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]

Ví dụ:

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ì trả Bool, hàm này trả về Writer [String] Bool. Đó là một vị từ Monad.

ghci> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
[1,2,3]

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

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 list trong khi vẫn tận dụng được ngữ cảnh Monad.

Một trong những ưu điểm của filterM đó là bài toán tìm tập con của tập hơn. Ví dụ như: [1,2,3] có các tập con là [1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], [].

Ta sẽ dựa vào sự bất định để giải quyết bài toán. Đàu tiên xét phần tử thứ nhất của list [1,2,3], tức là 1, rồi giữ lại hoặc bỏ đi. Như vậy, ta sẽ lọc list bằng một vị từ để vừa giữ lại, vừa bỏ đi từng phần tử một khỏi list.

powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs

ghci> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

17.14.5. foldM

Dạng Monad của foldl là foldM. foldl nhận vào một hàm hai ngôi, giá trị tích lũy và list. foldM cũng tương tự, chỉ khác là hàm hai ngôi tạo ra một Monad. Kiểu của foldl là như sau:

foldl :: (a -> b -> a) -> a -> [b] -> a

ghci> foldl (\acc x -> acc + x) 0 [2,8,3,1]
14

Còn foldM:

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a

Giá trị mà hàm hai ngôi trả về có tính Monad và vì vậy kết quả của toàn bộ phép fold cũng có tính Monad. Ta có thể thêm chức năng ngừng tính toán nếu có phần tử nào đó trong list lớn hơn 9 bằng Maybe thay vì kiểu thông thường. Sau đây là hàm Monad hai ngôi:

binSmalls :: Int -> Int -> Maybe Int
binSmalls acc x
    | x > 9     = Nothing
    | otherwise = Just (acc + x)

ghci> foldM binSmalls 0 [2,8,3,1]
Just 14
ghci> foldM binSmalls 0 [2,11,3,1]
Nothing

Vì có một số trong list lớn hơn 9, nên toàn bộ trở thành Nothing.

17.15. Hợp hàm Monad

Khi đọc các định luật Monad, hàm <=< đơn giản là phép hợp hàm.

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

Nếu ta có một loạt các hàm trong một list, ta có thể hợp tất cả thành một hàm bằng cách 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.

ghci> let f = foldr (.) id [(+1),(*100),(+2)]
ghci> f 3
501

Khi các hàm phức tạp hơn, trả về Monad thay vì giá trị thông thường thì ta dùng đến <=< và return thay cho id. Ta không cần dùng foldM thay cho foldr 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 Monad List 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ả về 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 đã nối 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:

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

Bằng cách dùng <=<, ta có thể giải quyết bài toán tổng quát hơn với $x$ lần quân Mã di chuyển.

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 để tạo list có chứa $x$ hàm moveKnight. Sau đó, ta hợp tất cả những hàm này làm một. Tiếp theo, ta chỉ việc biến ô xuất phát thành list 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 tổng quát hơn:

canReachIn :: Int -> KnightPos -> KnightPos -> Bool
canReachIn x start end = end `elem` inMany x start

17.16. Tạo Monad

Trong mục này, ta sẽ xét một ví dụ về cách tạo ra một kiểu Monad. Như đã thấy, list được dùng để biểu diễn giá trị bất định. Như [3,5,9] được gọi là bất định mà bản thân nó không tự quyết được sẽ là gì. Khi ta đưa list vào hàm bằng >>=, chương trình sẽ thực hiện tất cả những trường hợp khả dĩ sau đó biểu diễn tất cả kết quả dưới dạng list.

Nếu ta thêm thông tin về xác suất xuất hiện của mỗi phần tử trong list [3,5,9] thì chúng sẽ có dạng như sau, lưu ý rằng tổng xác suất phải luôn bằng 1:

[(3,0.5),(5,0.25),(9,0.25)]

Giá trị xác suất được biểu diễn từ 0 (không xảy ra) đến 1 ( chắc chắn xảy ra). Ngoài ra, để không bị mất thông tin dưới dạng số hữu tỉ, Haskell cho phép ta biểu diễn xác suất dưới dạng phân số bởi dấu %, gói trong module Data.Ratio.

ghci> 1%4
1 % 4
ghci> 1%2 + 1%2
1 % 1
ghci> 1%3 + 5%4
19 % 12

ghci> [(3,1%2),(5,1%4),(9,1%4)]
[(3,1 % 2),(5,1 % 4),(9,1 % 4)]

Trong trường hợp này, 3 có khả năng xuất hiện 50%, còn 5 và 9 sẽ là 25%.

Ta chọn list là ngữ cảnh cho tuple này và gói trong newtype.

import Data.Ratio

newtype Prob a = Prob { 
    getProb :: [(a, Rational)] 
} deriving Show

Rõ ràng list là một Functor nên ta có thể định nghĩa hàm fmap trên kiểu dữ liệu Prob.

instance Functor Prob where
    fmap f (Prob xs) = Prob $ map (\(x, p) -> (f x, p)) xs

Ta gỡ gói bằng pattern matching, ánh xạ $f$ lên giá trị bên trong khi vẫn giữ nguyên xác suất rồi gọi lại bằng Prob.

ghci> fmap negate (Prob [(3, 1 % 2),(5, 1 % 4),(9, 1 % 4)])
Prob {
    getProb = [(-3,1 % 2), (-5,1 % 4), (-9,1 % 4)]
}

Tiếp theo ta sẽ định nghĩa các hàm của Monad trên Prob để Prob là một Monad. Trước hết, 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 phải là 1!

Về >>=, nhớ rằng m >>= f tương đương join (fmap f m). Chẳng hạn, ta hãy xét list trong đó có 25% khả năng xuất hiện đúng một chữ ‘a’ hoặc ‘b’. Cả hai ‘a’ và ‘b’ đều cùng khả năng xuất hiện. Ngoài ra cũng có 75% khả năng là có đúng một chữ ‘c’ hoặc ‘d’ xuất hiện. ‘c’ và ‘d’ cũng có cùng khả năng có mặt. Tức $p(‘a’)=p(‘b’)=12.5\%$ và $p(‘c’)=p(‘d’)=37.5\%$.

Tuy nhiên, ta sẽ biểu diễn hoàn cảnh này bằng Prob:

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 hiện tại là Prob (Prob Char). Khi ép phẳng chúng, tức là đưa về kiểu Prob Char:

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 innerxs kiểu Prob Char và xác suất $p$ đi kèm rồi nhân xác suất bên trong innerxs với $p$. Ta ánh xạ multAll lên từng Prob Char rồi sau đó nối các kết quả thu được và đưa vào ngữ cảnh tối thiểu bằng hàm Prob.

Như vậy, Monad Prob có thể được định nghĩa rất đơn giản như sau:

instance Monad Prob where
    return x = Prob [(x, 1 % 1)]
    m >>= f = flatten (fmap f m)
    fail _ = Prob []

Một việc cũng quan trọng là kiểm tra xem liệu Monad Prob có thỏa mãn 3 định luật Monad hay không. Định luật đầu tiên phát biểu rằng return x >>= f tương đương f x. 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 ép phẳng, thì 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 đã có được bằng return, vì vậy sẽ không ảnh hưởng đến ngữ cảnh. Định luật 2 quy định m >>= return tương đương m cũng đơn giản. Định luật thứ ba phát biểu rằng f <=< (g <=< h) tương đương (f <=< g) <=< h. Điều này cũng thỏa mãn, vì phép nhân có tính kết hợp. $1\%2 * (1\%3*1\%5) = (1\%2 * 1\%3) * 1\%5$.

Monad Prob có thể được dùng để giải một số bài toán xác suất như sau. Chẳng hạn ta có hai đồng xu bình thường và một đồng xu được chế tạo để có khả năng sấp $90\%$. 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?

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

Khi gieo đồng xu:

import Data. list (all)

flipThree :: Prob Bool
flipThree = do
    a <- coin
    b <- coin
    c <- loadedCoin
    return (all (==Tails) [a,b,c])

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

Haskell #18: Zipper