Artem Malinko Artem Malinko - 3 months ago 21
Scala Question

Why does this code with free monad interpreter compile?

I'm trying to understand free monads. So with help of tutorials I wrote toy example to play with and now I don't understand why does it compile. Here it is:

import cats.instances.all._
import cats.~>

trait Operation[+A]

case class Print(s: String) extends Operation[Unit]

case class Read() extends Operation[String]

object Console {

def print(s: String): Free[Operation, Unit] = Free.liftF(Print(s))

def read: Free[Operation, String] = Free.liftF(Read())


object Interpreter extends (Operation ~> Option) {
// why does this compile?
override def apply[A](fa: Operation[A]): Option[A] = fa match {
case Print(s) => Some(println(s))
case Read() => Some(readLine())

object Main {
def main(args: Array[String]) {
val program = for {
_ <- Console.print("What is your name?")
name <-
_ <- Console.print(s"Nice to meet you $name")
} yield ()

I'm talking about apply method of Interpreter. It should return Option[A], but I can return Option[Unit] and Option[String] here so I assume it should be a compilation error. But it's not. This code compiles and works(although Idea tells me that it's an error). Why is that?

UPD: but why doesn't this compile?

def test[A](o: Operation[A]): Option[A] = o match {
case Print(s) => Some(s)
case Read() => Some(Unit)


Your apply method is supposed to return Option[A] where A is determined by the type of the argument. That is if the argument has type Operation[Unit], the result should also be an Option[Unit] and so on.

Now your body adheres to that contract perfectly. Yes, you do have a case where you return an Option[Unit] instead of a general Option[A], but you only do that if the argument was an instance of Print and thus an Operation[Unit]. That is you only ever return an Option[Unit] when the argument was an Operation[Unit], so the contract is not broken. The same is true with Read and String. Note that if you returned an Option[Unit] in the case for Read, that'd be an error because you'd now be returning a type other than that of the argument.

So that's why the code is semantically correct, but why does it compile? That's because the Scala type checker (unlike IntelliJ's approximation thereof) is smart enough to take the additional type information into account when pattern matching. That is, in the case Print it knows that you've just matched a value of type Operation[A] against a pattern of type Operation[Unit], so it assigns A = Unit inside the case's body.

Regarding your update:

case Print(s) => Some(s)

Here we have a pattern of type Operation[Unit] (remember that Print extends Operation[Unit]), so we should get a result of type Option[Unit], but Some(s) has type Option[String]. So that's a type mismatch.

case Read() => Some(Unit)

First of all Unit it the companion object of the Unit type, so it has its own type, not type Unit. The only value of type Unit is ().

Aside from that, it's the same situation as above: The pattern has type Operation[String], so the result should be Operation[String], not Operation[Unit] (or Operation[Unit.type]).