2018-12-03 17:56

Monads

Sweeping computational details under the carpet in a systematic way

Page 2

Reflections on last week's lecture

We wrote a parser for arithmetic expressions

We saw that by using a parser combinator library we could
- Reduce the code size for the parser dramatically.
- Reduce the risk of making mistakes by abstracting away from tedious details.
While a parse generator (like Yacc, Happy, BNFC) provides a domain-specific language (DSL) for creating parsers…
…the parsing combinator library can be seen as an embedded domain-specific language (EDSL) for creating parsers in Haskell.
- It's just a library, not a language extension or separate language.
- This illustrates a key strenth of Functional Programming.
  - Enabled by higher-order functions, polymorphism, data types, type classes, monads and lazy evaluation.

Page 3

Pure functional programming

In Haskell, functions are pure:
- Same argument ⟹ same result, there are no hidden dependencies
- The returned value is the only result
  - There are no other effects that can change the result of the program
Is this good or bad?
- + It helps keep your code clean and modular.
- + It's good for automated testing.
- - Limits what you can do with functions...

Page 4

Functions in other languages

Functions can be pure, like in Haskell

int f(int x) { return 5*x; } int g() { return f(3); }
What does g() return?

Page 5

Functions in other languages

Functions can have additional inputs

int k=1; int f(int x) { return k*x; } int g() { k=5; return f(3); }
What does f(3) return?
Note that f has the same type as in the previous example.

Page 6

Functions in other languages

Functions can have additional outputs

int y=0; int f(int x) { y=x+1; return 2*x; } int g() { int z=f(10); return y+z; }
What does g() return?
Note that f has the same type as in the previous examples.

Page 7

Functions in other languages

Functions can change the state and do IO

int pageNr=0; int newPageNr() { pageNr++; return pageNr; } void startNewPage() { printf("\f--- Page %d ---\n",newPageNr()); }
newPage changes the state (has both extra input and extra output).
startNewPage changes the state and performs IO operations.

Page 8

Functions in other languages

Functions might not always return a result

int f(int i) { if(i<0 || i+1>=size) throw BadArgument; else return (a[i]+a[i+1])/2; } void g(int i) { try printf("Answer: %d",f(i)); catch(e) printf("Oops"); }
Many languages have exception handling.
Note that f has the same type as in the previous examples.

Page 9

Functions with additional effects in Haskell

All inputs and outputs have to be visible in the type:

Pure function:	� Input -> Output�
Extra input:	� Input -> Extra -> Output�
Extra output:	� Input -> (Extra,Output)�
Changing the state:	� Input -> State -> (State,Output)�
IO operations:	� Input -> IO Output�
Sometimes no result:	� Input -> Maybe Output�
Many results:	� Input -> [Output]�

But will it be practical to write programs with functions of these types?

Page 10

Combining functions with additional effects

Assume we want to define a function h that combines two functions f and g that both have additional effects.

 -- Pure functions: Input -> Output
h x = g (f x)

-- Extra input:     Input -> Extra -> Output
h x e = g (f x e) e

Page 11

Combining functions with additional effects

 -- Extra output:      Input -> (Extra,Output)
h x = (o1<>o2,y2)
  where
    (o1,y1) = f x
    (o2,y2) = g y1

-- Changing the state: Input -> State -> (State,Output)
h x s0 = (s2,y2)
  where
     (s1,y1) = f x s0
     (s2,y2) = g y1 s1

Page 12

Combining functions with additional effects

 -- IO operations:      Input -> IO Output
h x = do y1 <- f x
         y2 <- g y1
         return y2

-- Sometimes no result: Input -> Maybe Output
h x = case f x of
        Nothing -> Nothing
        Just y -> g y

-- Many results:
h x = [y2 | y1 <- f x, y2 <- g y1]

Page 13

The burden of dealing with extra effects

It looks like a lot of extra code to deal with extra effects!
- This requires no extra code in other languages...
Do we really want a pure functional language?
- It is not as bad as it looks!
- We could define operators to simplify things!
  - Use the power of higher order functions!

Page 14

Function application with effects (1a)

Example: Extra output

Instead of ‹h x = g (f x)› we had to write

h x = (o1<>o2,y2)
  where
    (o1,y1) = f x
    (o2,y2) = g y1

Can we define an operator ‹=<<› that hides all the glue code?>
- ```
h x = g =<< f x
```

Page 15

Function application with effects (1b)

Example: Extra output

Instead of ‹h x = g (f x)› we had to write

h x = (o1<>o2,y2)
  where
    (o1,y1) = f x
    (o2,y2) = g y1

Can we define an operator ‹=<<› that hides all the glue code?>
- ```
h x = g =<< f x
```

Yes! Solution:

g =<< fx = (o1<>o2,y2)
   where
     (o1,y1) = fx
     (o2,y2) = g y1

Page 16

Function application with effects (2)

What about other effects?
We will need different variants of the ‹=<<› operator for different extra effects.>
The different variants will have different types.
Can we use overloading?
- To do that, we need make ‹=<<› a method in a type class.>
- To do that, we factor out a common pattern from the different types.

Page 17

Types for functions with effects (1)

Taking another look at the types:

Type of effect	Function type
Pure function:	� Input -> Output�
Extra input:	� Input -> Extra -> Output�
Extra output:	� Input -> (Extra,Output)�
Changing the state:	� Input -> State -> (State,Output)�
IO operations:	� Input -> IO Output�
Sometimes no result:	� Input -> Maybe Output�
Many results:	� Input -> [Output]�

Can we factor out a common pattern?

Page 18

Types for functions with effects (2)

We can factor them like this:

Type of effect	The common pattern	The difference
Pure function:	� Input -> M Output�	� M `a�` = � `a�`
Extra input:	� Input -> M Output�	� M `a�` = � Extra -> `a�`
Extra output:	� Input -> M Output�	� M `a�` = � (Extra,`a`)�
Changing the state:	� Input -> M Output�	� M `a�` = � State->(State,`a`)�
IO operations:	� Input -> M Output�	� M `a�` = � IO `a�`
Sometimes no result:	� Input -> M Output�	� M `a�` = � Maybe `a�`
Many results:	� Input -> M Output�	� M `a�` = � [`a`]�

In all cases it can be seen as a modification of the return type!

Page 19

Monads and monadic programming

Monadic programming means using functions of type �
```
Input -> M Output�
```
,
- for some type �
```
M�
```
  .
The type �
```
M�
```
is the monad.
The type of "monadic function application":
- ```
 (=<<) :: (a -> M b) -> M a -> M b
```
Compare with the type of pure function application:
- ```
 ($)   :: (a -> b) -> a -> b
```
Now let's put ‹=<<› in a type class...>

Page 20

The Monad class

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a->m b) -> m b
  -- ...

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

This allows us to write overloaded functions that work in any monad.
There are many predefined monadic functions. Some are in the prelude, there are more in the library module Control.Monad.
Note that the type variable �
```
m�
```
above ranges over types that take a parameter.

Page 21

The do notation

The ‹do› notation is translated into expressions using ‹>>=›
- That's why it works for any monad!
Example:
- ‹do x <- m1; y <- m2 x; return (x+y)› ⟹

‹m1 >>= (\x -> do y <- m2 x; return (x+y))› ⟹

‹m1 >>= (\x -> m2 x >>= (\y -> return (x+y)))›

Page 22

Combining monadic functions

While using ‹=<<› or the ‹do› notation is enough, here are some more variants of function application that are also useful.>

Operator	Function	Argument	Result
‹$›	� ��`a`->`b�`	� `a�`	� ��`b�`
‹<$>›	� ��`a`->`b�`	� `m` `a�`	� `m` `b�`
‹<*>›	� `m` (`a`->`b`)��	� `m` `a�`	� `m` `b�`
‹=<<›	� ��`a`->`m` `b�`��	� `m` `a�`	� `m` `b�`

One could imagine more combinations, but the operators above are all defined in the standard libraries...
The operators ‹<$>› and ‹<*>› actually have their own type classes…

Page 23

Type classes relating to monads

f <$> x = fmap f x
f =<< m = m >>= f

Page 24

The Functor class

class Functor f where
  fmap :: (a->b) -> f a -> f b
  
f <$> x = fmap f x

This is not just for monads, but for any data structure where it makes sense to apply a function to every element.
It's a generalization of ‹map› for lists. Compare:

map  ::              (a->b) -> [a] -> [b]
fmap :: Functor f => (a->b) -> f a -> f b

Page 25

Functor vs the do notation

We have seen a few examples where using ‹<$>› simplifies the code:

rNumeric :: Gen Rank
rNumeric = do n <- choose (2,10)
              return (Numeric n)

```
rNumeric = Numeric <$> choose (2,10)
```

number :: Parser Integer
number = do ds <- oneOrMore digit
            return (read ds)

```
number = read <$> oneOrMore digit
```

Page 26

The Applicative class

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a->b) -> f a -> f b

There are more instances in the �
```
Applicative�
```
class than in the �
```
Monad�
```
class.
- ‹<*>› is easier to implement than ‹=<<›.>
- ‹pure› is the same as ‹return›. They both exist for historical reasons.

Page 27

Applicative vs the do notation

Here are some examples where using ‹<*>› simplifies the code:

rCard :: Gen Card
rCard = do s <- rSuit
           r <- rRank
           return (Card s r)

```
rCard = Card <$> rSuit <*> rRank
```

oneOrMore :: Parser item -> Parser [item]
oneOrMore item = do i <- item
                    is <- zeroOrMore item        
                    return (i:is)

oneOrMore item = (:) <$> item <*> zeroOrMore item

Page 28

Monadic Expression Evaluation

Returning to the arithmetic expressions we saw last week
Live demo: MonadicEvaluators.hs

Page 29

Final thoughts on the monadic evaluator

In examples small enough to fit on a slide, using monads like this is perhaps overkill.
The benefits show up when the code gets larger and you can add more effects to the monad without rewriting all of the code that uses it.
By using �
```
Either�
```
instead of �
```
Maybe�
```
we could return informative error messages ("division by zero" or "undefined variable") instead of ‹Nothing›.
- It only takes a few simple changes in the monad, the function ‹evalM› remains unchanged!

Page 30

Monads

Sweeping computational details under the carpet in a systematic way

Reflections on last week's lecture

We wrote a parser for arithmetic expressions

Pure functional programming

Functions in other languages

Functions can be pure, like in Haskell

Functions in other languages

Functions can have additional inputs

Functions in other languages

Functions can have additional outputs

Functions in other languages

Functions can change the state and do IO

Functions in other languages

Functions might not always return a result

Functions with additional effects in Haskell

Combining functions with additional effects

Combining functions with additional effects

Combining functions with additional effects

The burden of dealing with extra effects

Function application with effects (1a)

Example: Extra output

Function application with effects (1b)

Example: Extra output

Function application with effects (2)

Types for functions with effects (1)

Types for functions with effects (2)

Monads and monadic programming

The Monad class

The do notation

Combining monadic functions

Type classes relating to monads

The Functor class

Functor vs the do notation

The Applicative class

Applicative vs the do notation

Monadic Expression Evaluation

Final thoughts on the monadic evaluator

Further reading