Session 2.md

Today we did two derivations to flex our type muscles.

From type to expression

What is the definition of foo given its type:

foo :: Functor f => a -> f (x, b) -> f (x, a)

Well, we know that it takes two arguments, a value which we know nothing about, and another which has two qualities: (1) it is a functor (2) full of tuples. From its return type, we notice that foo installs the value passed as the first argument as the right-most part of the tuples --- b does not appear anywhere, which means all values of type b are eliminated.

foo a fb = _

There's not much latitude here. What can you do with a? You can use the identity function id :: a -> a, but that does not get us anywhere. You can use the constant function const :: a -> b -> a. This one is a bit more interesting: it "forgets" its second argument... something that looks suspiciously close to what we need. But first we need to access the values inside that functor, so the only thing we can do is map over it:

foo a fb = fmap _ fb

By refering to the definition of fmap, the function we pass as the first argument must have type (x, b) -> (x, a). It's trivial to come up with a definition of that function, but there's another piece of information we know about tuples: they're functors too! Right-biased, to be precise, so mapping over a tuple will act on the right component, which is exactly what we want (what a coincidence!).

foo a fb = fmap (fmap _) fb

Now that we're mapping two layers deep, we need a function b -> a. We have seen that before, that's const, but partially applied! We arrive at

foo a fb = fmap (fmap (const a)) fb

We can get rid of these distracting brackets with the infix operator for fmap, <$>.

foo a fb = fmap (const a) <$> fb

Note that there is an infix operator for replacing all locations with a single value (here, a), you may like it:

foo a fb = (a <$) <$> fb

## From expression to type

Can you guess the type of
```hs
bar = (<*>) . (<$>) (,)

Yes you can, but guess has no role to play in that.

This is a point-free definition, and it's not very user-friendly. No sane Haskell programmer would ever write that, I just made it as ugly as possible for the sake of the example. Our plan of attack will be to derive a clearer definition of bar by applying substitutions. First, we'll need a few definitions:

(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(<$>) :: Functor f => (a -> b) -> f a -> f b
(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f (g x)
(,) :: a -> b -> (a, b)

Now we derive, using the definitions above and the algebraic rules of lambda calculus:

bar = (<*>) . (<$>) (,)
{- infix operator goes prefix -}
bar = (.) (<*>) ((<$>) (,))
{- eta-expansion -}
bar x = (.) (<*>) ((<$>) (,)) x
{- definition of (.) -}
bar x = (<*>) ((<$>) (,) x)
{- eta-expansion -}
bar x y = (<*>) ((<$>) (,) x) y
{- prefix goes infix, twice -}
bar x y = ((,) <$> x) <*> y
{- precedence of <$> over <*> -}
bar x y = (,) <$> x <*> y

We arrive at a pointful version of bar which now looks much easier to grok. That is an expression written in applicative style, where a computation is accumulated by successive applications of <*>. We can infer the type now. Given (,) :: a -> b -> (a, b), the expression (,) <$> x can only have type Functor f => f (b -> (a, b)). So, x :: f a. Given the type of <*> we need to strengthen the constraint to Applicative f and derive that y :: f b.

We arrive at

bar :: Applicative f => f a -> f b -> f (a, b)

aka the cartesian product of two functors as a functor of ordered pairs. It's fun to try that with a couple of functors:

bar [1,2,3] [4,5,6] = [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
bar (Just "hello") (Just "world") = Just ("hello","world")
bar (const 5) (const "five") = const (5, "five)

yeah... fun 😅