An introduction to applicative functors in Haskell, with a translation to F#.

This article is an instalment in an article series about applicative functors. While (non-applicative) functors can be translated to an object-oriented language like C# in a straightforward manner, applicative functors are more entrenched in functional languages like Haskell. This article introduces the concept with a motivating example in Haskell, and also shows a translation to F#. In the next article, you'll also see how to implement an applicative functor in C#.

### Deck of cards in Haskell #

Imagine that you want to model a card game. In order to do so, you start by defining data types for suits, faces, and cards:

```data Suit =
Diamonds | Hearts | Clubs | Spades deriving (Show, Eq, Enum, Bounded)

data Face =
Two  | Three | Four | Five | Six | Seven | Eight | Nine | Ten
| Jack | Queen | King | Ace
deriving (Show, Eq, Enum, Bounded)

data Card = Card { face :: Face, suit :: Suit } deriving (Show, Eq)```

Since both `Suit` and `Face` are instances of the `Enum` and `Bounded` typeclasses, you can easily enumerate them:

```allFaces :: [Face]
allFaces = [minBound .. maxBound]

allSuits :: [Suit]
allSuits = [minBound .. maxBound]```

For example, `allSuits` enumerates all four `Suit` values:

```λ> allSuits

Notice, by the way, how the code for `allFaces` and `allSuits` is identical. The behaviour, however, is different, because the types are different.

While you can enumerate suits and faces, how do you create a full deck of cards?

A full deck of cards should contain one card of every possible combination of suit and face. Here's one way to do it, taking advantage of lists being applicative functors:

```fullDeck :: [Card]
fullDeck = pure Card <*> allFaces <*> allSuits```

This will give you all the possible cards. Here are the first six:

```λ> forM_ (take 6 fullDeck) print
Card {face = Two, suit = Diamonds}
Card {face = Two, suit = Hearts}
Card {face = Two, suit = Clubs}
Card {face = Two, suit = Spades}
Card {face = Three, suit = Diamonds}
Card {face = Three, suit = Hearts}```

How does it work? Let's break it down, starting from left:

```λ> :type Card
Card :: Face -> Suit -> Card
λ> :type pure Card
pure Card :: Applicative f => f (Face -> Suit -> Card)
λ> :type pure Card <*> allFaces
pure Card <*> allFaces :: [Suit -> Card]
λ> :type pure Card <*> allFaces <*> allSuits
pure Card <*> allFaces <*> allSuits :: [Card]```

From the top, `Card` is a function that takes a `Face` value and a `Suit` value and returns a `Card` value. Object-oriented programmers can think of it as a constructor.

Next, `pure Card` is the `Card` function, elevated to an applicative functor. At this point, the compiler hasn't decided which particular applicative functor it is; it could be any applicative functor. Specifically, it turns out to be the list type (`[]`), which means that `pure Card` has the type `[Face -> Suit -> Card]`. That is: it's a list of functions, but a list of only a single function. At this point, however, this is still premature. The type doesn't materialise until we apply the second expression.

The type of `allFaces` is clearly `[Face]`. Since the `<*>` operator has the type `Applicative f => f (a -> b) -> f a -> f b`, the expression on the left must be the same functor as the expression on the right. The list type (`[]`) is an applicative functor, and because `allFaces` is a list, then `pure Card` must also be a list, in the expression `pure Card <*> allFaces`. In other words, in the definition of `<*>`, you can substitute `f` with `[]`, and `a` with `Face`. The interim result is `[Face -> b] -> [Face] -> [b]`. What is `b`, then?

You already know that `pure Card` has the type `[Face -> Suit -> Card]`, so `b` must be `Suit -> Card`. That's the reason that `pure Card <*> allFaces` has the type `[Suit -> Card]`. It's a list of functions. This means that you can use `<*>` a second time, this time with `allSuits`, which has the type `[Suit]`.

Using the same line of reasoning as before, you can substitute `Suit` for `a` in the type of `<*>`, and you get `[Suit -> b] -> [Suit] -> [b]`. What is `b` now? From the previous step, you know that the the expression on the left has the type `[Suit -> Card]`, so `b` must be `Card`. That's why the entire expression has the type `[Card]`.

### Deck of cards in F# #

You can translate the above Haskell code to F#. The first step is to make F# lists applicative. F# also supports custom operators, so you can add a function called `<*>`:

```// ('a -> 'b) list -> 'a list -> 'b list
let (<*>) fs l = fs |> List.collect (fun f -> l |> List.map f)```

This implementation iterates over all the functions in `fs`; for each function, it maps the list `l` with that function. Had you done that with a normal `List.map`, this would have returned a list of lists, but by using `List.collect`, you flatten the list.

It's worth noting that this isn't the only way you could have implemented `<*>`, but this is the implementation that behaves like the Haskell function. An alternative implementation could have been this:

```// ('a -> 'b) list -> 'a list -> 'b list
let (<*>) fs = List.collect (fun x -> fs |> List.map (fun f -> f x))```

This variation has the same type as the first example, and still returns all combinations, but the order is different. In the following of this article, as well as in subsequent articles, I'll use the first version.

Here's the playing cards example translated to F#:

```type Suit = Diamonds | Hearts | Clubs | Spades

type Face =
|  Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten
| Jack | Queen | King | Ace

type Card = { Face: Face; Suit : Suit }

// Face list
let allFaces = [
Two; Three; Four; Five; Six; Seven; Eight; Nine; Ten;
Jack; Queen; King; Ace]

// Suit list
let allSuits = [Diamonds; Hearts; Clubs; Spades]

// Card list
let fullDeck = [fun f s -> { Face = f; Suit = s }] <*> allFaces <*> allSuits```

The F# code is slightly more verbose than the Haskell code, because you have to repeat all the cases for `Suit` and `Face`. You can't enumerate them automatically, like you can in Haskell.

It didn't make much sense to me to attempt to define a `pure` function, so instead I simply inserted a single lambda expression in a list, using the normal square-bracket syntax. F# doesn't have constructors for record types, so you have to pass a lambda expression, whereas in Haskell, you could simply use the `Card` function.

The result is the same, though:

```> fullDeck |> List.take 6 |> List.iter (printfn "%A");;
{Face = Two; Suit = Diamonds;}
{Face = Two; Suit = Hearts;}
{Face = Two; Suit = Clubs;}
{Face = Two; Suit = Spades;}
{Face = Three; Suit = Diamonds;}
{Face = Three; Suit = Hearts;}```

While the mechanics of applicative functors translate well to F#, it leaves you with at least one problem. If you add the above operator `<*>`, you've now 'used up' that operator for lists. While you can define an operator of the same name for e.g. `option`, you'd have to put them in separate modules or namespaces in order to prevent them from colliding. This also means that you can't easily use them together.

For that reason, I wouldn't consider this the most idiomatic way to create a full deck of cards in F#. Normally, I'd do this instead:

```// Card list
let fullDeck = [
for suit in allSuits do
for face in allFaces do
yield { Face = face; Suit = suit } ]```

This alternative syntax takes advantage of F#'s 'extended list comprehension' syntax. FWIW, you could have done something similar in Haskell:

```fullDeck :: [Card]
fullDeck = [Card f s | f <- allFaces, s <- allSuits]```

List comprehension, however, is (as the name implies) specific to lists, whereas an applicative functor is a more general concept.

### Summary #

This article introduced you to lists as an applicative functor, using the motivating example of having to populate a full deck of cards with all possible combinations of suits and faces.

The next article in the series shows another list example. The F# and Haskell code will be similar to the code in the present article, but the next article will also include a translation to C#.

### Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

#### Published

Monday, 08 October 2018 06:17:00 UTC

#### Tags

"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 08 October 2018 06:17:00 UTC