Skip to content

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 Action where
  | flip
  | snap
  deriving DecidableEq, Repr

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:

def other : Fin 2 → Fin 2
  | 0 => 1
  | 1 => 0

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

  1. Write Phase.isOver, which is true for a finished game. Use the style of other: a line per alternative, and _ for what you don't need.
  2. Write Event.player?, which gives the player an event is about, or none for 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.