A Scala implementation of Hangman based on Scalaz's Arrow type class

ArrowHangman.scala

import scala.language.higherKinds
import scala.util.Random
import scalaz.Scalaz._
import scalaz._
import Circuit.arrowInstance


/////////////////////////////////////////////////////////////////////////////////////////
// This implementation closely follows the Haskell implementation in the Haskell Wikibook
// (https://en.wikibooks.org/wiki/Haskell/Arrow_tutorial).
//
// It is not necessarily the most natural implementation of Hangman, but it nicely
// demonstrates how Arrows are composed and used.
/////////////////////////////////////////////////////////////////////////////////////////


/**
  * A `Circuit[A, B]` is basically a fancy function. Given an `A`, it not only returns a `B`,
  * but also returns a new `Circuit[A, B]`. Thus `Circuit` can represent stateful transformations.
  *
  * `Circuit` has instances of `Arrow` and `Choice` typeclasses.
  */
case class Circuit[A, B](run: A => (Circuit[A, B], B))

object Circuit {

  implicit val arrowInstance: Arrow[Circuit] = new Arrow[Circuit] {
    override def arr[A, B](f: (A) => B): Circuit[A, B] = Circuit(arr(f) -> f(_))

    override def first[A, B, C](fa: Circuit[A, B]): Circuit[(A, C), (B, C)] = Circuit {case (a, c) =>
      val (cir, b) = fa.run(a)
      (first(cir), (b, c))
    }

    override def id[A]: Circuit[A, A] = Circuit(id -> _)

    override def compose[A, B, C](f: Circuit[B, C], g: Circuit[A, B]): Circuit[A, C] = Circuit {a =>
      val (gg, b) = g.run(a)
      val (ff, c) = f.run(b)
      (compose(ff, gg), c)
    }
  }

  implicit val choiceInstance: Choice[Circuit] = new Choice[Circuit] {

    override def id[A]: Circuit[A, A] = Arrow[Circuit].id

    override def compose[A, B, C](f: Circuit[B, C], g: Circuit[A, B]): Circuit[A, C] = Arrow[Circuit].compose(f, g)

    override def choice[A, B, C](f: => Circuit[A, C], g: => Circuit[B, C]): Circuit[\/[A, B], C] = Circuit {
      case -\/(a) => f.run(a).leftMap(choice(_, g))
      case \/-(b) => g.run(b).leftMap(choice(f, _))
    }
  }
}

object ArrowHangman {

  val dict = Vector("dog", "cat", "bird")
  val ran = new Random
  val maxAttempts: Int = 5

  /**
    * Feed values in `F[A]` one by one into the circuit, resulting in `F[B]`.
    */
  def runCircuit[A, B, F[_] : Traverse](cir: Circuit[A, B], fa: F[A]): F[B] = fa.mapAccumL(cir)(_ run _)._2

  /**
    * A circuit that accumulates the `A` values fed to it, using the
    * accumulation function `f` and the starting value `acc`.
    */
  def accum[ACC, A, B](acc: ACC)(f: (A, ACC) => (B, ACC)): Circuit[A, B] = Circuit {a =>
    val (b, acc2) = f(a, acc)
    (accum(acc2)(f), b)
  }

  /**
    * A simplified version of `accum` where the type of the accumulated value is `B`.
    */
  def accum2[A, B](b: B)(f: (A, B) => B): Circuit[A, B] = accum(b) {(a, b) =>
    val bb = f(a, b)
    (bb, bb)
  }

  /**
    * A circuit that returns \/- the first time and -\/ each time afterwards.
    *
    * This is used to control whether a new word is picked in a Hangman game. A new word should only be picked the
    * first time (i.e., when the game starts).
    */
  val oneshot: Circuit[Unit, \/[Unit, Unit]] = accum(().right[Unit]) {(_, acc) => (acc, ().left)}

  /**
    * A circuit which takes a value, stores it, and returns the previously stored value. The first time it is called,
    * `init` is returned.
    */
  def delayedEcho[A](init: A): Circuit[A, A] = accum(init) {(a, b) => (b, a)}

  val pickWord: Circuit[Unit, Option[String]] = Arrow[Circuit].arr(_ => dict(ran.nextInt(dict.length)).some)

  val notPickWord: Circuit[Unit, Option[String]] = Arrow[Circuit].arr(_ => None)

  /**
    * A circuit that returns a randomly picked word in the dictionary the first time it is called. Each time
    * afterwards it always returns that same word.
    */
  val getWord: Circuit[Unit, String] =
    oneshot >>> (notPickWord ||| pickWord) >>> total[Option[String]] >>> Arrow[Circuit].arr(_.orZero)

  def livesLeft(hung: Int): String = {
    s"Lives: [${"#" * (maxAttempts - hung)}${" " * hung}]"
  }

  /**
    * An input is valid iff it is a string of length 1.
    */
  val getInput: Circuit[String, Option[Char]] = Arrow[Circuit].arr {in =>
    (in.length === 1).fold(in.headOption, None)
  }

  def total[A: Monoid]: Circuit[A, A] = accum2(Monoid[A].zero)(_ |+| _)

  /**
    * Update guess when an input is received. For example, if the word is "dog", then initially guess is "_ _ _".
    * After the player enters "g", the guess becomes "_ _ g".
    */
  val updateGuess: Circuit[(String, Option[Char]), (String, String)] =
    accum2[(String, Option[Char]), (String, String)](null, null) {
      case ((word, input), (_, guess)) => input match {
        case Some(c) => word -> (Option(guess) | ("_" * word.length)).zip(word)
          .map {case (g, w) => (w === c).fold(w, g)}.mkString
        case _ => word -> (Option(guess) | ("_" * word.length))
      }
    }

  /**
    * Update hung (the number of incorrect guesses) when an input is received.
    */
  val updateHung: Circuit[(String, Option[Char]), Int] = ((word: String, input: Option[Char]) => input match {
    case Some(c) if !word.contains(c) => 1
    case _ => 0
  }).tupled.arrow[Circuit] >>> total


  val result: Circuit[(String, String, Int), List[String]] = Arrow[Circuit].arr {
    case (word, guessed, hung) =>
      if (word === guessed) List(guessed, "You won!")
      else List(guessed, livesLeft(hung)) ++ ((hung >= maxAttempts) ? List("You died!") | Nil)
  }

  val end: Circuit[(String, String, Int), Boolean] =
    ((word: String, guessed: String, hung: Int) => (word === guessed) !|| (hung >= maxAttempts))
      .tupled.arrow[Circuit] >>> delayedEcho(true)

  val hangman: Circuit[String, (Boolean, List[String])] = {
    val flatten = Arrow[Circuit].arr[((String, String), Int), (String, String, Int)] {
      case ((a, b), c) => (a, b, c)
    }

    // Scala does not have the proc notation as Haskell does, so we have to resort to this less readable syntax.
    (((_: String) => ()).arrow[Circuit] &&& Arrow[Circuit].id) >>>
      (getWord *** getInput) >>> (updateGuess &&& updateHung) >>> flatten >>> (end &&& result)
  }

  def main(args: Array[String]): Unit = {
    println("Welcome to Arrow Hangman")
    runCircuit(hangman, List("", "a", "g", "d", "o")).takeWhile(_._1).>>=(_._2).foreach(println)
  }
}