Beginning F#: Card Tricks

hen attempting to learn a new computer language, it’s difficult to find a problem that’s both interesting enough to bother working with and also simple enough to let you concentrate on language rather than logic. Fortunately, it turns out you can learn a lot about F# with a deck of playing cards. This article shows how to create a simple F# application that shuffles a deck and displays the cards in the console window. Along the way you’ll explore:

  • Discriminated unions
  • Tuples
  • Lists and list sequence expressions
  • Functions and recursion
  • Pattern matching and functional polymorphism
What You Need
The minimum requirement for following along with the code is this article is Microsoft F# Interactive, delivered as part of the Microsoft F# download package available on MSDN. F# Interactive runs in a console window and compiles and runs F# commands interactively. However, the recommended setup is Visual Studio 2008 (or later) with Microsoft F# installed. If you don’t have the full version of Visual Studio 2008, you can install the free Visual Studio 2008 Shell (Integrated Mode). After installing the Visual Studio Shell, install Microsoft F#.

Getting Started
Visual Studio gives you the option to create F# applications and class libraries, and has an integrated window running F# Interactive. F# will eventually be available as a standalone Visual Studio Express Edition product.

If you’re using Visual Studio, create a new F# Application project named DevX.Cards.PartI. Click View ? Other Windows ? F# Interactive to display the integrated F# Interactive window.

If you aren’t using Visual Studio then click Start ? All Programs ? Microsoft F# version ? F# Interactive (console) to launch F# Interactive. Be sure to append two semicolons (;;) to the end of every expression you enter in F# Interactive. Just a warning: Some of the code snippets in this article include the semicolons; others do not.

Discriminated Unions and Enumerations
There are three types of playing cards in a standard 54-card deck: rank cards, face cards, and jokers. Rank cards and face cards have a suit: diamonds, clubs, hearts, or spades. Rank cards have a rank from two to ten, and face cards have a face: jack, queen, king, or ace. Jokers are…well, jokers.

The F# discriminated union construct is a great way to model the attributes of a playing card. For example, a suit is either diamonds, clubs, hearts, or spades, while F# discriminated unions are a type a that can be one of x, y, or z:

   type Rank =   | Two   | Three   | Four   | Five   | Six   | Seven   | Eight   | Nine   | Ten      type Face =   | Jack   | Queen   | King   | Ace      type Suit =   | Diamonds   | Clubs   | Hearts   | Spades

You can use F# Interactive to explore how to create and compare discriminated unions.

Author’s Note: F# Interactive is a command-line application in which you enter the code shown at the caret (>) prompt, and F# responds on the following line or lines?those that don’t start with a caret. F# Interactive responds with output in the form:

   val expression-name : expression-type-and-result
If your expression doesn’t have a name, then F# Interactive gives it the generic name it.

   val it : expression-type-and-result

Type these examples into F# interactive:

   > let suit1 = Diamonds;;   val suit1 : Suit      > let suit2 = Spades;;   val suit2 : Suit      > suit1 > suit2;;   val it : bool = false      > suit1 = suit2;;   val it : bool = false      > suit1 < suit2;;   val it : bool = true

The combination of a Rank and a Suit creates a rank card, and the combination of a Face and a Suit creates a face card. F# provides a first-class construct for modeling combinations of values: tuples.

Tuples
F# models paired (or tripled, quadrupled, etc.) values using tuples, which encapsulate two or more values combined into one structure. Here's an example using F# Interactive that explores how to create tuples:

   > let tupleOfTwo = ("Charlie", "Brown");;   val tupleOfTwo : string * string      > let tupleOfThree = ("Abraham", "Lincoln", 16);;   val tupleOfThree : string * string * int      > let tupleOfTuples = (tupleOfTwo, tupleOfThree);;   val tupleOfTuples : (string * string) * (string * string * int)

Note that F# responds with the type of each value defined in the tuple. Tuples with two values are called "two-tuples;" those with three values are "3-tuples," etc. You access the first and second elements of a two-tuple with the fst and snd functions. You can access any element in an n-tuple with a let binding as shown below (these use the tuples created in the preceding example):

   > fst tupleOfTwo;;   val it : string = "Charlie"      > snd tupleOfTwo;;   val it : string = "Brown"      > let x, y, z = tupleOfThree;;   val z : int   val y : string   val x : string      > x;;   val it : string = "Abraham"      > y;;   val it : string = "Lincoln"      > z;;   val it : int = 16      > let _, secondTuple = tupleOfTuples;;   val secondTuple : string * string * int      > secondTuple;;   val it : string * string * int = ("Abraham", "Lincoln", 16)

Note how the asterisk (*) separates the members of a tuple type, and the underscore ((_) is a wildcard character that means "any" or "ignore". The underscore is a way to acknowledge that one portion of a data structure exists without giving it a name?usually because you're more interested in some other portion of the data structure.

To get back to the main topic, you can model a playing card elegantly using a discriminated union whose members are represented as tuples:

   type Card =   | RankCard of Rank * Suit   | FaceCard of Face * Suit   | Joker

Think of this expression as, "A Card may be a RankCard represented as a two-tuple of Rank and Suit, or a Card may be a FaceCard represented as a two-tuple of Face and Suit?or a Card may be a Joker."

Here's an F# Interactive listing that explores how to create Cards:

   > let juliusCaesar = FaceCard (King, Diamonds);;   val juliusCaesar : Card      > juliusCaesar;;   val it : Card = FaceCard (King,Diamonds)      > let lowChicago = RankCard (Two, Spades);;   val lowChicago : Card      > lowChicago;;   val it : Card = RankCard (Two,Spades)      > let courtJester = Joker;;   val courtJester : Card      > courtJester;;   val it : Card = Joker

All three cards maintain both their identity as a Card and their identity as one of the Card's discriminated union members; this characteristic is one of the key enablers of functional polymorphism in F#, which you'll see more about later.

Playing cards are rarely useful by themselves; most card games are based on collections of cards.

Lists and List Sequence Expressions
There are four prominent collection types in F#.

  • Lists are native, immutable linked lists delimited by brackets [ a; b; c ].
  • Arrays are native, mutable arrays delimited by brackets and pipes [| a; b; c |].
  • Sequences are native descriptions of what a collection will contain when it's eventually enumerated. Sequences are delimited by the seq keyword and braces ({}).
  • .NET Collections are the types in the System.Collections and System.Collections.Generic namespaces.

You can use lists for the playing card application; they're easy to use, and illustrate some of the powerful features in F#. To build a deck of playing cards, begin by creating a list of the ranks, faces, and suits:

   let ranks =        [ Two; Three; Four; Five; Six; Seven;          Eight; Nine; Ten ]      let faces =        [ Jack; Queen; King; Ace ]      let suits =        [ Diamonds; Clubs; Hearts; Spades ]

Instead of constructing lists with an implicit set of semicolon delimited elements, you can apply a list sequence expression that instructs F# how to generate the list. The following F# Interactive listing explores list sequence expressions, for example:

   > let squares = [ for i in 1..10 -> i * i ];;   val squares : int list      > squares;;   val it : int list =       [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]      > let squaresAndCubes = [ for i in 1..10 ->       [ i * i; i * i * i ] ];;   val squaresAndCubes : int list list      > squaresAndCubes;;   val it : int list list = [[1; 1]; [4; 8];       [9; 27]; [16; 64]; [25; 125];       [36; 216]; [49; 343];       [64; 512]; [81; 729]; [100; 1000]]   

The list sequence expression for squaresAndCubes generates a list of lists; lists may contain anything, including primitives, other lists, collections and functions.

F# Interactive also lets you explore the two native operators F# provides to manipulate lists:

   > let firstHalf = [ "one"; "two" ];;   val firstHalf : string list      > let secondHalf = [ "three"; "four"];;   val secondHalf : string list      > let bothHalves = firstHalf @ secondHalf;;   val bothHalves : string list      > bothHalves;;   val it : string list = ["one"; "two"; "three"; "four"]      > let fullList = "zero" :: bothHalves;;   val fullList : string list      > fullList;;   val it : string list = ["zero"; "one"; "two"; "three"; "four"]

The ampersand (@) operator concatenates two lists to create another list, and the double colon (::) operator prepends or appends an element to a list to create another list. Neither operator modifies the original list(s), because F# lists are immutable

F# also provides the List module with a number of useful list manipulation functions. Here are some F# Interactive examples that explore the List.concat and List.iter functions:

   > let nestedLists = [ [ 1; 2 ]; [ 3; 4 ]; [ 5; 6] ];;   val nestedLists : int list list      > nestedLists;;   val it : int list list = [[1; 2]; [3; 4]; [5; 6]]      > let flattenedList = List.concat nestedLists;;   val flattenedList : int list      > flattenedList;;   val it : int list = [1; 2; 3; 4; 5; 6]      > let reportElement element =       printfn "Found element %A" element;;   val reportElement : 'a -> unit      > List.iter reportElement flattenedList;;   Found element 1   Found element 2   Found element 3   Found element 4   Found element 5   Found element 6   val it : unit = ()      > flattenedList |> List.iter reportElement;;   Found element 1   Found element 2   Found element 3   Found element 4   Found element 5   Found element 6   val it : unit = ()

List.concat concatenates and flattens the elements of one or more lists. List.iter applies a function to every element in a list. The preceding code uses a let binding to define the function reportElement, and then passes that as the first argument to the List.iter function.

At the end of the listing, you can see that instead of passing flattenedList to List.iter as the second argument, you can use the pipe operator (|>) to pipe it into the intermediate function created by the expression List.iter reportElement. The pipe operator isn't necessary, but it makes many F# expressions more readable.

Lists, list sequence expressions, list operators and list functions provide everything you need to generate rank cards, face cards and a complete deck:

   let ranks =        [ Two; Three; Four; Five; Six; Seven; Eight; Nine; Ten ]      let faces =        [ Jack; Queen; King; Ace ]      let suits =        [ Diamonds; Clubs; Hearts; Spades ]      let rankCards =       List.concat [ for s in suits -> [ for r in ranks -> RankCard (r, s) ] ]      let faceCards =       List.concat [ for s in suits -> [ for f in faces -> FaceCard (f, s) ] ]      let jokers =        [ Joker; Joker ]      let fiftyTwoCards =       rankCards @ faceCards      let fiftyFourCards =       fiftyTwoCards @ jokers

Now you're ready to use a functional approach to shuffling and drawing cards from these immutable decks.

Functions and Recursion
Consider this simple algorithm for shuffling a deck of cards:

  1. Compute the upper bound for random number generation. Let upper bound = (number of cards in the deck) x 100.
  2. Assign an integer value, or weight, to each card in the deck. Let weight = a random number between 0 and upper bound.
  3. Sort the cards according to their weight values.

This algorithm is particularly useful in a functional approach to shuffling, because it is easy to implement without a mutable data structure.

Author's Note: Effective and sufficiently random card shuffling is a fascinating topic that is particularly important in the online gaming industry. Use your favorite internet search engine to learn more about it, and read some of the heated forum discussions. Also see The Art of Computer Programming by Donald Knuth.

Here's how to declare a function that accepts a list of cards:

   let shuffle cards =      …

The first step in the shuffling algorithm is to compute the upper bound for random number generation:

   let shuffle cards =      let upperBound = (List.length cards) * 100

List.length is a function in the List module that returns the number of elements in a list. Multiplying it by 100 significantly reduces the chance that two cards in the deck will have the same weight value (1/5400 x 1/5400, to be exact).

The second step in the shuffling algorithm is to assign a random weight value to every card in the list. That is, you want to perform a mapping from card c to tuple(c, w), where w is the card's weight value. Mapping elements in a source list to a new target list is a common operation in functional programming, and the List module provides a List.map function to do that:

   let randomNumberGenerator =      new System.Random()      let shuffle cards =      let upperBound = (List.length cards) * 100      let weightedCards =          List.map            (fun card -> card,               randomNumberGenerator.Next(0, upperBound))            cards

List.map takes two arguments. Its signature is:

   ('a -> 'b) -> 'a list -> 'b list

The first argument is a function that accepts an element (of any type 'a) from the source list and evaluates to an element (of any type 'b) for the target list. The second argument is the source list ('a list). The result is target list.

The fun keyword declares an anonymous function, which is similar to anonymous methods and delegates in Java and C#. Using anonymous functions isn't always required, but it allows you to use expressions declared in the scope of the outer function. In this case, the anonymous function uses the upperBound expression even though the function declaration doesn't accept it as an argument.

The anonymous function accepts a card as an input and returns a tuple of the card and a random weight value. The signature of the function is:

   (Card -> (Card, int))

This particular usage of List.map will have this signature at runtime:

   (Card -> (Card, int)) ->       Card list -> (Card, int) list

The third step in the shuffling algorithm is to sort the list of cards according to their weight value. In this case, you need to sort the list of tuples. Like List.map, sorting elements in a source list to create a new target list is a common operation in functional programming, so the List module provides a List.sort function for you:

   let shuffle cards =      let upperBound = (List.length cards) * 100      let weightedCards =          List.map             (fun card -> card, randomNumberGenerator.Next(0, upperBound))             cards      let sortedWeightedCards =          List.sort             (fun (_, leftWeight) (_, rightWeight) -> leftWeight-rightWeight)             weightedCards

List.sort takes two arguments. Its signature is:

   ('a -> 'a -> int) -> 'a list -> 'a list

The first argument is a function that accepts two elements (of any type 'a) from the source list and evaluates to an integer that represents the result of the comparison?greater than zero, zero, or less than zero. The second argument is the source list ('a list). The result is the sorted target list (the 'a list).

The anonymous comparison function accepts two tuples from the source list of weighted cards. Note the use of the underscore to represent the card in each tuple. The comparison function doesn't need the cards to perform the comparison, so you ignore them with the underscore. You could declare the anonymous function as:

            (fun (leftCard, leftWeight) (rightCard, rightWeight) ->               leftWeight-rightWeight) 

But as you can see, leftCard and rightCard are never used. This is a powerful example of pattern matching in F#?discussed further in the next section.

The final step in the shuffling function is to return not a sorted list of tuples, but a sorted list of cards. That is, you need to map the sorted list of tuples back to a list of cards:

   let shuffle cards =      let upperBound = (List.length cards) * 100      let weightedCards =          List.map             (fun card -> card, randomNumberGenerator.Next(0, upperBound))             cards      let sortedWeightedCards =          List.sort             (fun (_, leftWeight) (_, rightWeight) -> leftWeight-rightWeight)             weightedCards      List.map          (fun (card, _) -> card)          sortedWeightedCards

The final map operation becomes the result of the function: the sorted list of cards.

Now that you have a shuffled deck of cards, you're ready to write a function to draw cards from the deck. Because the card list is already shuffled, you can draw a card from it by removing the first card in the list and returning it as a tuple with the remaining cards in the deck:

   let drawOneCard deck =      (List.hd deck, List.tl deck)

List.hd returns the first element in a list (the head), and List.tl returns the list minus its first element (the tail):

   > let source = [1; 2; 3; 4];;   val source : int list      > (List.hd source, List.tl source);;   val it : int * int list = (1, [2; 3; 4])

This simple function won't do for most card games, however; you need to be able to draw an arbitrary number of cards from a shuffled deck. The functional approach to such a task is to break it down into its simplest form, drawing one card at a time, and executing that task n times. This is called recursion, a central technique in functional programming.

Author's Note: The alternative to recursion is iteration, accomplished in traditional imperative languages like Java and C# using while and for constructs. F# supports both recursion and iteration, but this article focuses on the functional approach.

Here is the code to draw n cards from a shuffled deck using recursion:

   let draw count cards =       if count > (List.length cards) then           failwith "Deck doesn't have that many cards"       let rec loop n (drawnCards, remainingCards) =           if n = 0 then               (drawnCards, remainingCards)           else               let newDrawnCards = (List.hd remainingCards) :: drawnCards               let newRemainingCards = List.tl remainingCards               loop (n-1) (newDrawnCards, newRemainingCards)       loop count ([], cards) 

The first expression in this function checks to see if there are enough cards in the deck. If not, it throws an exception using the failwith function, a simple way to throw exceptions in F#.

The second expression in this function is a local, recursive function declaration that's accessible only to the outer draw function. The rec keyword lets the compiler know that this is a recursive function so that it can make certain under-the-hood optimizations?namely, it attempts to recycle stack memory to prevent stack overflow.

Author's Note: Most recursive function calls run the risk of running out of stack memory. For example, Windows allocates 1MB of memory to the stack, so processing a list of 10,000 elements using recursion could produce a StackOverflowException. However, F# can reuse stack memory from call to call if the function is tail-recursive; that is, the call to the recursive function is always the last call in the function. Note that the loop function in this section is tail-recursive because the inner call to itself is the last expression it evaluates.

The final expression in this function is the first call to the recursive loop function, passing in the arguments passed to the outer draw function: the number of cards to draw (count) and the shuffled deck (cards) to use as a starting point.

To demonstrate how the recursive function works, suppose you were to call:

   let shuffledDeck = shuffle fiftyTwoCards   draw 4 deck

This would call the loop function five times:

  1. loop 4 ([], [c1; c2; c3; c4; c5; ? cN])
  2. loop 3 ([c1], [c2; c3; c4; c5; ? cN])
  3. loop 2 ([c1; c2], [c3; c4; c5; ? cN])
  4. loop 1 ([c1; c2; c3], [c4; c5; ? cN])
  5. loop 0 ([c1; c2; c3; c4], [c5; ? cN)

The last call to loop simply returns the four drawn cards and the remainder of the shuffled cards?exactly what you would expect to return from the draw function.

Pattern Matching and Functional Polymorphism
One of F#'s notable features is its ability to make inferences about expressions. Here's an F# Interactive exploration showing how F# makes inferences about types:

   > let list1 = [ 1; 2; 3];;   val list1 : int list      > let list2 = [ [ "apple"; "orange" ]; [ "pear"; "mango" ] ];;   val list2 : string list list      > let add x y =       x + y   ;;      val add : int -> int -> int      > add 2 3;;   val it : int = 5      > add "two" "three";;        add "two" "three";;     ----^^^^^^      stdin(8,5): error FS0001: This expression has type      string   but is here used with type      int.

F# Interactive's response to the first line of code above is to examine the list1 expression and determine that it is of type int list: a list of integers. F# similarly infers that the list2 expression is of type string list list: a list of lists of strings.

In the third entry, F# examines the add function, and by looking at the use of the x and y arguments, infers that it is of type int -> int -> int: a function that accepts two integers and evaluates to an integer.

You can use F#'s inference capabilities to look for specific patterns in types and expressions and then take action accordingly. This process is called pattern matching, and you've already see it in action throughout this article. First, you used it to extract the elements of a 3-tuple:

   > let tupleOfThree = ("Abraham", "Lincoln", 16);;   val tupleOfThree : string * string * int      > let x, y, z = tupleOfThree;;   val z : int   val y : string   val x : string      > x;;   val it : string = "Abraham"      > y;;   val it : string = "Lincoln"      > z;;   val it : int = 16

You also used it to extract only the relevant elements of 2-tuple in a comparison function:

      let sortedWeightedCards =          List.sort             (fun (_, leftWeight) (_, rightWeight) -> leftWeight-rightWeight)             weightedCards

The match keyword is another way to take advantage of pattern matching:

   > let findTwosInTuple tuple =       match tuple with       | (2, _) -> "2 is the first member of the tuple!"       | (_, 2) -> "2 is the second member of the tuple!"       | _ -> "There isn't a 2 in this tuple";;      val findTwosInTuple : int * int -> string      > findTwosInTuple (2, 0);;   val it : string = "2 is the first member of the tuple!"      > findTwosInTuple (3, 0);;   val it : string = "There isn't a 2 in this tuple"      > findTwosInTuple(99, 2);;   val it : string = "2 is the second member of the tuple!"

Pattern matching is useful in far more ways than this article can list, but the most prominent use for the construct in F# is functional polymorphism: allowing a function to change its behavior based on the type (or pattern) of the expression it's acting on. The playing card application provides a perfect example.

After the playing card application draws cards from the deck, you need to display the results in the console window. Here's a function called printCard that accepts a playing card, but that behaves differently based on the card type (face card, rank card, or joker). The match construct makes this trivial:

       let printCard card =           match card with           | RankCard(rank, suit) -> printfn "%A of %A" rank suit           | FaceCard(Ace, suit) -> printfn "Bam! An Ace of %A" suit           | FaceCard(face, suit) -> printfn "Nice! %A of %A" face suit           | Joker -> printfn "Joker is wild!"  

The printCard function is polymorphic with regard to rank cards, aces, face cards and jokers. The polymorphic behavior in this case is a trivial printfn expression, but you could easily replace that with function expressions that encapsulate complex behaviors.

The application's main function is now complete:

   let main =       let shuffledCards = shuffle fiftyFourCards       let (drawnCards, remainingDeck) = draw 10 shuffledCards       let printCard card =           match card with           | RankCard(rank, suit) -> printfn "%A of %A" rank suit           | FaceCard(Ace, suit) -> printfn "Bam! An Ace of %A" suit           | FaceCard(face, suit) -> printfn "Nice! %A of %A" face suit           | Joker -> printfn "Joker is wild!"         List.iter printCard drawnCards

Here's the console output from one execution:

   Bam! An Ace of Clubs   Nice! Queen of Spades   Joker is wild!   Six of Spades   Bam! An Ace of Spades   Eight of Diamonds   Nine of Clubs   Five of Clubs   Nice! King of Diamonds   Three of Clubs

As you can see by the terseness of the code you've written, F# is an elegant, logical language. You've explored the functional programming approach and some of F#'s native features, such as:

  • Discriminated unions
  • Tuples
  • Lists and list sequence expressions
  • Functions and recursion
  • Pattern matching and functional polymorphism

You've created a simple yet powerful playing card application using only 92 lines of code. Stay tuned for a follow-up article that explores some of F#'s more advanced features to implement the core of any playing card game: the rules.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

Recent Articles: