Exam Check-List: Discussion on Part 05 - Monads

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

Exam Check-List: Discussion on Part 05 - Monads

Beitrag von FeG »

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 :roll: ),
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
    
    Without the monad:

    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 specification.

    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 definition of a Monad type class and fix 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 fix 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.

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

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

Beitrag von sewe »

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
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

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

Beitrag von FeG »

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 specification.", I think I just got it. I changed my answer in the first post...

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

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

Beitrag von AlexanderF »

about 9:
FeG hat geschrieben: Find errors in the implementation of Monad instance for [Maybe/State/Error] monad and fix 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
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

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

Beitrag von FeG »

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 :wink:

Best,
Felix

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

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

Beitrag von AlexanderF »

Oh yes,
I'm sorry! :-)

Antworten

Zurück zu „Archiv“