git.iko.soy/Haskell-HSE/haskell-lectures-2024
on main help sign in
Haskell-HSE/haskell-lectures-2024/2.Laws.md
296 lines 9.7 kB history raw
1# Typeclass laws
3In the previous lecture, we introduced typeclasses as Haskell's analogue of
4interfaces. Sometimes, good documentation of an interface explicitly describes a
5set of invariants any implementation should uphold; in the case of Haskell, it
6is a common rule of good manners to provide _typeclass laws_ for any typeclass
7you define. For example, `Semigroup` and `Monoid` classes from Haskell's
8standard library are defined like this:
10```haskell ignore
11-- | The class of semigroups (types with an associative binary operation).
12--
13-- Instances should satisfy the following:
14--
15-- [Associativity] @x '<>' (y '<>' z) = (x '<>' y) '<>' z@
16class Semigroup a where
17 -- | An associative operation.
18 --
19 -- >>> [1,2,3] <> [4,5,6]
20 -- [1,2,3,4,5,6]
21 (<>) :: a -> a -> a
23-- | The class of monoids (types with an associative binary operation that
24-- has an identity). Instances should satisfy the following:
25--
26-- [Right identity] @x '<>' 'mempty' = x@
27-- [Left identity] @'mempty' '<>' x = x@
28class Semigroup a => Monoid a where
29 -- | Identity of '<>'
30 --
31 -- >>> "Hello world" <> mempty
32 -- "Hello world"
33 mempty :: a
34```
36An instance of a typeclass which abides its laws is called a "lawful instance".
37While nothing stops you from making a non-lawful instance, you should
38nevertheless try to make your instances lawful because typeclass laws usually
39capture an important intuition about an interaction between operations inside a
40class: for example, we can safely omit parentheses while working with a lawful
41semigroup instance, but with non-lawful instance we cannot.
43__Exercise 1__: define a function `foldList :: Monoid a => [a] -> a` which
44reduces a list using methods from `Monoid` typeclass. Which laws did you
45implicitly rely on during the implementation?
47__Exercise 2__: some types can be viewed as a monoid in more than one way, e.g.
48both addition and multiplication on numbers. In such cases we often define
49`newtype`s and make those instances of `Monoid`. Implement `Monoid` instances
50for these newtypes defined below. What is needed of `Num a` instance for Monoid
51laws to hold?
53```haskell
54newtype Sum a = Sum { getSum :: a }
56newtype Mul a = Mul { getMul :: a }
57```
59__Exercise 3__. Using newtypes above and the instances you've written, define
60functions `sumList :: Num a => [a] -> a` and `productList :: Num a => [a] -> a`
61via `foldList` defined before.
63Solutions to all exercises are given at the end of this file.
65## Endofunctor class hierarchy
67### Foldable
69Typeclasses are actually more powerful than their counterparts in other
70languages. Most notably, we can define typeclasses which describe an interface
71of a generic type instead of a concrete type. For example, a `Foldable` class
72describes a type of generic collections whose contents can be folded with a
73monoid operation:
75```haskell ignore
76class Foldable (t :: * -> *) where
77 foldMap :: Monoid b => (a -> b) -> t a -> b
78```
80__Exercise 4__. Make the following tree type into `Foldable` by writing down an
81instance for it:
83```haskell
84data BinTree a = Leaf | Branch (BinTree a) a (BinTree a)
85```
87### Functor
89Just like with folding, a capability of mapping over elements of a container is
90captured in a typeclass:
92```haskell ignore
93class Functor (f :: * -> *) where
94 fmap :: (a -> b) -> f a -> f b
95```
97The Functor laws capture an important property that mapping over elements should
98not change an overall internal structure of a container. In other words,
1001. `fmap id x = x` (Identity);
1012. `fmap g (fmap f x) = fmap (g . f) x` (Composition).
103__Exercise 5__. Write out a lawful instance of `Functor BinTree`.
105However, Functor laws are so strict that, if you can write out a lawful
106instance, every other possible instance would behave the same. Luckily for us,
107we can derive such an instance automatically. For example, for `BinTree` we
108could do the following:
110```haskell ignore
111data BinTree a = Leaf | Branch (BinTree a) a (BinTree a) deriving (Functor)
112```
114### Applicative
116Actually, there are things more powerful than functors: applicative functors.
118```haskell ignore
119class Functor f => Applicative f where
120 pure :: a -> f a
121 (<*>) :: f (a -> b) -> f a -> f b
122 liftA2 :: (a -> b -> c) -> f a -> f b -> f c
123```
125As notation and types are a little tricky, let us explain them bit by bit.
127* At first sight, applicative functors can be seen as a generalization from
128 lifting unary functions (`fmap`) to lifting functions of arbitrary arity:
129 `pure x` is a lifting of an 0-ary function `x`; `liftA2` (read as lift
130 applicative binary) lifts binary functions, and each and every `liftAN` can
131 be written out in terms of `pure` and `(<*>)`:
133```haskell ignore
134liftA1 :: Applicative f => (a -> b) -> f a -> f b
135liftA1 g fa = pure g <*> fa
137(<$>) :: Applicative f => (a -> b) -> f a -> f b
138(<$>) = liftA1
140liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
141liftA2 g fa fb = g <$> fa <*> fb
143liftA3 ::
144 Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
145liftA3 g fa fb fc = g <$> fa <*> fb <*> fc
146```
148 Note that in doing so we showed that every applicative functor (that is,
149 a type implementing `pure` and `(<*>)`) is a functor.
151* On the other hand, applicative functor is a functor which can __apply__
152 functions from inside of it via `(<*>)`, here's why it is called an
153 __Applicative__.
155If `liftA2` can be implemented using `pure` and `(<*>)`, why is it included in
156the class declaration? The reason for this is that `(<*>)` can be implemented
157using `liftA2`:
159```haskell ignore
160(<*>) :: Applicative f => f (a -> b) -> f a -> f b
161(<*>) = liftA2 (\g x -> g x)
162```
164Applicative laws:
1661. `pure id <*> v = v` (Identity);
1672. `pure f <*> pure x = pure (v x)` (Homomorphism);
1683. `u <*> pure y = pure (\f -> f y) <*> u` (Interchange);
1694. `u <*> (v <*> w) = ((pure (.) <*> u) <*> v) <*> w` (Composition);
1705. `liftA2 g u v = pure g <*> u <*> v` (relation with `liftA2`);
1716. `fmap = liftA1` (relation with Functor).
173Intuitively:
175* `pure` must not provide any additional information meaningful to `(<*>)` (so
176 here's the source of the name: it should encapsulate a __pure__ value and do
177 nothing more);
178* the merging of internal structure performed in `(<*>)` should be associative.
180__Exercise 6__: show that functor laws hold automatically for every lawful
181applicative.
183### Monad
185Now, the most notable typeclass of all is a Monad. What is this?
187```haskell ignore
188class Applicative m => Monad m where
189 return :: a -> m a
190 return = pure
192 (>>=) :: m a -> (a -> m b) -> m b
194 (>>) :: m a -> m b -> m b
195 mx >> my = mx >>= (\_ -> my)
196```
198As we mentioned before, this is an interface most useful to express effectful
199operations: `return x` is a pure result of otherwise effectful computation;
200`(>>=)` and `(>>)` both execute operations in order, where in `(>>=)` (also
201called "bind") a second computation can depend on the outcome of the first.
203Turns out that it is a proper subclass of Applicative, meaning that `(<*>)` can
204be written out in terms of `return` and `(>>=)`:
206```haskell
207ap :: Monad m => m (a -> b) -> m a -> m b
208ap mf mx = mf >>= \f -> mx >>= \x -> return (f x)
209```
211(This is already defined in standard library, in module `Control.Monad`. Don't
212be afraid to use Hoogle to find such combinators!)
214A little insight into the way these typeclasses could be discovered. Starting
215from `Functor f`, every class introduces new capabilities for lifting of
216functions into `f`:
218* `fmap` is `(a -> b)` to `(f a -> f b)`
219* `(<*>)` is `f (a -> b)` to `(f a -> f b)`
220* `flip (>>=)` is `(a -> f b)` to `(f a -> f b)`
222`(f a -> f b)` to `(f a -> f b)` is `id`; what about this?
224```haskell ignore
225whatIsThis :: (f a -> b) -> (f a -> f b)
226```
228Actually, this is a method from `Comonad` interface, which has its own
229interesting applications. However, they are out of scope for now.
231Monad laws:
2331. `return a >>= k = k a` (Left identity);
2342. `m >>= return = m` (Right identity);
2353. `(m >>= k) >>= h = m >>= (\x -> k x >>= h)` (Associativity).
237After squinting a little, this looks like monoid laws. With additional
238technical work, Monad actually looks like a proper "monoid in the category of
239endofunctors", whatever this category-theoretic talk means. However, you do not
240need this arcane knowledge to program in Haskell: just learn the laws and the
241interface itself.
243# Exercise solutions
245```haskell
246foldList :: Monoid a => [a] -> a
247foldList [] = mempty
248foldList (x : xs) = x <> foldList xs
250instance Num a => Semigroup (Sum a) where
251 Sum x <> Sum y = Sum (x + y)
253instance Num a => Monoid (Sum a) where
254 mempty = Sum 0
256instance Num a => Semigroup (Mul a) where
257 Mul x <> Mul y = Mul (x * y)
259instance Num a => Monoid (Mul a) where
260 mempty = Mul 1
262sumList :: Num a => [a] -> a
263sumList = getSum . foldList . map Sum
265productList :: Num a => [a] -> a
266productList = getMul . foldList . map Mul
268instance Foldable BinTree where
269 foldMap _ Leaf = mempty
270 foldMap f (Branch l x r) = foldMap f l <> f x <> foldMap f r
272instance Functor BinTree where
273 fmap _ Leaf = Leaf
274 fmap f (Branch l x r) = Branch (fmap f l) (f x) (fmap f r)
275```
277Solution for __Exercise 6__:
279```haskell ignore
280fmap id x = liftA1 id x = pure id <*> x = x
282fmap g (fmap f x) = liftA1 g (liftA1 f x)
283 = pure g <*> (pure f <*> x)
284 = ((pure (.) <*> pure g) <*> pure f) <*> x
285 = (pure ((.) g) <*> pure f) <*> x
286 = pure ((.) g f) <*> x
287 = pure (g . f) <*> x
288 = liftA1 (g . f) x
289 = fmap (g . f) x
290```
292# Sources
294[Typeclassopedia](https://wiki.haskell.org/Typeclassopedia) contains a thorough
295description of the most ubiquitous typeclasses together with explanation of
296their laws and with more exercises.