Skip to content

The deck

Snap is played with an ordinary 52-card deck. Here is how the rules make one:

def deck : List Card :=
  (List.range 4).flatMap fun s => (List.range 13).map fun r => ⟨r + 1, s⟩

That is a lot of new things in two lines. Take them one at a time.

Lists of numbers

List.range n is the list of the first n numbers, starting from 0:

/-- info: [0, 1, 2, 3] -/
#guard_msgs in
#eval List.range 4

So List.range 4 is the four suits and List.range 13 the thirteen ranks, counted from zero.

Functions without names

fun r => r + 1 is a function with no name: it takes r and gives back r + 1. Functions are values in Lean, like numbers, so you can pass one to another function. map does that: it applies a function to every element of a list.

/-- info: [1, 2, 3, 4] -/
#guard_msgs in
#eval (List.range 4).map fun r => r + 1

/-- info: [1, 2, 3, 4] -/
#guard_msgs in
#eval (List.range 4).map (· + 1)

The second line is the same function written shorter: (· + 1) means "a function that adds one to its argument". (Type \. for the dot.)

Lists of lists

flatMap is map for a function that gives back a list for each element: it joins the results into one list instead of a list of lists.

/-- info: [[0, 1], [10, 11]] -/
#guard_msgs in
#eval [0, 10].map fun x => [x, x + 1]

/-- info: [0, 1, 10, 11] -/
#guard_msgs in
#eval [0, 10].flatMap fun x => [x, x + 1]

Now read deck again. For each suit s from 0 to 3, it makes the list of thirteen cards of that suit, with ranks 1 to 13 (r + 1, because ranges start at 0 and an ace is 1). flatMap joins the four suits into one deck:

/-- info: 52 -/
#guard_msgs in
#eval deck.length

/-- info: [{ rank := 1, suit := 0 }, { rank := 2, suit := 0 }, { rank := 3, suit := 0 }] -/
#guard_msgs in
#eval deck.take 3

/-- info: 4 -/
#guard_msgs in
#eval (deck.filter fun c => c.rank == 1).length

take 3 is the first three elements, and filter keeps the elements a test accepts: here, the four aces.

Dealing

To deal, the rules shuffle the deck and hand out the cards alternately. Here is deal, which makes the state of a new game:

def deal (seed maxFlips : Nat) : State :=
  let (shuffled, _) := (Engine.Rng.ofSeed seed).shuffle deck.toArray
  let cs := shuffled.toList.zipIdx
  { hand0 := { down := cs.filterMap fun (c, i) => if i % 2 == 0 then some c else none }
    hand1 := { down := cs.filterMap fun (c, i) => if i % 2 == 1 then some c else none }
    maxFlips }

let names a value for the lines that follow it.

  • The shuffle. (Engine.Rng.ofSeed seed).shuffle deck.toArray shuffles the deck with a random number generator started from seed. It gives back a pair: the shuffled cards, and the generator after use. let (shuffled, _) takes the pair apart, keeping the cards and ignoring the generator (that's what _ means).
  • Numbering the cards. zipIdx pairs every element with its position.
  • Dealing alternately. filterMap keeps the even positions for one player and the odd for the other:
/-- info: [("a", 0), ("b", 1), ("c", 2)] -/
#guard_msgs in
#eval ["a", "b", "c"].zipIdx

/-- info: ["a", "c"] -/
#guard_msgs in
#eval ["a", "b", "c"].zipIdx.filterMap fun (x, i) => if i % 2 == 0 then some x else none

some x and none say "here is a value" and "there is none". You'll see this type, Option, again in the next chapter.

Lean has no hidden randomness: a function given the same inputs always gives the same result. So the shuffle depends only on the seed, and the same seed always deals the same game. This is why a game can be replayed exactly, and why it can be reasoned about:

/-- info: (26, 26) -/
#guard_msgs in
#eval let s := State.deal 42 2000; (s.hand0.down.length, s.hand1.down.length)

/-- info: true -/
#guard_msgs in
#eval State.deal 42 2000 == State.deal 42 2000

/-- info: false -/
#guard_msgs in
#eval State.deal 42 2000 == State.deal 43 2000

The shuffle itself lives in the engine, which all three games share:

/-- Fisher–Yates, from the top: for `i` from `n - 1` down to `0`, swap
position `i` with a position chosen uniformly from `0..i`. -/
def shuffleAux {α} : Nat → Array α → Rng → Array α × Rng
  | 0, a, g => (a, g)
  | i + 1, a, g =>
    -- Written without a `let`: with one, Lean's equation-lemma generator for
    -- this definition does not terminate, which blocks every proof about it.
    shuffleAux i (a.swapIfInBounds i (g.below (i + 1)).1) (g.below (i + 1)).2

This is a function that calls itself, for each position from the last to the first. You don't need to follow it yet. Notice the comment, though: how a definition is written can matter for proving things about it later.

Exercises

  1. How many hearts (suit 1) are in the deck? Use filter and length.
  2. How many cards are picture cards (rank above 10)?
  3. Check that every rank appears exactly four times. List.all says whether a test holds for every element of a list.
Solution
/-- info: 13 -/
#guard_msgs in
#eval (deck.filter fun c => c.suit == 1).length

/-- info: 12 -/
#guard_msgs in
#eval (deck.filter fun c => c.rank > 10).length

def ranks : List Nat := (List.range 13).map (· + 1)

/-- info: true -/
#guard_msgs in
#eval ranks.all fun r => (deck.filter fun c => c.rank == r).length == 4