Nim

---
Examples from the paper "Liberating effects with rows and handlers"
by Daniel Hillerström and Sam Lindley, reworked for Nanyx contexts.
<https://www.dhil.net/research/papers/liberating_effects-tyde2016.pdf>

Nanyx contexts are implicit parameters rather than resumable effect
handlers, so the examples that rely on multi-shot `resume` (game trees,
exploring both choices) are written with direct recursion instead.
---

module nim

import nanyx/math

-- Players ------------------------------------------------------------------

type Player = #bob | #alice

def Player.show: Player -> string = {
  | #bob -> "bob"
  | #alice -> "alice"
}

def Player.other: Player -> Player = {
  | #bob -> #alice
  | #alice -> #bob
}

-- The game ----------------------------------------------------------------

-- A strategy decides how many sticks a player takes from a heap of `n`
context Move = (move: (Player, int) -> int)

-- Alice goes first; the player who takes the last stick wins
def turn: [Move] (Player, int) -> Player = { player, n ->
  if n <= 0 then player.other
  else turn(player.other, n - move(player, n))
}

def game: [Move] int -> Player = { n -> turn(#alice, n) }

-- Perfect strategy --------------------------------------------------------

def perfect = Move(move = { _, n -> Math.max(1, n % 4) })

def examplePerfect1 = { use perfect in game(7) }    -- alice
def examplePerfect2 = { use perfect in game(12) }   -- bob

-- Game trees --------------------------------------------------------------

type GameTree =
  | #take(Player, list((int, GameTree)))
  | #winner(Player)

def validMoves: int -> list(int) = { n -> [1, 2, 3] \filter { <= n } }

-- The tree of every possible game from a heap of `n`
def buildTree: (Player, int) -> GameTree = { player, n ->
  if n <= 0 then #winner(player.other)
  else
    def subtrees = validMoves(n) \map { sticks -> (sticks, buildTree(player.other, n - sticks)) }
    #take(player, subtrees)
}

def gameTree: int -> GameTree = { n -> buildTree(#alice, n) }

def showIndented: (GameTree, int) -> string = {
  | #winner(p), _ -> p.show ++ " wins"
  | #take(p, moves), indent ->
    def lines = moves \map { sticks, subtree ->
      "\n" ++ String.repeat(" ", indent) ++ "{sticks} -> " ++ showIndented(subtree, indent + 2)
    }
    p.show ++ (lines \String.join(""))
}

def GameTree.show: GameTree -> string = { tree -> showIndented(tree, 2) }

def exampleGameTree = { gameTree(3).show }   -- figure 1 in the paper

-- Cheating ----------------------------------------------------------------

type Outcome = #won(Player) | #cheated(Player)

-- Check a move before playing it, so an illegal move ends the game
def checkedMove: [Move] (Player, int) -> #some(int) | #error(#cheated(Player)) = { player, n ->
  def m = move(player, n)
  if validMoves(n) \contains(m) then #some(m) else #error(#cheated(player))
}

def checkedTurn: [Move] (Player, int) -> Outcome = { player, n ->
  if n <= 0 then #won(player.other)
  else
    match checkedMove(player, n)
      | #some(m) -> checkedTurn(player.other, n - m)
      | #error(#cheated(p)) -> #cheated(p)
}

def checkedGame: [Move] int -> Outcome = { n -> checkedTurn(#alice, n) }

-- Bob cheats by taking the whole heap
def cheating = Move(move = {
  | #alice, n -> Math.max(1, n % 4)
  | #bob, n -> n
})

def exampleCheck = { use perfect in checkedGame(7) }    -- #won(#alice)
def exampleCheat = { use cheating in checkedGame(12) }  -- #cheated(#bob)

-- Choosing a strategy -----------------------------------------------------

context Choose = (choose: () -> bool)

-- Bob cheats or plays perfectly depending on a choice made elsewhere
def bobChooses: [Choose] () -> Move = {
  Move(move = { player, n ->
    if player == #bob and choose() then n else Math.max(1, n % 4)
  })
}

-- Both outcomes, by running the game once per choice
def exampleChoose = {
  [true, false] \map { c ->
    use Choose(choose = { c }) in
    use bobChooses() in checkedGame(7)
  }
}   -- [#cheated(#bob), #won(#alice)]

def exampleCoin: [Random] () -> Outcome = {
  use Choose(choose = { Random.coinToss() }) in
  use bobChooses() in checkedGame(7)
}

-- Scoreboard --------------------------------------------------------------

type Scores = map(Player, int)

def initialScores: Scores = [#alice => 0, #bob => 0]

def updateScore: (Scores, Player) -> Scores = { scores, winner ->
  def #some(current) = scores(winner) except #notFound -> #some(0)
  scores \Map.insert(winner, current + 1)
}

def printBoard: [Console] Scores -> () = { scores ->
  for scores | player, score -> println("{player.show} -> {score}")
}

-- Play a number of rounds against a coin-flipping Bob and keep the score
def examplePrint: [Console & Random] int -> () = { rounds ->
  def final = (1..rounds) \fold(initialScores) { scores, _ ->
    def winner =
      match exampleCoin()
        | #won(p) -> p
        | #cheated(p) -> p.other
    updateScore(scores, winner)
  }
  printBoard(final)
}

@entry
def main: [Console & Random] () -> () = {
  println(examplePerfect1().show)
  println(examplePerfect2().show)
  println(exampleGameTree())
  println("{exampleCheck()}")
  println("{exampleCheat()}")
  println("{exampleChoose()}")
  examplePrint(10)
}

This program lives in the repository as examples/Nim.nyx.