Choices¶
A card has a rank and a suit: a structure is one thing and another. Much of a game is the other kind of thing, one thing or another. A player can flip or snap. A game is being played, or it's over. This chapter is about types like that, and how to take them apart.
Types with alternatives¶
Here are Snap's two moves:
inductive defines a type by listing every way to make a value of it. An
Action is either flip or snap, and nothing else. These alternatives are
called constructors. Their full names are Action.flip and Action.snap.
An alternative can carry data. Here is the phase of a game:
inductive Phase where
| playing
/-- `none` is a draw. -/
| finished (winner : Option (Fin 2))
deriving DecidableEq, Repr, Inhabited
A game is either playing, or finished, and a finished game carries its
winner. The winner's type is Option (Fin 2): either some p for a player
p, or none for a draw.
/-- info: Games.Snap.Action.flip -/
#guard_msgs in
#eval Action.flip
/-- info: Games.Snap.Phase.finished (some 0) -/
#guard_msgs in
#eval Phase.finished (some 0)
Two players¶
Fin 2 is the type of numbers below 2: just 0 and 1. Snap uses it for
players, so that there is no player 2 to forget about. Here is how the rules
find the other player:
This definition has no := and no argument names. Each line starting with
| handles one possible argument: give other a 0 and it gives back 1,
and the other way round. Lean checks that the lines cover every value of
Fin 2. If you deleted one, the definition would be refused.
def first : Fin 2 := 0
def second : Fin 2 := 1
/-- info: 1 -/
#guard_msgs in
#eval other first
/-- info: 0 -/
#guard_msgs in
#eval other (other first)
Pattern matching¶
Taking a value apart by its alternatives is called pattern matching, and
match does it inside a function body:
def describe (p : Phase) : String :=
match p with
| .playing => "still playing"
| .finished none => "a draw"
| .finished (some w) => s!"player {w} won"
/-- info: "a draw" -/
#guard_msgs in
#eval describe (.finished none)
/-- info: "player 1 won" -/
#guard_msgs in
#eval describe (.finished (some 1))
Each pattern can look inside the value: .finished none matches only a draw,
and .finished (some w) matches a win and names the winner w. The leading
dot is short for the type's name: Lean knows p is a Phase, so .playing
means Phase.playing. s!"…" builds a string with values put in where the
braces are.
Do the top cards match?¶
Now the question at the heart of Snap. The pile lists start with their top card, so a match means both lists have a first element and the two ranks are the same:
def isMatch (s : State) : Bool :=
match s.hand0.up, s.hand1.up with
| c :: _, d :: _ => c.rank == d.rank
| _, _ => false
This matches two things at once, the two face-up piles. c :: _ is a list
whose first element is c, followed by anything (_ ignores the rest). So
the first line covers "both piles have a top card", and _, _ covers
everything else, including an empty pile. There's no special code for empty
piles: they simply don't fit the first pattern.
def twoKings : State :=
{ hand0 := { up := [⟨13, 0⟩] }, hand1 := { up := [⟨13, 2⟩, ⟨4, 1⟩] }, maxFlips := 100 }
/-- info: true -/
#guard_msgs in
#eval twoKings.isMatch
def oneEmpty : State :=
{ hand0 := {}, hand1 := { up := [⟨13, 2⟩] }, maxFlips := 100 }
/-- info: false -/
#guard_msgs in
#eval oneEmpty.isMatch
isMatch takes a State, which is a whole game. The next chapter is about
that.
What happened¶
Every accepted move produces events: what happened, for players to read.
inductive Event where
| flipped (p : Fin 2) (card : Card)
| recycled (p : Fin 2)
| snapped (p : Fin 2) (won : Nat)
| falseSnap (p : Fin 2) (lost : Nat)
| finished (winner : Option (Fin 2))
deriving DecidableEq, Repr
Exercises¶
- Write
Phase.isOver, which istruefor a finished game. Use the style ofother: a line per alternative, and_for what you don't need. - Write
Event.player?, which gives the player an event is about, ornonefor the end of the game. (A name ending in?is Lean's convention for a function that might have no answer.)
As before, put them inside namespace Games.Snap, so dot calls find them.
Solution
namespace Games.Snap
def Phase.isOver : Phase → Bool
| .playing => false
| .finished _ => true
def Event.player? : Event → Option (Fin 2)
| .flipped p _ => some p
| .recycled p => some p
| .snapped p _ => some p
| .falseSnap p _ => some p
| .finished _ => none
/-- info: true -/
#guard_msgs in
#eval (Phase.finished none).isOver
/-- info: some 1 -/
#guard_msgs in
#eval (Event.snapped 1 6).player?
end Games.Snap
Try deleting one line of Event.player?: Lean tells you which
alternative is missing.