Full deck by Mark Seemann
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 [Diamonds,Hearts,Clubs,Spades]
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 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#.
Next: An applicative password list.
