Understanding Scala for comprehension in this example code

Question

I'm new to the Scala world and have some questions regarding following code.

sealed trait Input
case object Coin extends Input
case object Turn extends Input

case class Machine(locked: Boolean, candies: Int, coins: Int)

object Candy {
  def update = (i: Input) => (s: Machine) =>
    (i, s) match {
      case (_, Machine(_, 0, _)) => s
      case (Coin, Machine(false, _, _)) => s
      case (Turn, Machine(true, _, _)) => s
      case (Coin, Machine(true, candy, coin)) =>
        Machine(false, candy, coin + 1)
      case (Turn, Machine(false, candy, coin)) =>
        Machine(true, candy - 1, coin)
    }

  def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] = for {
    _ <- sequence(inputs map (modify[Machine] _ compose update))
    s <- get
  } yield (s.coins, s.candies)
}

case class State[S, +A](run: S => (A, S)) {
  def map[B](f: A => B): State[S, B] =
    flatMap(a => unit(f(a)))
  def map2[B,C](sb: State[S, B])(f: (A, B) => C): State[S, C] =
    flatMap(a => sb.map(b => f(a, b)))
  def flatMap[B](f: A => State[S, B]): State[S, B] = State(s => {
    val (a, s1) = run(s)
    f(a).run(s1)
  })
}
object State {
    def modify[S](f: S => S): State[S, Unit] = for {
        s <- get // Gets the current state and assigns it to `s`.
        _ <- set(f(s)) // Sets the new state to `f` applied to `s`.
    } yield ()

    def get[S]: State[S, S] = State(s => (s, s))

    def set[S](s: S): State[S, Unit] = State(_ => ((), s))

    def sequence[S,A](sas: List[State[S, A]]): State[S, List[A]] =
        sas.foldRight(unit[S, List[A]](List()))((f, acc) => f.map2(acc)(_ :: _))

    def unit[S, A](a: A): State[S, A] =
        State(s => (a, s))
}

1. In simulateMachine method, what is the first and second _? Feels first one is an ignored output, are those two stands for the same value?
2. The get is from State, how does it get the state of Machine?
3. yield output a Tuple, how does it matching return type State[Machine, (Int, Int)]
4. How to call this simulateMachine method? Looks like I need do initiate Machine state somewhere.

I don't think this document can give me the right comprehension about what is happening under the hood. How can I understand it better?

Answer 1

Here's a slightly more verbose version of simulateMachine that should be a bit easier to understand.

def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] = for {
    _ <- State.sequence(  // this _ means "discard this 'unpacked' value"
      inputs.map(
        (State.modify[Machine] _).compose(update) // this _ is an eta-expansion
      )
    )
    s <- State.get
  } yield (s.coins, s.candies)

"Unpacked" value - for { value <- container } ... basically "unpacks" value from container. Semantics of unpacking is different between different containers - the most straightforward is List or Seq semantics, where value each item of the becomes value and for semantics in this case becomes just iteration. Other notable "containers" are:

• Option - for semantics: value present or not + modifications of the value if present
• Try - for semantics: successful computation or not + modifications of the successful
• Future - for semantics: defining a chain of computations to perform when value becomes present

Practically, each monad (explaining what monad is is haaard :) Try this as a starting point) defines the way to "unpack" and "iterate". Your State is practically a monad (even though it doesn't declare this explicitly) (and btw, there's a canonical State monad you can find in 3rd party libs such as cats or scalaz)

Eta-expansion is explained in this SO answer, but in short it converts a function/method into a function object. Roughly equivalent to x => State.modify[Machine](x)

Or a completely desugared version:

def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] = {
    val simulationStep: Input => State[Machine, Unit] = (State.modify[Machine] _).compose(update) // this _ is an eta-expansion

    State.sequence(inputs.map(input => simulationStep(input)))
      .flatMap(_ => State.get)  // `_ => xyz` creates a function that does not care about it's input
      .map(machine => (machine.candies, machine.coins))
  }

Note that the use of _ in _ => State.get is yet another way _ is used - now it creates a function that doesn't care about it's argument.

Now, answering questions as they are asked:

1. See above :)
2. If you look at desugared version, you'd see that the State.get is passed as a "callback" to flatMap. There are a few hoops to jump through to trace it (I'll leave it as an exercise for you :)), but essentially what it does is to replace the "result" part of the state (A) with the state itself (S)). Trick here is that it does not get the Machine at all - it just "chains" a call to "fetch" the Machine from the S part of state to A part of state.
3. I think desugared version should be pretty self-explanatory. Regarding the for-comprehension version - for fixes the "context" using the first call in the chain, so everything else (including yield) is executed in that "context" - specifically, it's fixed to State[_, _]. yield is essentially equivalent to calling map at the end of the chain, and in State[_, _] semantics, map replaces the A part, but preserves the S part.
4. Candy.simulateMachine(List(Coin, Turn, Coin, Turn)).run(Machine(false, 2, 0))

P.S. your current code still misses State.set method. I'm assuming it's just def set[S](s: => S): State[S, S] = State(_ => (s, s)) - at least adding this makes your snippet compile in my environment.