How to distinguish between None (the constructor) and None.type

What is the correct way to return None from a pattern match? Here is what I tried.


object Simulate {

  def findFinal[Sigma,L,E](dfa:Dfa[L,E], delta:(Sigma,L)=>Boolean)(seq:Seq[Sigma]):Option[State[L,E]] = {
    seq.foldLeft(Some(dfa.q0)) { (mq:Option[State[L,E]], s:Sigma) =>
      mq match {
        case None => None
        case Some(q) =>
          val maybeTransition = q.transitions.find { case Transition(_, l, _) => delta(s, l) }

          maybeTransition match {
            case Some(Transition(_, _, d: State[L, E])) => Some(d) // transition to state d
            case None => None // found an input for which there is no valid transition from state q
          }
      }
    }
  }

But I get a compiler error.

Error:(29, 22) type mismatch;
 found   : None.type
 required: Some[dfa.State[L,E]]
        case None => None

The error is also displayed in IntelliJ

I tried replacing case None => None with either case None => None[State[L,E]] or case None => None[Option[State[L,E]]], and in both cases I get another compiler error:

Error:(29, 26) object None does not take type parameters.
        case None => None[Option[State[L,E]]]

I also tried declaring a local val n of type Option[State[L,E]] and returning that from the case, but I get an even stranger compiler error.


package dfa

object Simulate {

  def findReachableFinal[Sigma,L,E](dfa:Dfa[L,E], delta:(Sigma,L)=>Boolean)(seq:Seq[Sigma]):Option[State[L,E]] = {
    seq.foldLeft(Some(dfa.q0)) { (mq:Option[State[L,E]], s:Sigma) =>
      val n:Option[State[L,E]] = None

      mq match {
        case None => n
        case Some(q) =>
          val maybeTransition = q.transitions.find { case Transition(_, l, _) => delta(s, l) }

          maybeTransition match {
            case Some(Transition(_, _, d: State[L, E])) => Some(d) // transition to state d
            case None => n // found an input for which there is no valid transition from state q
          }
      }
    }
  }
}

The error is this:

Error:(31, 22) type mismatch;
 found   : Option[dfa.State[L,E]]
 required: Some[dfa.State[L,E]]
        case None => n

I think the problem is that you start with Some in foldLeft, try starting with Option:
foldLeft(Option(dfa.q0))

ouch, that devious! The following works.


object Simulate {

  def findReachableFinal[Sigma,L,E](dfa:Dfa[L,E], delta:(Sigma,L)=>Boolean)(seq:Seq[Sigma]):Option[State[L,E]] = {
    val init:Option[State[L,E]] = Some(dfa.q0)
    seq.foldLeft(init) { (mq:Option[State[L,E]], s:Sigma) =>

      mq match {
        case None => None
        case Some(q) =>
          val maybeTransition = q.transitions.find { case Transition(_, l, _) => delta(s, l) }

          maybeTransition match {
            case Some(Transition(_, _, d: State[L, E])) => Some(d) // transition to state d
            case None => None // found an input for which there is no valid transition from state q
          }
      }
    }
  }
}

…or foldLeft[Option[dfa.State[L,E]]](Some(dfa.q0)) { ... }

1 Like

Just an aside: The nested Option match might be rewritten as flatMap/map (~ for/yield).

1 Like

This might not be helpful, but my experience has been that directly constructing objects via Some or None always ends up causing me some heartburn with types. Per @sangamon’s advice, I prefer to always use Option for instantiating an optional value, map, flatMap and filter (or an equivalent for-comprehension) for transforming it (transforms are a no-op if it’s a None, and can be chained with filter in a type-safe way, which is one of the things I love about Options). I tend to only use Some and None directly in pattern matches for value extraction.

While I use Some and None more than that, I largely agree with @wrbriggs1 – you don’t need complicated workarounds, just use the Option() constructor instead of the Some constructor. (Or the Option.empty[T] constructor when you need None in that situation.) That way, the type is inferred as Option[T] instead of Some[T], and the type inference does what you expect…

Side-note – the Option constructor and the Some constructor differ not only in their return type, but also in their handling of null. Option(null) is None while Some(null) is Some(null)

The signature of foldLeft is

def foldLeft[B](z: B)(op: (B, A) ⇒ B): B

Type inference goes one argument list at a time. Since the first argument you give to foldLeft is Some[State[L, E]], it decides the second argument needs to be a (Some[State[L, E]], A) => Some[State[L, T]]]). But you want Option[State[L, E]]] instead of Some[State[L, E]]. You can fix this by replacing

seq.foldLeft(Some(dfa.q0)) { … }

with

seq.foldLeft(Some(dfa.q0): Option[State[L, E]]) { … }

Actually, even better, just provide the type argument to foldLeft. So, instead of

seq.foldLeft(Some(dfa.q0)) { … }

write

seq.foldLeft[Option[State, L, E]]](Some(dfa.q0)) { … }

First of all, many thanks to everyone for the kind and understandable explanation.

Scala is the only statically typed language I’ve ever really used. To me this issue seems really difficult. Is it my imagination? Is it a difficulty particular to Scala linked to forward-only type inferencing, or do other statically typed languages impose the same frustration?

The suggestion to use for is a good one. I don’t usually think of mapping with Option. Thanks for the suggestion.

However, something surprising happens. The following code works using concentric pattern matching

  def findReachableFinal[Sigma, L, E](dfa: Dfa[L, E], delta: (Sigma, L) => Boolean)(seq: Seq[Sigma]): Option[State[L, E]] = {
    val init: Option[State[L, E]] = Some(dfa.q0)
    seq.foldLeft(init) { (mq: Option[State[L, E]], s: Sigma) =>

      mq match {
        case None => None
        case Some(q) =>
          val maybeTransition = q.transitions.find { case Transition(_, l, _) => delta(s, l) }

          maybeTransition match {
            case Some(Transition(_, _, d: State[L, E])) => Some(d) // transition to state d
            case None => None // found an input for which there is no valid transition from state q
          }
      }
    }
  }

If I try to rewrite this directly using for{}, as follows, it get a compilation error.

  def findReachableFinal[Sigma, L, E](dfa: Dfa[L, E], delta: (Sigma, L) => Boolean)(seq: Seq[Sigma]): Option[State[L, E]] = {
    val init: Option[State[L, E]] = Some(dfa.q0)
    seq.foldLeft(init) { (mq: Option[State[L, E]], s: Sigma) =>

      for{
        q <- mq
        Transition(_,_,d:State[L,E]) <- q.transitions.find { case Transition(_, l, _) => delta(s, l) }
      } yield Some(d)
    }
  }

The error is

Error:(33, 19) type mismatch;
 found   : Some[dfa.State[L,E]]
 required: dfa.State[L,E]
      } yield Some(d)

I can correct it by changing yield Some(d) to yield d.

  def findReachableFinal[Sigma, L, E](dfa: Dfa[L, E], delta: (Sigma, L) => Boolean)(seq: Seq[Sigma]): Option[State[L, E]] = {
    val init: Option[State[L, E]] = Some(dfa.q0)
    seq.foldLeft(init) { (mq: Option[State[L, E]], s: Sigma) =>

      for{
        q <- mq
        Transition(_,_,d:State[L,E]) <- q.transitions.find { case Transition(_, l, _) => delta(s, l) }
      } yield d
    }
  }

Throughout the for expression, you basically are inside the Option monad already. Given

def foo(s: String): Option[Int] = ???
def bar(i: Int): Option[(String, Int)] = ???

Then

for {
  i <- foo("test")
  (_, b) <- bar(i)
} yield b

is (roughly) equivalent to

foo("test").flatMap(bar).map { case (_, b) => b }

and both expressions have type Option[Int]. If you do

foo("test").flatMap(bar).map { case (_, b) => Some(b) }

instead, you end up with Option[Option[Int]].

1 Like

This issue is well known and (well known to be) annoying. It’s unique to languages with inference and sub typing.

Once you know what to watch out for, it’s easy to fix, but it remains annoying and something pretty much every new scala user stumbles over at some point.

1 Like