- May 9, 2017: changes

This post is a tutorial on applicative functors (applicatives) and alternatives - what they are, how they’re used, and how to build an intuition for them.

It’s going to be extremely practical. It’s going to be all Haskell. We’ll build stuff along the way so that it makes more sense.

The following imports are assumed to be in scope for this post:

```
import Control.Applicative
import Data.Monoid
```

All code used in this post is available here.

Let’s start with some informal definitions.

An applicative is an abstraction that lets us express function composition in a context. Applicative composition only succeeds if each independent component in the computation succeeds. Rules for what success looks like vary from context to context. Its interface looks like this.

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

Notably, all applicative functors must also be functors. We won’t cover functors here, but it suffices to say that they’re an abstraction for applying context-free functions to context-embedded values.

`pure`

is sometimes called `lift`

because it lifts a pure value of type `a`

into the context `f`

. `<*>`

is our applicative composition operator. It allows us to chain together contextual computations.

An alternative is an abstraction that builds on applicatives. Like it sounds, it allows to express the idea of trying something else in case something fails. Composition of alternatives take the first success. Its interface looks like this:

```
class Applicative f => Alternative (f :: * -> *) where
empty :: f a
(<|>) :: f a -> f a -> f a
```

`empty`

is our failure value, to represent a failure of all alternatives. `<|>`

is our composition operator, for chaining together alternatives.

With those definitions out of the way -

Let’s build our first applicative! To do so, we’ll look at the `Option`

type.

An `Option`

or `Maybe`

type allows us to express the idea of nullability safely. It looks like this:

```
data Option a
= Some a
| None
deriving Show
```

We either have `Some`

value of type `a`

or we have `None`

.

Here’s the applicative (and functor) implementation for `Option`

:

```
instance Functor Option where
fmap f (Some a) = Some (f a)
fmap _ None = None
instance Applicative Option where
pure = Some
Some f <*> Some a = Some (f a)
None <*> Some _ = None
Some _ <*> None = None
None <*> None = None
```

The only way a computation for `Option`

can succeed is if we have `Some`

value along all paths. The moment we encounter a `None`

, we abort.

Let’s look at the implementation of `Alternative`

for `Option`

now:

```
instance Alternative Option where
empty = None
Some a <|> Some _ = Some a
Some a <|> None = Some a
None <|> Some a = Some a
None <|> None = None
```

In this case, we succeed as long as some computational path results in `Some`

. We fail only if all paths fail.

I’ll provide some examples next. A few notes:

`<$>`

is`fmap`

, or, the means to apply a pure function in a context`:{`

is used in the Haskell REPL to indicate multi-line input`:}`

terminates multi-line input

Here’s how what we’ve written looks like in use:

```
> (+) <$> Some 1 <*> Some 2
Some 3
> (+) `fmap` Some 1 <*> Some 2
Some 3
> (+) <$> Some 1 <*> None
None
> add3 a b c = a + b + c
> :t add3
add3 :: Num a => a -> a -> a -> a
> add3 <$> Some 1 <*> Some 2 <*> Some 3
Some 6
> add3 <$> Some 1 <*> None <*> Some 3
None
> None <|> Some 1
Some 1
> None <|> None
None
> None <|> None <|> Some 3
Some 3
> :{
| (+) <$> None <*> Some 1
| <|> (*) <$> Some 5 <*> Some 10
| :}
Some 50
> :(
| (*) <$> Some 8 <*> Some 5
| <|> None
| :}
Some 40
```

The examples above all use integers, but we could easily use any other type. Furthermore, notice that we can chain as many computations as we need, like with `add3`

. This is much more convenient than pattern matching on the spot every time, like:

```
add3OptLengthy :: Num a => Option a -> Option a -> Option a -> Option a
add3OptLengthy a b c =
case a of
None -> None
(Some a') -> case b of
None -> None
(Some b') -> case c of
None -> None
(Some c') -> Some (add3 a' b' c')
```

It is also less error-prone that using if-expressions, like so:

```
isNone :: Option a -> Bool
isNone None = True
isNone _ = False
-- dangerous
getOption :: Option a -> a
getOption (Some a) = a
getOption None = error "oh no crash"
add3OptUnsafe :: Num a => Option a -> Option a -> Option a -> Option a
add3OptUnsafe a b c =
if isNone a
then None
else if isNone b
then None
else if isNone c
then None
else Some (add3 (getOption a) (getOption b) (getOption c))
```

Alternatives and applicatives (and functors!) capture this logic for us so we don’t have to repeat ourselves. All of the above to say:

```
> f3 a b c = add3 <$> a <*> b <*> c
> :t f3
Num a => Option a -> Option a -> Option a -> Option a
```

Let’s look at a new context type now: `Xor`

`Xor`

(or it’s Haskell analogue, `Either`

) is a type used to store simple error information in the case of a failure. It looks like this:

```
data Xor a b
= XLeft a
| XRight b
deriving Show
```

The `XLeft`

branch is typically used to capture an error. The `XRight`

branch is our success path.

Here’s the implementation of `Applicative`

for `Xor`

:

```
instance Functor (Xor a) where
fmap f (XRight a) = XRight (f a)
fmap _ (XLeft a) = XLeft a
instance Applicative (Xor a) where
pure = XRight
XRight f <*> XRight a = XRight (f a)
XRight _ <*> XLeft a = XLeft a
XLeft a <*> XRight _ = XLeft a
XLeft a <*> XLeft _ = XLeft a -- choose the first error to short-circuit
```

As before, the only way to get to a success is to have successes all along the way.

`Xor`

does not admit an `Alternative`

instance. This is because, there is no reasonable definition of `Alternative`

’s `empty`

. If the left-branch type `a`

was a `Monoid`

, then it’d be possible to define, but it still wouldn’t be very interesting. We’ll elide that for now and show a more reasonable error-capturing type in the next section that allows for alternatives.

For the examples involving `Xor`

, we’ll first define a simple error data type with a few helper functions:

```
data NumberError
= NumberTooBig
| NumberTooSmall
| NumberNotAllowed
deriving Show
validateNumber :: Int -> Xor NumberError Int
validateNumber x
| x > 500 = XLeft NumberTooBig
| x < 30 = XLeft NumberTooSmall
| x `elem` [42, 69, 420] = XLeft NumberNotAllowed
| otherwise = XRight x
```

Now for some examples:

```
> validateNumber 32
XRight 32
> validateNumber 69
XLeft NumberNotAllowed
> validateNumber 501
XLeft NumberTooBig
> validateNumber 29
XLeft NumberTooSmall
> (+) <$> validateNumber 31 <*> validateNumber 33
XRight 64
> (+) <$> validateNumber 31 <*> validateNumber 42
XLeft NumberNotAllowed
```

Next, let’s look at an extension to the `Xor`

type - the `Validation`

type.

`Validation`

is a very handy type for any form of validation where you’d like to keep track of all errors that occur, instead of throwing them away. It looks fairly similar to `Xor`

, even:

```
data Validation a b
= Failure a
| Success b
deriving Show
```

Exchange `Validation`

with `Xor`

, `Failure`

with `XLeft`

, and `Success`

with `XRight`

and we’re right back to the last section! However, we’ll see that how we implement `Applicative`

and `Alternative`

can make a big difference.

Here’s the `Applicative`

implementation:

```
instance Functor (Validation a) where
fmap f (Success a) = Success (f a)
fmap _ (Failure a) = Failure a
-- accumulating errors
instance Monoid a => Applicative (Validation a) where
pure = Success
Success f <*> Success a = Success (f a)
Failure a <*> Success _ = Failure a
Success _ <*> Failure a = Failure a
Failure a <*> Failure b = Failure (a <> b)
```

The biggest change so far is that we require the error type to implement the `Monoid`

interface, which, expresses things that can be concatenated/merged/etc via the `<>`

operator. Instead of keeping only the first error encounterd, we keep them all. We’ll see how this works more closely with some examples soon.

Here’s the implementation for `Alternative`

:

```
instance Monoid a => Alternative (Validation a) where
empty = Failure mempty
Success a <|> Success _ = Success a
Success a <|> Failure _ = Success a
Failure _ <|> Success a = Success a
Failure _ <|> Failure a = Failure a
```

Nothing changed here compared to `Xor`

.

Before getting to examples, let’s define some convenient functions around our `NumberError`

data type from before:

```
numberTooSmall :: Validation [NumberError] a
numberTooSmall = Failure [NumberTooSmall]
numberTooBig :: Validation [NumberError] a
numberTooBig = Failure [NumberTooBig]
numberNotAllowed :: Validation [NumberError] a
numberNotAllowed = Failure [NumberNotAllowed]
validateNumberV :: Int -> Validation [NumberError] Int
validateNumberV x
| x > 500 = numberTooBig
| x < 30 = numberTooSmall
| x `elem` [42, 69, 420] = numberNotAllowed
| otherwise = Success x
```

And some examples:

```
> validateNumberV 32
Success 32
> validateNumberV 69
Failure [NumberNotAllowed]
> add3V a b c = a + b + c
> add3V <$> validateNumberV 32 <*> validateNumberV 33 <*> validateNumberV 34
Success 99
> add3V <$> validateNumberV 42 <*> validateNumberV 69 <*> validateNumberV 420
Failure [NumberNotAllowed, NumberNotAllowed, NumberNotAllowed]
> add3V <$> validateNumberV 42 <*> validateNumberV 10 <*> validateNumberV 50
Failure [NumberNotAllowed, NumberTooSmall]
> :{
(+) <$> validateNumberV 42 <*> validateNumberV 10
<|> (+) <$> validateNumberV 41 <*> validateNumberV 31
:}
Success 72
```

These examples are mostly silly, mainly for showing the mechanics, but the `Validation`

type is incredibly useful for giving thorough feedback to users when validating complex input. It often comes up in the context of web form validation (if working in a language like Purescript) where you want to check that all fields have sensible values, and if not, reporting what fields aren’t valid and why.

I’ll list two implementations below:

- Haskell validation
- Purescript validation

As this post has already gotten kind of long, I’ll leave several other amazing bits out of it for this time. The most useful bits I’m not bringing up, are that applicatives and alternatives can be used for:

- parsing
- text and bytestring formats: attoparsec
- complex text parsing, say, for programming languages: megaparsec
- JSON: aeson
- database fields: postgresql-simple
- command line options: optparse-applicative
- HTTP query params: wai-request-spec
- Though the servant package does this even more nicely with fancier techniques

- sequencing parallel code: parallel
- sequencing concurrent code: async
- even more

As a small example of applicatives and alternatives for parsing, here’s a bit of code from one of my projects that uses the attoparsec library noted above:

```
-- #SELECTABLE:YES
parseSelectable :: Parser Selectable
parseSelectable =
Selectable <$> (startTag *> parseSelect)
where startTag :: Parser Char
startTag = pound *> stringCI (tagBytes TNSelectable) *> char ':'
parseSelect :: Parser Bool
parseSelect =
(stringCI "YES" $> True) <|> (stringCI "NO" $> False)
```

The goal is to parse a string that looks like `"#SELECTABLE:YES"`

or `"#SELECTABLE:NO"`

, and having done so, wrap it in a type that differentiates it from a plain boolean type.

`*>`

is an applicative operator that performs parse sequencing, but discards the left-hand side. `$>`

is a functor operator that performs the effect to the left, and if successful, lifts the right-hand side into the current context.

`startTag`

matches the `"#SELECTABLE:`

portion, and `parseSelect`

looks for either a `"yes"`

or a `"no"`

in a case-insensitive fashion.

Probably the most interesting bit here is that I had the ability to specify alternative, valid parses using `<|>`

in `parseSelect`

. This comes in handy for parsing any sort of enumerated type, say, the error return code from a web API you’re consuming.

Anyway, that’s all! I hope this helped clarify what applicatives and alternatives are, and how you might use them. Even though this post is Haskell-centric, the core ideas can be expressed in other programming languages. Ultimately, applicatives and alternatives are just a safe, broad interface for composing computations with context and assigning rules to those contexts.