## Exam Check-List: Discussion on Part 05 - Monads

FeG
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

### Exam Check-List: Discussion on Part 05 - Monads

Hi,

when I went through the monad slides and redid the according exercises, I though I understood the monads concept. Sadly, when trying to answer the check-list questions, especially the implementation questions, I ran into many problems, unresolved question marks, and frustration . I'd thus be very happy to get some helping comments on the open questions left below - in any case don't take this as any kind of "solution" (at least until Andreas commented on it), as I might have come up with completely wrong code examples for some tasks.

So far, hope the subsequent topics go more fluently (and that the monad tasks on Friday aren't the hardest ones ),
Felix

1. Give two concrete application scenarios of monads. Explain how they improve the design in these scenarios.

a) Non-functional computations: Non-functional computations do not on any input return a well-defined value, but result in, e.g., an error for some inputs (example: division (by zero)). When used in a process of multiple computations, implementations directly have to throw an error, halting the whole program. With monads (e.g., the Maybe Monad), the error can be indicated and handeled appropriate in later computation steps.

b) Passing state: The State monad allows to pass state within a computation process, which eases the representation of mutable entities, e.g., a database changing by queries applied to it.
2. Explain how monads can be used for error handling.

As an example use the Maybe monad, which allows to return a value "Just <value>" or "Nothing", which one may use interpreted as an error signal. A function in a process chain may now indicate an error by return the value "Nothing" (possibly within a larger data structure); a subsequent function in the process can handle this accordingly (e.g., remove "Nothing" values from a returned list, then further process it). That way, errors don't force a function to halt the program with, e.g., a call to "error".
3. Explain how monads can be used for modelling mutable state in a pure functional language.

The State monad allows to define state transformers, i.e., functions that, given a state, output a new (possibly modified) state and a result value. Subsequent function can now directly use the modified state as well as the result value. Thus, state is modeled as an object passed along a computation chain, where each step provides the subsequent one with a new, possibly altered, copy.
4. Given a program using the [Maybe/State/Error] monad, give an equivalent implementation without the monad.

Code: Alles auswählen

  type DB = [Integer]
type Query = Integer -> Bool
db = [3, 5, 10, 2, 6, 9, 7]
q1 = \n -> n > 4
q2 = \n -> n > 5
q3 = \n -> even n

doQuery q xs
| subset == [] = Nothing
| otherwise    = Just subset
where subset = filter q xs

queryAssemblyLine = (return db) >>= doQuery q1
>>= doQuery q2
>>= doQuery q3


Code: Alles auswählen

  doQuery q xs = filter q xs
queryAssemplyLine = doQuery q3 (doQuery q2 (doQuery q1 db))

[I assume there are more catchy examples...]
5. Given a program, re-implement it using [Maybe/State/Error] monad.

Code: Alles auswählen

  values = [1,2,5,10,20]

divide x []     = []
divide x (y:ys)
| y /= 0    = (x / y) : (divide x ys)
| otherwise = error "Division by 0."

filter (\x -> x > 1) (divide 10 values)

Re-implementation using Maybe monad:

Code: Alles auswählen

  values = [1,2,5,10,20]

divide x []          = []
divide x (Just y:ys)
| y /= 0 &&    = Just ((x / y) : (divide x ys))
| otherwise = Nothing

doFilter = return ... ???

--> divide results in nested Maybe-list, so: how does one implement such da function with monads??
6. Given a program in do-notation, reimplement it using explicit bind operations (or the other way around).

Code: Alles auswählen

  queryAssemblyLine = (return db) >>= doQuery q1
>>= doQuery q2
>>= doQuery q3

With do-notation:

Code: Alles auswählen

  queryAssemblyLine = do
db1 <- doQuery q1 db
db2 <- doQuery q2 db2
doQuery q3 db2

7. Implement a function working with [Maybe/State/Error] monad according to the given speciﬁcation.

Function provided a state being a list of integers, shall return the sum of all list elements as well as a new
state consisting of this sum added to the head of the old state list.

Code: Alles auswählen

sumlist :: State [Int] Int
sumlist = State (\s -> (foldr (+) 0 s, (foldr (+) 0 s) : s))

Use and calling:

Code: Alles auswählen

sumNtimes :: Int -> State [Int] Int
sumNtimes 0 = return 0
sumNtimes 1 = sumlist
sumNtimes x = do
sumlist
sumNtimes (x-1)

output :: [Int] -> State [Int] Int -> (Int, [Int])
output init (State m) = m init

-- calling:
output [1,2,3] sumlist == (6,[6,1,2,3])
output [1,2,3] (sumNtimes 0) == (0,[1,2,3])
output [1,2,3] (sumNtimes 3) == (24,[24,12,6,1,2,3])

8. Find errors in the deﬁnition of a Monad type class and ﬁx them.

Code: Alles auswählen

class Monad m where
return :: a -> m a
(>>=) :: m a -> a -> m b
(>>) :: m a -> m b -> mb
m >> n = m >>= \_ -> n

Has to be:

Code: Alles auswählen

class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> mb
m >> n = m >>= \_ -> n

9. Find errors in the implementation of Monad instance for [Maybe/State/Error] monad and ﬁx them.

Code: Alles auswählen

instance Monad Maybe where
(Just x) >>= f  = f x
Nothing  >>= f  = Nothing
return x        = x
fail s          = s

Has to be:

Code: Alles auswählen

instance Monad Maybe where
(Just x) >>= f  = f x
Nothing  >>= f  = Nothing
return x        = Just x    -- as return :: a -> m a      (must return a monad value)
fail s          = Nothing   -- as fail :: String -> m a   (must return a monad value)

10. Tell what the two monadic operations do. Describe their signatures.

Code: Alles auswählen

return :: a -> m a

Encapsulates a given value of type a in a monad.

Code: Alles auswählen

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

Takes a monad with a contained value of type a, passes this value to the second parameter, a function of type (a -> m b), which returns a monad containing a value of type b. This monad is returned.
Zuletzt geändert von FeG am 23. Aug 2012 11:21, insgesamt 1-mal geändert.

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Re: Exam Check-List: Discussion on Part 05 - Monads

FeG hat geschrieben:Re-implementation using Maybe monad:

Code: Alles auswählen

  values = [1,2,5,10,20]

divide x []          = []
divide x (Just y:ys)
| y /= 0 &&    = Just ((x / y) : (divide x ys))
| otherwise = Nothing

doFilter = return ... ???

--> divide results in nested Maybe-list, so: how does one implement such da function with monads??
OK, first you should decide what the signature of divide should be.

Let's suppose we want to stick to a specific monad (Maybe):

Code: Alles auswählen

divide :: Float -> [Float] -> [Maybe Float]
divide x []   = []
divide x (y:ys)
| y /= 0    = Just (x / y) : (divide x ys)
| otherwise = Nothing : (divide x ys)

This is not terribly exciting, in particular since we did not make use of the monad-specific functions >>=, return, and fail. So let's do that:

Code: Alles auswählen

divide x []   = []
divide x (y:ys)
| y /= 0    = return (x / y) : (divide x ys)
| otherwise = fail "" : (divide x ys)

If you don't fix a type explicitly but rather ask ghci about it (:t divide), it tells you that the type of divide is now (Eq a, Fractional a, Monad m) => a -> [a] -> [m a]; in particular, we now can use this piece of code with any monad.

So how do we "inject" the Maybe monad? By using divide in a context where type-inference tells Haskell that m = Maybe!

Code: Alles auswählen

import Data.Maybe
map isJust (divide 2 [1, 0, 2]) -- returns [True, False, True]
You can also get the non-Maybe behaviour back:

Code: Alles auswählen

import Data.Functor.Identity
map runIdentity (divide 2.0 [3.0, 0.0, 1.0]) -- returns [0.666666, error!

FeG
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

### Re: Exam Check-List: Discussion on Part 05 - Monads

Thanks for the explanation, which made this setting a bit clearer. However, the original type of divide (with Maybe) was

Code: Alles auswählen

divide :: (Fractional a) => a -> [Maybe a] -> [Maybe a]
So my question was more directed like "how can I use divide in a setting where it get's passed a list of 'Maybe Float' entries?".

Concerning task 7. "Implement a function working with [Maybe/State/Error] monad according to the given speciﬁcation.", I think I just got it. I changed my answer in the first post...

AlexanderF
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

### Re: Exam Check-List: Discussion on Part 05 - Monads

FeG hat geschrieben: Find errors in the implementation of Monad instance for [Maybe/State/Error] monad and ﬁx them.[/i]

Code: Alles auswählen

instance Monad Maybe where
(Just x) >>= f  = f x
Nothing  >>= f  = Nothing
return x        = x
fail s          = s

Has to be:

Code: Alles auswählen

instance Monad Maybe where
(Just x) >>= f  = f x
Nothing  >>= f  = Nothing
return x        = Just x    -- as return :: a -> m a      (must return a monad value)
fail s          = Nothing   -- as fail :: String -> m a   (must return a monad value)

I think it has to be:

Code: Alles auswählen

instance Monad Maybe where
(Just x) >>= f  = Just \$ f x  <- result type shoud be Maybe type
Nothing  >>= f  = Nothing
return x        = Just x
fail s          = Nothing


FeG
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

### Re: Exam Check-List: Discussion on Part 05 - Monads

Nope,

Code: Alles auswählen

(Just x) >>= f  = f x
is correct (cf. monads slides, p. 60).

The reason is that >>= from the monad class has type

Code: Alles auswählen

(>>=) :: m a -> (a -> m b) -> m b
i.e., f already has to return a monad.

But I agree that it looks strange at first sight. I had to look it up, too

Best,
Felix

AlexanderF
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Oh yes,
I'm sorry!