The deck¶
Snap is played with an ordinary 52-card deck. Here is how the rules make one:
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:
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.toArrayshuffles the deck with a random number generator started fromseed. 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.
zipIdxpairs every element with its position. - Dealing alternately.
filterMapkeeps 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¶
- How many hearts (suit
1) are in the deck? Usefilterandlength. - How many cards are picture cards (rank above 10)?
- Check that every rank appears exactly four times.
List.allsays 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