Chapter 13, Monads
Ch 13: Monads
Copyright By PowCoder代写 加微信 powcoder
University of the Fraser Valley
COMP 481: Functional and Logic Programming
• Intro to Monads
• Tightrope Walking Simulation (Pierre)
• Banana on a Wire
• `do` Notation
• Pattern Matching and Failure
• The List Monad
• `MonadPlus` and the `guard` Function
• A Knights Quest
• Monad Laws
• Left Identity
• Right Identity
• Associativity
• More Simplifications
— Intro to Monads —
We have worked with implementing applicatives for
various types so that:
• `Maybe a` values represent computations that may end up in failure
• `[a]` values represent all possible computational results
(nondeterministic)
• `IO a` values represent computations with side effects
These can be facilitated with the special characters `>>=` as a binary
operation between Monad values. This function is called bind.
Monads are a type class with similar behaviour as
`Functors` and `Applicatives` to make functions work in
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
This time, we want:
• to take an input value with some context `m a`
• a function that expects no input context `a ->`
• but the function returns a result `m b` with context when applied on
the input `m a`
Recall how we mapped with functors:
ghci> fmap (++”!”) (Just “wisdom”)
Just “wisdom!”
ghci> fmap (++”!”) Nothing
• a value of `Nothing` as a result of such a mapping can be interpreted
as a failure for some calculation
functors have the added context to the function
ghci> Just (+3) <*> Just 3
ghci> Nothing <*> Just “greed”
ghci> Just (ord) <*> Nothing
• if either of the operands is `Nothing` it is propagated to the result
Applicative
<$> and <*>
There was also the applicative style:
ghci> max <$> Just 3 <*> Just 6
ghci> max <$> Just 3 <*> Nothing
Implementation
Now the implementation of the `Monad` type class:
class Applicative m => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
x >> y = x >>= \_ -> y
• the `return` function is the same as `pure` as we saw it in the
`Applicative` type class
• recently Haskell developers decided it would be a requirement to make
any `Monad` also be a subclass of `Applicative`
• just a reminder that `return` is not like in other programming
languages—here it simply wraps a value within the context of `m`
• the `>>` operation has a default implementation that is rarely
• there also used to be a `fail` function, but that is no longer required
to implement an instance of `Monad`
The `Maybe` type as an instance of `Monad`:
instance Monad Maybe where
return x = Just x
Nothing >>= f = Nothing
Just x >>= f = f x
• if there is `Nothing` input on the left-hand side of `>>=`,
the expression evaluates also to `Nothing`
• otherwise, there is a nested value within `Just` and we can apply the
function `f` to it
• note that the result of `f` is in a context with
a nested value that at least has the same type as `x`
Now we give `Maybe` a try as a monad:
ghci> return “WHAT” :: Maybe String
Just “WHAT”
ghci> Just 9 >>= \x -> return (x*10)
ghci> Nothing >>= \x -> return (x*10)
— Tightrope Walking Simulation —
We will demonstrate one of the advantages of monads:
• change the behaviour of calculations in the way we desire
• context of a monad can participate in the computation
• we cannot do this with applicatives alone, since
they only lift computations into the nested context
Tightrope Walking
Suppose we have a man Pierre
that tightrope walks with a pole:
• birds land on either side of the pole
• if more than a difference of 3 birds land on
either side, Pierre falls…
(to a safety net, of course)
Photographer: (CC BY 3.0)
https://creativecommons.org/licenses/by/3.0/
Simulation
We will first implement a few types to
help us keep track of the number of birds:
type Birds = Int
type Pole = (Birds, Birds)
Next we want functions to simulate birds
landing on either side of the pole:
landLeft :: Birds -> Pole -> Pole
landLeft n (left, right) = (left + n, right)
landRight :: Birds -> Pole -> Pole
landRight n (left, right) = (left, right + n)
We try out our functions without monads:
ghci> landLeft 2 (0, 0)
ghci> landRight 1 (1, 2)
ghci> landRight (-1) (1, 2)
• just use a negative number to simulate birds flying away
Operations
Chain simulated birds landing by nesting operations:
ghci> landLeft 2 (landRight 1 (landLeft 1 (0, 0)))
• we can create a utility function to help us write more concisely:
x -: f = f x
• then we can write the parameter before the function, and rewrite
our previous expression:
ghci> (0, 0) -: landLeft 1 -: landRight 1 -: landLeft 2
Failure (1)
So far, this does not check our condition for if Pierre will
• if we did any lopsided landing of birds,
then we just get back the ordered pair
• instead, we would like to check for Pierre’s failure,
so we use `Maybe`
Failure (2)
Implement new versions of our bird-landing
simulation functions:
landLeft :: Birds -> Pole -> Maybe Pole
landLeft n (left, right)
| abs (left + n – right) < 4 = Just (left + n, right) | True = Nothing landRight :: Birds -> Pole -> Maybe Pole
landRight n (left, right)
| abs (left – right – n) < 4 = Just (left, right + n)
| True = Nothing
Simulating
• Our implementation will maintain a difference of three for the
number of birds on either side of the pole
• if > 3, the result of any `landLeft` or `landRight` will be `Nothing` to
indicate imbalance and represent falling
• since these versions of our functions:
• take a `Pole` for input,
• but a `Maybe Pole` for output,
• we will need to make use of `>>=`
• to apply successive operations together
ghci> return (0, 0) >>= landLeft 1 >>= landRight 1 >>= landLeft 2
Just (3,1)
return (0, 0) >>= landLeft 1 >>= landRight 1 >>= landLeft 2
• note that we had to begin the calculation with the context of a
monad, so we used `return`
• the `return` function can be used no matter the specific application
of a monad context for a sequence of calculations
Finally, let’s see Pierre fall!
ghci> return (0, 0) >>= landLeft 1 >>= landRight 4
>>= landLeft (-1) >>= landRight (-2)
• can you tell at which point the pole became imbalanced?
Try to make sure you do not conflate the context of the
monad with the functions used:
• monad is `Maybe` and NOT the functions `landLeft` and `landRight`
• the functions have merely been edited to
take advantage of `Maybe` as a monad
— Banana on a Wire —
We implement more functions that can combine with the
other computations we have designed for simulation:
• suppose a banana on the wire could slip Pierre while walking
• this automatically forces Pierre to fall
banana :: Pole -> Maybe Pole
banana _ = Nothing
It is fairly clear what will happen when we use this
ghci> return (0, 0) >>= landLeft 1 >>= banana >>= landRight 1
Default >>
To ignore a monadic value on the right and return the left
value, we can adjust the `>>` operation from its default:
(>>) :: (Monad m) => m a -> m b -> m a
n >> m = m >>= \_ -> n
Otherwise, the default is to ignore the left value and
return the right value, equivalent to the `do` block:
for monad values n and m, the above returns m.
ghci> Nothing >> Just 3
ghci> Just 3 >> Just 4
ghci> Just 3 >> Nothing
(keep in mind the above demonstrates the default implementation!)
Thus, we can omit having to write a `banana` function,
and just use `>> Nothing` to the same effect.
— `do` Notation —
We can use monad-style expressions with lambdas:
ghci> Just 3 >>= (\x -> Just (show x ++ “!”))
• monadic value `Just 3` has its nested `3` passed
as input into the lambda on the right side
• a monadic value is returned `Just “3!”`
The above expression can be rewritten as two nested `>>=`
operations:
ghci> Just 3 >>= (\x -> Just “!” >>= (\y -> Just (show x ++ y)))
Notice >>= “binds” an unwrapped value to the parameter.
The expression can be rewritten as two nested `>>=`:
ghci> Just 3 >>= (\x -> Just “!” >>= (\y -> Just (show x ++ y)))
Notice >>= “binds” an unwrapped value to the parameter.
• this is similar to the following:
in show x ++ y
The advantage of the more elaborate version:
• we get monads to help manage context
• at each part of the calculation
• without needing to explicitly write code at each stage to deal with it
ghci> Nothing >>= (\x -> Just “!” >>= (\y -> Just (show x ++ y)))
ghci> Just 3 >>= (\x -> Nothing >>= (\y -> Just (show x ++ y)))
ghci> Just 3 >>= (\x -> Just “!” >>= (\y -> Just Nothing))
Just Nothing
• at each point, the value could instead be `Nothing`,
and the result is dealt with appropriately without error
We move toward a nicer syntax available, first, in the form
of a function:
foo :: Maybe String
foo = Just 3
>>= (\x -> Just “!”
>>= (\y -> Just (show x ++ y)
• there is an alternative cleaner syntax available with the `do` block
foo :: Maybe String
x <- Just 3 y <- Just "!" Just (show x ++ y) foo :: Maybe String x <- Just 3 y <- Just "!" Just (show x ++ y) • the `do` block allows a different way to chain monadic calculations into one monadic calculation • if any of the monadic values is a `Nothing` then the result of the `do` expression will be `Nothing` • lines that are not monadic value have to be in a `let` expression • we use `<-` assignment to obtain a nested value (bind) • if we have a Just "!" monadic value, the nested value is "!" as a `String` type • if we have a `Just 3` monadic value, the nested value is `3` as a numeric type • the last line of a `do` block cannot use `<-`, since this would not make sense as the result returned for a monadic expression The typical design: • to compute and assign nested values • on each line of the `do` block • and return them in some combined expression • within the monadic context Equivalent One more small example: ghci> Just 9 >>= (\x -> Just (x > 8))
marySue :: Maybe Bool
marySue = do
x <- Just 9 Just (x > 8)
ghci> mary True
(Simranjit Singh)
— various types of addition
— infix (any func that’s a special symbol is automatically infix)
— functor
fmap (+1) [1,2,3]
(+1) <$> [1,2,3]
— applicative functor
[(+1)] <*> [1,2,3]
[(+)] <*> [1] <*> [1,2,3]
pure (+) <*> [1] <*> [1,2,3]
(+) <$> [1] <*> [1,2,3]
(Simranjit Singh)
[1] >>= \x -> return (x+1)
[1,2,3] >>= \x -> return (x+1)
— nested >>= operations
[1,2,3] >>= \x -> return (x+1) >>= \y -> return (y+1)
— alternative do block
x <- [1,2] y <- [3,4,5] return $ x + y + 1 Simulation We can rewrite our previous example of Pierre's tightrope walking with a simulation for birds landing on a pole. We now design it in a `do` block: routine :: Maybe Pole routine = do start <- return (0, 0) first <- landLeft 2 start second <- landRight 2 first landLeft 1 second ghci> routine
Just (3,2)
• each line of a `do` block depends on the success of the previous one
Without monads, this issue can be seen differently where
computation would have to be nested:
routine :: Maybe Pole
routine = case Just (0, 0) of
Nothing -> Nothing
Just start -> case landLeft 2 start of
Nothing -> Nothing
Just first -> case landRight 2 first of
Nothing -> Nothing
Just second -> landLeft 1 second
• the ghci session will issue a warning with the above code, but you
should still be able to issue `routine`
Overwrites
Then if we want to throw in a banana peel like we did
routine :: Maybe Pole
routine = do
start <- return (0, 0) first <- landLeft 2 start second <- landRight 2 first landLeft 1 second • the line with `Nothing` does not use `<-`, much like our use of `>>` to ignore a previous monadic value
• this is nicer than needing to write equivalently `_ <- Nothing`
It is up to you whether you want to use `>>=` versus `do`
blocks, but in general:
• to avoid naming prior results, use `>>=`
• to mix together multiple previous results, use `do` blocks
Neither is exclusively needed to accomplish the above…
— Pattern Matching and Failure —
Pattern matching can be used on a binding:
justH :: Maybe Char
justH = do
(x:xs) <- Just "hello" • the above grabs the first letter of the string "hello" • the `justH` function evaluates to `Just h` • remember, the left value of a `:` operation is a `Char`, not a singleton When a pattern match fails within a function: • the next pattern is attempted • if matching falls past all patterns, the function throws an error • the program crashes With `let` expressions, an error occurs on failure of matching because there is no falling mechanism for matching further patterns. Implementing When matches fail within a `do` block: • the context of the monad often implements a `fail` function • to deal with the issue in its context • as we have seen with the `Maybe` type • this used to be implemented as part of a default `Monad` function • it is now dealt with as an instance of the `Monad` type with a custom implementation of `fail` per each type For example, with `Maybe` as a `Monad`, we can implement: fail :: Maybe a -> Maybe a
fail _ = Nothing
• but `fail` is a default function to throw an error with String message
• then when all patterns fall through unmatched within a `do` block,
the function expression will evaluate to `Nothing` instead of crashing
wopwop :: Maybe Char
wopwop = do
(x:xs) <- Just "" ghci> wopwop
• there is only a failure mitigated within the context of monad `Maybe`
• there is no program-wide failure
— The List Monad —
Recall that we can do nondeterministic calculations with
lists using the applicative style:
ghci> (*) <$> [1,2,3] <*> [10, 100, 1000]
[10,100,1000,20,200,2000,30,300,3000]
Let us now see the implementation of `Monad` for lists:
instance Monad [] where
return x = [x]
xs >>= f = concat (map f xs)
fail _ = []
• `return` just puts the input value within
minimal list contex, i.e.: a singleton `[x]`
The function `concat` might seem not to fit the context, but
we want to implement nondeterminism.
ghci> [3,4,5] >>= \x -> [x,-x]
[3,-3,4,-4,5,-5]
• as you can see, all the possible results of `[3,4,5]`
fed into `\x -> [x, -x]` are shown as one conjoined list
The `>>=` operation can handle `[]`:
ghci> [] >>= \x -> [“bad”, “sad”]
ghci> [1,2,3] >>= \x -> []
It is possible to chain `>>=` operations to propagate the
nondeterminism:
ghci> [1,2] >>= \n -> [‘a’,’b’] >>= \ch -> return (n, ch)
[(1,’a’),(1,’b’),(2,’a’),(2,’b’)]
• notice that the input variable `n` shows up as part of the final
expression after the next `>>=` operation
• remember, each next `>>=` operation is nested as part of the previous one
• `return` places each pair within a singleton context
• all the pairs are concatenated together into one flat list
Describing the propagation of nondeterministic operations:
• “for all” elements in `[1,2]` should be paired
• with every element of `[‘a’,’b’]`.
The previous expression could be written in a `do` block,
but you might find the following syntax easier to read:
>>= \n -> [‘a’,’b’]
>>= \ch -> return (n, ch)
[(1,’a’),(1,’b’),(2,’a’),(2,’b’)]
`do` Block
Otherwise, in a module, I would use a `do` block:
listOfTuples :: [(Int, Char)]
listOfTuples = do
n <- [1,2] ch <- ['a','b'] return (n, ch) ghci> listOfTuples
[(1,’a’),(1,’b’),(2,’a’),(2,’b’)]
• these syntax make the nondeterminism clearer to keep track of
• `n` takes on every value of `[1,2]`
• `ch` takes on every value of `[‘a’,’b’]`
Similar to List
Comprehension
Lastly, we had originally learned list comprehension to do
essentially the same thing as above:
ghci> [ (n, ch) | n <- [1,2], ch <- ['a','b'] ] [(1,'a'),(1,'b'),(2,'a'),(2,'b')] • the `<-` notation works pretty much the same, to handle the nondeterministic context for us • we did not need to use the `return` function because list comprehension takes care of that for us • documentation typically calls alternatives such as this syntactic sugar for the more formally written expressions — `MonadPlus` and the `guard` Function — List comprehension can apply filtering with a conditional expression: ghci> [ x | x <- [1..50], '7' `elem` show x ] [7,17,27,37,47] The `MonadPlus` type class is for implementing filtering. • it is for monads that can also act as monoids class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a
• `mzero` is synonymous with `mempty` from `Monoid`
• `mplus` corresponds to `mappend`
We know lists are both monads as well as monoids, so:
instance MonadPlus [] where
mzero = []
mplus = (++)
• a failed computation for lists is an empty list
• `mplus` concatenates two nondeterministic computational results
There is also a `guard` function that helps perform filters:
import Control.Monad
guard :: (MonadPlus m) => Bool -> m ()
guard True = pure ()
guard False = mzero
• a Boolean expression is input into `guard` as the test to either create
a dummy value or nothing (`mzero`)
• empty tuple `pure ()` is used as a dummy and used to then filter
• input into `>>` operations on the left side, it will either keep or throw
away the right-hand side values
ghci> import Control.Monad
ghci> guard (5 > 2) >> return “cool” :: [String]
ghci> guard (1 > 2) >> return “cool” :: [String]
There are two ways we can write the use of `guard` in order
to filter as in the list comprehension:
• the first is with nested `>>=` expressions
• the second is within a `do` block
ghci> [1..50] >>= (\x -> guard (‘7’ `elem` show x) >> return x)
[7,17,27,37,47]
sevensOnly :: [Int]
sevensOnly = do
x <- [1..50] guard ('7' `elem` show x) ghci> sevensOnly
[7,17,27,37,47]
import Control.Monad
— Using list1, create all possible pairs (x, y)
— such that x is always greater than y
list1 = [1, 2, 3, 4, 5]
listCompPairs =
[(x, y) | x <- list1, y <- list1, x > y]
nestedMethodPairs =
list1 >>= (\x -> list1 >>= (\y -> guard (x > y) >> return (x, y)))
doMethodPairs = do
x <- list1 y <- list1 guard (x > y)
return (x, y)
— A Knights Quest —
Simulating
Knights in
We would like to simulate on a chess board, a knight which
has a restricted `L` move each turn.
Are they able to reach a square within three turns?
• the image below shows the positions in one turn where a knight
piece could choose to move
• it should be symmetrical, and there are two spots missing behind the
first row, but the pieces cannot move off the board
We use a pair to keep track of the row and the column
• the first number gives the row
• the second number gives the column
type KnightPos = (Int, Int)
So, if the knight starts at position `(6, 2)`, can they move to `(6, 1)`?
• we might w
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com