## And a bit of Traversable

updated 2021-05-25

## What are they?

### `Applicative`

• An `Applicative` is short for a strong lax monoidal functor or some people might call it an Applicative Functor.

• In Haskell - it is a Functor that comes with an operation `<*> :: f (a -> b) -> f a -> f b` that tells it how to Apply a higher level `Functor` to another `Functor`.

• If you remember from the `Functor` article, we already defined what a `Functor` is and what `fmap` (aka. `<\$>`) does - let’s compare them side by side:

``````<?> ::   (a -> b) -> f a -> f b
<*> :: f (a -> b) -> f a -> f b
``````
• In essence the difference is that with `<\$>` the function is flat - i.e. outside the realms of the `Functor` and it is injected inside.

• In `<*>` ( a.k.a. “splat” - as I have just found out during an interview earlier this week) the first argument is a lifted function - i.e. the `Functor` contains a higher order type.

• for Haskell to believe you a type is an instance of an `Applicative` it is sufficient to prove it has the functions:
• `pure` of type `Applicative f => a -> f a`, and
• either:
• `<*>` of type `Applicative f => f (a -> b) -> f a -> f b`, or
• `liftA2` of type `Applicative f => (a -> b -> c) -> f a -> f b -> f c`.
• Other laws that it must satisfy:
• Identity `pure id <*> v = v`
• Composition `pure (.) <*> u <*> v <*> w = u <*> (v <*> w)`
• Homomorphism `pure f <*> pure x = pure (f x)`
• Interchange `u <*> pure y = pure (\$ y) <*> u`
• For the whole list with further conversation it would be good to consult hackage.

## Scenario

Lets say we want to have a type `Doer` that stores both a type and its meta sign- which is a property we came up with.

The meta sign has the following behaviour: when we do operations with these type, the signs interact and the resulting sign follow the normal sign rule i.e. :

• `+ & +` = `+`,
• `+ & -` = `-`,
• `- & +` = `-`,
• `- & -` = `+`.

I would also like to introduce the use of `GADTs` in this case, as it makes working with the type nicer. Note that this could have been done without it, but I thought it would be clearer what we are doing by using them.

## Implementation

• As mentioned before lets enable `GADTs`, and also let’s import the `Applicative` module
``````{-# LANGUAGE GADTs #-}
import Control.Applicative
``````

• And continue by defining our types. Let us define the type `Op` which is our meta sign. We also implement a `Show` so we can display it nicely.
``````data Op = Add | Sub deriving (Eq)

instance Show Op where
show o = if o == Add then "+" else "-"
``````

• Now we can define our sign rule function that combines the two `Op`s.
``````signRule :: Op -> Op -> Op
signRule x y
= case x of
Sub -> Sub
Sub -> case y of
``````
• But if we look, we can see a pattern - `Op` is a `monoid` where `Add` is the neutral element. So let’s make use of this and also enrich our type with another of its inherent - discovered properties.
• Note: algebraic properties are discovered and not designed - they are inherent to the type itself. You can design your types to make use of types that have the properties or not - but you cannot design the property into a type - if it doesn’t have it.
``````instance Semigroup Op where
(<>) = signRule

instance Monoid Op where
``````

• Next let’s define our type `Doer`. In this implementation, our type constructor `ON` takes a meta sign `Op` and any type `a` and it creates an instance of `Doer a` - think of it like an embellished type that contains our meta-sign.
``````data Doer a where
ON :: Op -> a -> Doer a
deriving (Show, Eq)
``````

• And let’s look at a few examples that would make it clear
``````ex0 =  ON Sub 3            -- ON - 3
ex1 =  ON Add "Hello"      -- ON + "Hello"
ex2 = [ON Sub 3, ON Add 2] -- [ON - 3,ON + 2]
``````

We can see that `Doer a` is a `Functor`. Let’s prove it.

``````instance Functor Doer where
fmap f (ON o x) = ON o \$ f x
``````

Now, let’s prove it is an `Applicative`.

``````instance Applicative Doer where
pure                      = ON (mempty::Op)
(<*>) (ON o f) (ON o' n') = ON (o <> o') (f \$ n')
``````

Note: we made use in `(o <> o')` of our previously discovered `Monoid` property. The reader (yes, you) can check that the rest of the laws of the `Applicative Functor` stand.

#### Examples

• OK I’m glad to say that we’ve covered most of the info regarding `Applicative`, some examples to see it in action would be good.

#### Example 1:

Let’s use our splat to apply the lifted function `(+1)` to a functor:

``````ex01 = ON Sub (+1) <*> ON Sub 1 -- ON + 2
--   = ON - (+1) <*> ON - 1     -- this is what happens
--   = ON ( - <> - ) (1 \$ (+1))
--   = ON + 2
``````

So it works as intended, we have the result of the operation and the result of the interaction between their meta signs.

#### Example 2:

We want to compose two functions and apply them to a `Functor`

``````ex02 = pure ((+1). (+2)) <*> ON Sub 3 -- ON - 6
``````

Is there another way to write this? Of course, and it might give some insight into what actually happens:

``````ex03 = pure (.) <*> pure (+1) <*> pure (+2) <*> ON Sub 3 -- ON - 6
``````

Explanation: we lift the composition, we partially apply it to the lifted `(+1)` we then apply it to the lifted `(+2)` giving us the lifted composition of `(+1)` and `(+2)`. Then in the end we apply this to lifted `3` and we get lifted `6`. As the functions are pure our meta sign is not altered.

#### Example 3:

We want to do the previous while changing our meta sign accordingly.

``````ex04 = pure (.) <*> ON Sub (+1) <*> ON Add (+2) <*> ON Sub 3 -- ON + 6
``````

Isn’t that fantastic:

• we already know that `6` is the result of the function application
• `- + - ` = `+` - which gets through to us in the type.

#### Example 4:

Say we have a list of `Doer`s and a higher typed `Doer` and we want to `fmap` it.

``````ex2  = [ON Sub 3, ON Add 2]
ex05 = (pure (+1) <*>) <\$> ex2    -- [ON - 4,ON + 3]
``````

This is interesting - we can observe here what is going on - if we refactor again with something that we’ve seen before:

``````ex05' = (fmap (+1)) <\$>  ex2    -- [ON - 4,ON + 3]
ex05''= fmap (fmap (+1)) ex2    -- [ON - 4,ON + 3]
``````

This behaviour is linked to the definition of `pure`. But the added benefit of being able to interact through `<*>` is that it easily allows us to change the meta-sign.

``````ex06 = ((ON Sub (+1)) <*> ) <\$> ex2  -- [ON + 4,ON - 3]
``````

Observe how in `ex06` the meta signs have flipped.

## Traversable Time

### What is it ?

• It is a `typeclass` that can be traversed from left to right - but its uses are a bit more subtle than that - and we’ll talk a bit more about it when time comes.

• I’m not going to go very in depth with regards to `Traversable`, because the post would fork too much (I will make a dedicated post at some point) - but it’s important to note that `Traversable`, `Applicatives`, `Monads` are very tightly connected. (The wiki article is a good read)

• Note: in the examples the `Traversable, Foldable t` is the `[]` type.

### Examples

• Example: say we take a list of `Doer`s and we want to nest it into a `Doer` type itself, with the correct meta-sign (the sign of folding all the meta signs inside the list with the `<>` we defined) while in essence unwrapping the elements. The type of this function would look something like:
``````squishSign :: [Doer a] -> Doer [a]
``````

So here are the challenges we are facing:

• if we `foldMap :: Monoid m => (a -> m) -> t a -> m` we need to do quite a bit of work to to get our `Doer` to match that type - not ideal - and we are lazy.
• Wouldn’t it be nice if we had some sort of function that would traverse our list, do something with the type and then at the end gives us that something? Don’t worry Haskell has our back:
``````sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
``````
• observe how that `t` and `f` swap positions - that is what we want to do. We know `Doer` is `Applicative`, and we know that `[]` is `Traversable` so what are we waiting for:
``````squishSign :: [Doer a] -> Doer [a]
squishSign  = sequenceA
``````

I wrote it as a section as it reads a bit better - but let’s see it in action:

``````ex11 = squishSign [ON Sub 3, ON Add 2]           -- ON - [3,2]
ex12 = squishSign [ON Sub 3, ON Add 2, ON Sub 3] -- ON + [3,2,3]
``````

Now we can apply some more functy (funky + functor) things we’ve seen earlier.

``````ex13 = pure sum <*> squishSign [ON Sub 3, ON Add 2, ON Sub 3] -- ON + 
``````

This has been a well long post, and we’ve had a lot of functy time together. What other cool `Applicative` and `Traversable` design patterns do you use or have discovered? Let me know!