CS代考 COMP 481: Functional and Logic Programming

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