git.iko.soy/Haskell-HSE/haskell-lectures-2024
on main help sign in
Haskell-HSE/haskell-lectures-2024/4.Transformers.md
189 lines 6.6 kB history raw
1# Composition of side effects
3```haskell
4{-# LANGUAGE LambdaCase #-}
5{-# LANGUAGE QuantifiedConstraints #-}
7import Control.Applicative (liftA2)
8import Control.Monad (ap)
9```
11On our last lecture, we introduced the Parser monad:
13```haskell
14type Stream = String
16newtype ParseError = ParseError { reason :: String }
18newtype Parser a = Parser { runParser :: Stream -> Either ParseError (a, Stream) }
19```
21In essence, it was a combination of two side-effects: of signaling failure and
22of operating a stream state. Remember that we omitted a `Monad` instance for
23this type; if you have done it yourself, you should have noticed how tedious it
24was to just reiterate the same operations you did while writing instances for
25`Either` and `State`.
27Lucky for us, we don't have to repeat the same again and again for each monad
28you might introduce to your codebase. In this lecture, we'll learn how to
29properly compose side effects.
31## (Applicative) functors compose; Monads don't
33We know that functions can be composed: `\f g x -> f (g x)`. We can try and do
34the same with type operators:
36```haskell
37newtype Compose f g a = Compose { runCompose :: f (g a) }
38```
40Note that type parameters of `Compose` are different in their meaning: `a` is a
41simple type, while `f` and `g` are operators that, given a type, produce another
42type. In other words, `f` and `a` have different __kinds__: `a` is simply a
43`Type` (also called `*` for brevity) and `f` has kind `* -> *`. Most of the
44time, kinds are inferred just like types, but you can always specify the kind
45explicitly:
47```haskell ignore
48newtype Compose (f :: * -> *) (g :: * -> *) (a :: *) = Compose (f (g a))
49```
51This can be done also to specify more concrete types: for example, the first
52definition of `Compose` has slightly more general kinds which can be seen by
53typing `:i Compose` in GHCi after loading this `.lhs` file into it.
55Now, on to the instances of `Compose`. Every composition of functors is a
56functor:
58```haskell
59instance (Functor f, Functor g) => Functor (Compose f g) where
60 fmap h = Compose . fmap (fmap h) . runCompose
61```
63Moreover, every composition of applicative functors is an applicative functor:
65```haskell
66instance (Applicative f, Applicative g) => Applicative (Compose f g) where
67 pure = Compose . pure . pure
68 liftA2 h (Compose x) (Compose y) = Compose $ liftA2 (liftA2 h) x y
69```
71Things are going great! However, if one tries to write out an instance of a
72Monad in the same fashion, he would get stuck:
74```haskell ignore
75join :: Monad m => m (m a) -> m a
76join = (>>= id)
78instance (Monad f, Monad g) => Monad (Compose f g) where
79 x >>= f = Compose $ _ $ runCompose $ fmap (runCompose . f) x
80```
82More precisely, he would get stuck because writing out this instance also
83requires for `g` to _distribute_ over `f`; in other words, that there exists a
84function of a type `forall a. g (f a) -> f (g a)`. Does it exist for any pair of
85monads? Sadly, no.
87How do we get around this? We could encapsulate it into a typeclass and write
88out an instance for each possible pair, but there is a better solution: monad
89transformers.
91## Monad transformers
93The idea is that, instead of providing just a monad of kind `* -> *` which can
94be later used as-is, we provide a __monad transformer__ which adds a new
95capability to the monad provided by the user (in other words, transforms it).
96For example, to provide a capability to short-circuit the computation, we
97introduce a __maybe transformer__, in short `MaybeT`:
99```haskell
100newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
101```
103Notice how monads inside are composed: `Maybe (m a)` would be just "either
104`Nothing` or an effectful computation", while `m (Maybe a)` can short-circuit
105anywhere inside an effectful computation.
107`Functor` and `Applicative` instances can safely replicate instances for
108`Compose`:
110```haskell
111instance Functor f => Functor (MaybeT f) where
112 fmap f = MaybeT . fmap (fmap f) . runMaybeT
114instance Applicative f => Applicative (MaybeT f) where
115 pure = MaybeT . pure . pure
116 liftA2 h (MaybeT x) (MaybeT y) = MaybeT $ liftA2 (liftA2 h) x y
117```
119`Monad` instance replicates instance for `Maybe` except that we need to take `m`
120into consideration:
122```haskell
123instance Monad m => Monad (MaybeT m) where
124 MaybeT x >>= f = MaybeT $ x >>= \case
125 Just y -> runMaybeT (f y)
126 Nothing -> return Nothing
127```
129One more important example: to provide a read-only environment of type `e`, a
130transformer `ReaderT` is used:
132```haskell
133newtype ReaderT e m a = ReaderT { runReaderT :: e -> m a } deriving (Functor)
135instance Applicative f => Applicative (ReaderT e f) where
136 pure = ReaderT . pure . pure
137 liftA2 h (ReaderT x) (ReaderT y) = ReaderT $ liftA2 (liftA2 h) x y
139instance Monad m => Monad (ReaderT e m) where
140 ReaderT x >>= f = ReaderT $ \e -> x e >>= (\a -> runReaderT (f a) e)
141```
143Notice the common pattern: a transformer `t` is something that takes a base
144monad `m` and returns new monad `t m` augmented with new capabilities. This is
145encapsulated in a `MonadTrans` class:
147```haskell
148class (forall m . Monad m => Monad (t m)) => MonadTrans t where
149 lift :: Monad m => m a -> t m a
150```
152Really, this new method `lift` is to be expected: if transformer `t` adds new
153capabilities and retains all the old ones, you should be able to embed a
154computation of type `m a` into this computation of type `t m a` with added
155capabilities. Knowing the `Monad` typeclass, this wordy description can be
156expressed in just two laws:
158* `lift . return = return`
159* `lift (m >>= f) = lift m >>= (lift . f)`
161## Base monad
163Now, we learned how to add capabilities to the monad using monad transformers;
164but what do we take as a base monad? Actually, you can take any monad you like,
165for example a `State` monad. But if you look at the definition of `State` monad
166in Hoogle, you will see the following:
168```haskell ignore
169type State s = StateT s Identity
170```
172So `State` is also defined as a transformer? And with some other monad
173`Identity` as a base? Introducing the most basic monad of all, `Identity` monad:
175```haskell
176newtype Identity a = Identity { runIdentity :: a } deriving (Functor)
178instance Applicative Identity where
179 pure = Identity
180 (<*>) = ap
182instance Monad Identity where
183 Identity x >>= f = f x
184```
186Without all the discussion involving transformers, this definition looks useless
187the same way 0 looks useless if you've never done addition before. So Identity
188monad is like the most basic monad of all, adding no capabilities or
189side-effects to the computation whatsoever.