OutlineUDT ExampleCS421 Lecture 5a: Variant Records, ExtendedExample1Mark [email protected] of Illinois at Urbana-ChampaignJune 8, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleUDT ExampleMark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleObjectivesSince variant records are an important topic, this lecturesupplement provides an exte nded example of their use. At the endof this suppleme nt, you should:◮better understand the creation and use of v ariants◮know how to write functions which work over variantsMark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleThe Extended Example: PokerCard games make good examples, since they provide multiplevariant types we can use (enumerations, disjoint unions) and haveinteresting rules we can encode. We will use poker as our example– the O’Rei ll y book uses French Tarot.Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleThe Basics◮A deck has 52 cards◮Cards are in four suits : hearts, diamonds, clubs, and spades◮Cards are numbered from 2 to 10 and also include the ace,king, queen, and jackMark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleRepresenting SuitsSuits can be represented as an Enumeration, since all the suits arejust constant values.1 # type suit = Hearts | Diamonds | Clubs | Spades;;2 type suit = Hearts | Diamonds | Clubs | SpadesMark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleRepresenting CardsCards do have associated data – suit and, for numbe red cards, thenumber. So, this will be a disjoint union.1 # type card = Ace of suit2 | King of suit3 | Queen of suit4 | Jack of suit5 | Num of suit * int;;6 type card =7 Ace of suit8 | King of suit9 | Queen of suit10 | Jack of suit11 | Num of suit * intMark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExamplePrinting SuitsSuits can be printed usi ng a function and basic pattern matching.1 #let name_of_suit s =2 match s with3 | Diamonds -> "Diamonds"4 | Hearts -> "Hearts"5 | Clubs -> "Clubs"6 | Spades -> "Spades";;7 val name_of_suit : suit -> string = <fun>Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExamplePrinting CardsPrinting a des cription of the cards is a bit more involved, since itinvolves matching const ructors and data values held with theconstructors.1 #let name_of_card c =2 match c with3 | Ace s -> "Ace of " ^ name_of_suit s4 | King s -> "King of " ^ name_of_suit s5 | Queen s -> "Queen of " ^ name_of_suit s6 | Jack s -> "Jack of " ^ name_of_suit s7 | Num (s,n) -> string_of_int n ^ " of " ^ name_of_suit s;;8 val name_of_card : card -> string = <fun>Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleCreating a DeckWe need to generate the deck of 52 cards to get started. We cando that usi ng several helper functions.1 let generate_deck =2 let rec generate_list n m =3 if n = m then [m] else n :: (generate_list (n + 1) m)4 and generate_num_for_suit s =5 List.map (fun n -> Num (s, n)) (generate_list 2 10)6 and generate_suit s =7 Ace s :: King s :: Queen s :: Jack s ::8 generate_num_for_suit s9 in10 fun () -> List.fold_right (fun s y -> generate_suit s @ y)11 [Hearts;Diamonds;Clubs;Spades] [];;12 val generate_deck : unit -> card list = <fun>Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleThe Created Deck1 # generate_deck();;2 - : card list =3 [Ace Hearts; King Hearts; Queen Hearts; Jack Hearts; Num (Hearts, 2);4 Num (Hearts, 3); Num (Hearts, 4); Num (Hearts, 5); Num (Hearts, 6);5 Num (Hearts, 7); Num (Hearts, 8); Num (Hearts, 9); Num (Hearts, 10);6 Ace Diamonds; King Diamonds; Queen Diamonds; Jack Diamonds;7 Num (Diamonds, 2); Num (Diamonds, 3); Num (Diamonds, 4); Num (Diamonds, 5);8 Num (Diamonds, 6); Num (Diamonds, 7); Num (Diamonds, 8); Num (Diamonds, 9);9 Num (Diamonds, 10); Ace Clubs; King Clubs; Queen Clubs; Jack Clubs;10 Num (Clubs, 2); Num (Clubs, 3); Num (Clubs, 4); Num (Clubs, 5);11 Num (Clubs, 6); Num (Clubs, 7); Num (Clubs, 8); Num (Clubs, 9);12 Num (Clubs, 10); Ace Spades; King Spades; Queen Spades; Jack Spades;13 Num (Spades, 2); Num (Spades, 3); Num (Spades, 4); Num (Spades, 5);14 Num (Spades, 6); Num (Spades, 7); Num (Spades, 8); Num (Spades, 9);15 Num (Spades, 10)]Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleShuffling the DeckTo shuffle the deck, we somehow need to create a new deck fromthe old deck . Our strategy will be to randomly pick one card fromthe old deck and put it into the new deck until we are out of cards.First, we need a way to remove an element from a list.Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleRemoving an Element from a ListTo remove a single element from a list, we can write a functionallbut nth, which will give us back all but the nth element.1 # let rec all_but_nth n l =2 match l with3 | [] -> []4 | x::xs ->5 match n with6 | 0 -> xs7 | _ -> x :: all_but_nth (n-1) xs;;8 val all_but_nth : int -> ’a list -> ’a list = <fun>Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleShuffling the DeckNow, we can randomly grab cards out of the old deck until weempty it. Note the use of Random, a provided module for randomnumber generation.1 # let shuffle_deck d =2 let () = Random.self_init()3 in let rec pick_until_done d =4 match d with5 | [] -> []6 | _ ->7 let n = Random.int (List.length d) in8 (List.nth d n) :: (pick_until_done (all_but_nth n d))9 in pick_until_done d;;10 val shuffle_deck : ’a list -> ’a list = <fun>Mark Hills CS421 Lecture 5a: Variant Records, Extended ExampleOutlineUDT ExampleA Sample Shuffle1 # let deck = shuffle_deck (generate_deck());;2 val deck : card list =3 [Num (Clubs, 5); Jack Diamonds; Num (Spades, 5); Num (Clubs, 2);4 Num (Hearts, 4); Ace Clubs; Num (Clubs, 6); Num (Spades, 9); King Clubs;5 Queen Diamonds; Num (Spades, 3); Num (Hearts, 9); Ace Diamonds;6 Num (Clubs, 10); Num (Hearts, 6); Num (Hearts, 2); Num (Hearts, 8);7 Num (Clubs, 9); Queen Spades; Num (Spades, 2); Num (Hearts, 5);8 Queen Hearts; Num (Diamonds, 3); Ace Hearts; Num (Diamonds, 5);9 Num (Diamonds, 6); Num (Diamonds, 8); Num (Clubs, 4); Num (Diamonds, 10);10 King Diamonds; Num (Spades, 10); Num (Diamonds, 4); Num (Spades, 4);11 Jack Spades; Ace Spades;
View Full Document
Unlocking...