Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Beginning F#: Card Tricks : Page 3

Discover the power of F# by writing a complete card-shuffling program in only 92 lines of code.


advertisement
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.



Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap