Haskell #17: Monad (kế)

Haskell #17: Monad

17.5. List Monad

Ta đã đề cập đến cách mà list biểu diễn các giá trị bất định khi xét list là một Applicative. Một giá trị (ví dụ 5) thì có tính tất định vì chúng ta biết chính xác đó là gì. Mặt khác, [3,8,9] thì không rõ ràng.

ghci> (*) <$> [1,2,3] <*> [10,100,1000]
[10,100,1000,20,200,2000,30,300,3000]

Khi xử lý dữ liệu bất định, ta có nhiều lựa chọn, vì vậy đơn giản là ta thử tất cả những lựa chọn đó.

Ngữ cảnh bất định này có thể biểu diễn bằng Monad.

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    fail _ = []

return nhận một giá trị và trả về ngữ cảnh tối thiểu, là list chỉ chứa một giá trị.

>>= lấy một giá trị kèm ngữ cảnh (Monad) và ánh xạ nó lên hàm, vốn nhận giá trị thường và trả về giá trị có ngữ cảnh. Nếu hàm đó chỉ tạo ra giá trị thường thay vì giá trị có ngữ cảnh, thì ngữ cảnh sẽ mất đi chỉ sau một lần gọi hàm.

ghci> [3,4,5] >>= \x -> [x,-x]
[3,-3,4,-4,5,-5]

Khi dùng >>= với list, nó giúp ta để ý đến sự bất định. [3,4,5] là một giá trị bất định và ta đưa nó vào một hàm, vốn cũng trả về một giá trị bất định, và nó cho thấy tất cả những giá trị cụ thể khi lấy các phần tử trong list [3,4,5] và truyền chúng vào cho hàm \x -> [x,-x]. Hàm này nhận một số rồi trả về hai kết quả: một số giữ nguyên và một số đảo dấu.

Trước hết, ta khởi đầu với list [3,4,5]. Sau đó ta ánh xạ lambda lên nó và kết quả như sau:

[[3,-3],[4,-4],[5,-5]]

Sau cùng, ta chỉ việc làm phẳng list bằng hàm concat.

Cũng giống như với các Maybe, ta có thể xâu list với >>=.

ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

[1,2] là n còn ['a','b'] là ch. return (n,ch) nghĩa là lấy một cặp (n,ch) và đặt nó vào ngữ cảnh tối thiểu. Điều chúng ta đang xét ở đây là: với từng phần tử trong [1,2], duyệt qua mỗi phần tử trong ['a','b'] rồi tạo ra một tuple chứa một phần tử trong mỗi list. Khi tương tác giữa những giá trị bất định, bạn có thể coi các đại lượng của chúng như một cây trong đó mỗi kết quả có thể trong list được biểu diễn bởi một cành riêng biệt.

Sau đây là biểu thức nói trên viết lại theo cú pháp do:

listOfTuples :: [(Int,Char)]
listOfTuples = do
    n <- [1,2]
    ch <- ['a','b']
    return (n,ch)

Cách viết này giống như chúng ta sử dụng list comprehension:

ghci> [ (n,ch) | n <- [1,2], ch <- ['a','b'] ]
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

Thực ra, list comprehension chỉ là cách viết tắt khi chúng ta tương tác với list Monad. List comprehension cho phép lọc đầu ra. Chẳng hạn:

ghci> [ x | x <- [1..50], '7' `elem` show x ]
[7,17,27,37,47]

Để thấy quá trình lọc trong list comprehension, ta cần kiểm tra hàm guard và lớp MonadPlus. Lớp MonadPlus là những Monad có thể đóng vai trò như Monoid:

class Monad m => MonadPlus m where
    mzero :: m a
    mplus :: m a -> m a -> m a

mzero tương đồng với mempty còn mplus tương ứng với mappend. Vì list vừa là Monoid, vừa là Monad, chúng có thể được làm thành instance của lớp MonadPlus:

instance MonadPlus [] where
    mzero = []
    mplus = (++)

Hàm guard được định nghĩa như sau:

guard :: (MonadPlus m) => Bool -> m ()
guard True = return ()
guard False = mzero

Nó nhận một giá trị Boolean và trong trường hợp True, thì nhận vào () rồi đặt nó vào trong ngữ cảnh tối thiểu. Ngược lại, chỉ cần trả về phần tử trung hòa mzero. Sau đây là cách dùng hàm này:

ghci> guard (5 > 2) :: Maybe ()
Just ()
ghci> guard (1 > 2) :: Maybe ()
Nothing
ghci> guard (5 > 2) :: [()]
[()]
ghci> guard (1 > 2) :: [()]
[]

Trong List Monad, ta dùng guard để lọc những đại lượng bất định:

ghci> [1..50] >>= (\x -> guard ('7' `elem` show x) >> return x)
[7,17,27,37,47]

Trước hết, hàm guard kết hợp với >>:

ghci> guard (5 > 2) >> return "cool" :: [String]
["cool"]
ghci> guard (1 > 2) >> return "cool" :: [String]
[]

Nếu guard thành công thì kết quả chứa trong nó là tuple rỗng. Vì vậy ta dùng >> để phớt lờ [()] và biểu diễn kết quả là thứ gì đó khác. Tuy nhiên, nếu guard thất bại, thì vế sau đó cũng vậy, vì [] được truyền vào >>= luôn trả về []. Về cơ bản, guard mang ý nghĩa: nếu False thì hãy tạo ra một thất bại ngay ở đây, còn không thì hãy tạo ra một kết quả tượng trưng là () bên trong nó.

Sau đây là ví dụ trước được viết lại bằng do:

sevensOnly :: [Int]
sevensOnly = do
    x <- [1..50]
    guard ('7' `elem` show x)
    return x

Nếu quên dùng return, thì list thu được là list chứa những tuple rỗng.

ghci> [ x | x <- [1..50], '7' `elem` show x ]
[7,17,27,37,47]

Vì vậy việc lọc list cũng giống như dùng guard.

17.5. Giải bài toán Knight Step

Sau đây là một bài toán rất thích hợp với cách giải có dùng tính bất định. Chẳng hạn có một bàn cờ vua và một quân Mã. Ta cần biết liệu quân Mã có đến được một ô nào đó sau ba nước đi hay không. Để biểu diễn vị trí, ta sẽ dùng một cặp gồm hai số. Con số thứ nhất dùng để chỉ hàng và con số thứ hai chỉ cột mà quân Mã đang đứng.

type KnightPos = (Int,Int)

Ví dụ, ban đầu Mã đứng ở (6,2), chúng ta sẽ kiểm tra nó có thể đi đến (6,1) sau 3 nước đi hay không. Nếu bắt đầu tại (6,2), nước đi tiếp theo sẽ là gì? Để giải, chúng ta xét tất cả các nước đi của Mã một lúc bằng hàm nhận vào vị trí của quân Mã rồi trả về tất cả những nước đi tiếp theo cuả nó.

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c,r) = do
    (c', r') <- [(c + 2, r - 1),(c + 2, r + 1),(c - 2, r - 1),(c - 2, r + 1)
               ,(c + 1, r - 2),(c + 1, r + 2),(c - 1, r - 2),(c - 1, r + 2)
               ]
    guard (c' `elem` [1..8] && r' `elem` [1..8])
    return (c', r')

Quân Mã di chuyển theo hình chữ L. (c',r') nhận từng giá trị từ list các nước đi và sau đó guard đảm bảo rằng nước đi mới hợp lệ.

Hàm này cũng có thể viết bằng filter:

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c,r) = filter onBoard
    [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)
    ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)
    ]
    where onBoard (c,r) = c `elem` [1..8] && r `elem` [1..8]

ghci> moveKnight (6,2)
[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]
ghci> moveKnight (8,1)
[(6,2),(7,3)]

Khi vị trí tiếp theo là bất định, ta chỉ việc dùng >>= để đưa nó vào moveKnight và lặp lại 3 lần:

in3 :: KnightPos -> [KnightPos]
in3 start = do 
    first <- moveKnight start
    second <- moveKnight first
    moveKnight second

hay:

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

Việc đặt một giá trị vào ngữ cảnh mặc định bằng cách áp dụng return rồi đưa nó vào trong hàm bằng >>= giống như ánh xạ lên cho giá trị.

Bây giờ, ta hãy tạo một hàm nhận vào hai vị trí rồi báo cho ta biết liệu có thể đi từ một vị trí này sang vị trí khác sau đúng ba nước:

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

Ta phát sinh tất cả những vị trí có thể trong ba bước rồi xét xem liệu vị trí mong muốn có nằm trong số đó không.

ghci> (6,2) `canReachIn3` (6,1)
True
ghci> (6,2) `canReachIn3` (7,3)
False

17.6. Định luật Monad

Giống như Applicative, và trước đó là Functor, luôn có một số định luật mà Monad tuân theo. Để một kiểu dữ liệu trở thành Monad thì kiểu đó phải thỏa mãn các định luật Monad. Những định luật này cho phép ta đặt nên những giả định hợp lý về kiểu dữ liệu cùng hành vi của nó.

17.6.1. Left identity

Định luật thứ nhất phát biểu rằng nếu ta nhận một giá trị, đặt nó vào trong một ngữ cảnh mặc định bằng return rồi ánh xạ nó lên hàm bằng >>=, thì tương đương với ánh xạ giá trị lên. Phát biểu chặt chẽ:

return x >>= f tương đương f x

Đối với Monad Maybe thì return là Just:

ghci> return 3 >>= (\x -> Just (x+100000))
Just 100003
ghci> (\x -> Just (x+100000)) 3
Just 100003

Đối với list, return đặt giá trị vào list đơn phần tử. >>= sẽ duyệt qua tất cả những giá trị trong list đó rồi ánh xạ hàm lên chúng, nhưng vì chỉ có một phần tử trong list nên việc này cũng giống như là ánh xạ hàm lên giá trị đó:

ghci> return "WoM" >>= (\x -> [x,x,x])
["WoM","WoM","WoM"]
ghci> (\x -> [x,x,x]) "WoM"
["WoM","WoM","WoM"]

17.6.2. Right identity

Định luật thứ hai phát biểu rằng nếu ta có một Monad và dùng >>= để đưa nó vào return, thì kết quả sẽ là Monad ban đầu ta có:

m >>= return tương đương m

Khi đưa Monad vào hàm bằng >>=, hàm nhận giá trị thông thường và trả về Monad. return cũng là một hàm như vậy, nếu xét đến kiểu của nó. return đặt giá trị vào trong ngữ cảnh tối thiểu. Điều này nghĩa là, chẳng hạn đối với Maybe, nó không trả về Nothing; và đối với list, nó không trả về đại lượng bất định.

ghci> Just "move on up" >>= (\x -> return x)
Just "move on up"
ghci> [1,2,3,4] >>= (\x -> return x)
[1,2,3,4]
ghci> putStrLn "Wah!" >>= (\x -> return x)
Wah!

Nếu nhìn kĩ hơn vào list:

xs >>= f = concat (map f xs)

Vì vậy khi ta đưa [1,2,3,4] vào return, đầu tiên return được ánh xạ lên [1,2,3,4], được kết quả là [[1],[2],[3],[4]], sau đó kết quả này được nối lại bằng hàm concat và ta lại được list ban đầu.

17.6.3. Tính kết hợp

Định luật Monad cuối cùng phát biểu rằng khi ta có một dãy các ánh xạ hàm nối bởi >>=, thì kết quả không bị ảnh hưởng bởi thứ tự ánh xạ.

(m >>= f) >>= g tương đương m >>= (\x -> f x >>= g)

Ta có Monad m và hai hàm f, g. (m >>= f) >>= g đã đưa m vào f, trả về Monad m'. Sau đó, ta đưa m' vào g. Trong biểu thức m >>= (\x -> f x >>= g), ta lấy Monad m đưa vào trong hàm vốn có nhiệm vụ đưa kết quả của f x vào g.

Sau đây là cách hiểu khác về định luật này: xét việc hợp hai hàm, f và g. Việc hợp hai hàm được thực hiện như sau:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = (\x -> f (g x))

Nếu như kiểu của g là a -> b và kiểu của f là b -> c, ta cần hàm mới có kiểu a -> c. Nếu f và g đều trả về Monad kiểu a -> m b, thì ta không thể đơn giản là truyền kết quả của f vào g kiểu b -> m c, vì g không nhận Monad. Tuy vậy, ta có thể dùng >>= để khiến điều này xảy ra. Như vậy là bằng cách dùng >>=, ta có thể hợp hai hàm.

(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> (a -> m c)
f <=< g = (\x -> g x >>= f)

Như vậy giờ ta đã có thể hợp hai hàm:

ghci> let f x = [x,-x]
ghci> let g x = [x*3,x*2]
ghci> let h = f <=< g
ghci> h 3
[9,-9,6,-6]

Khi nhìn định luật dưới hình thức hàm hợp f <=< (g <=< h) tương đương (f <=< g) <=< h.

Nếu ta chuyển hai định luật đầu về <=<, thì định luật Left identity phát biểu rằng với mỗi hàm f thì f <=< return tương đương f, định luật Right identity phát biểu rằng return <=< f tương đương f.

Điều này giống với nhận định (f . g) . h giống f . (g . h), f . id giống f và id . f giống f.

Haskell #17: Monad (kế)