Applicatives and Alternatives

Introduction

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.

Option Types; Optional Contexts

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:

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 - Success or Failing With Informational Errors

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 - Keeping Track of All The Errors

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:

Conclusion

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:

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.

Concluding For Real

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.

Updates/Edits