Treating None as false ... Option.or()

Question
1

Isn’t there a way to do the following with some sort of map or flatMap or filter without the tmp variable x?

x is an Option, if it is not empty, then I’ve found what I’m looking for and I can return it, otherwise I need to make a recursive call.

  val x = growByOne(c :: cap, findCapExtensions(c, cap, deck - c))
  if (x.nonEmpty)
    x
  else
    recur(cs)

The expression growByOne(c :: cap, findCapExtensions(c, cap, deck - c)).getOrElse(recur(cs)) does not work because getOrElse returns the content of the Option not the Option itself.

I need something like .ifEmpty(recur(cs))

The following is fewer lines of code, but I’m not sure whether it is clearer.

growByOne(c :: cap, findCapExtensions(c, cap, deck - c)) match {
  case None => recur(cs)
  case x@Some(_) => x
}
2

How about x.getOrElse(recur(cs))?

regards,
Siddhartha

3

No, that’s the wrong type. if x has type Option[A] then getOrElse returns type A but recur(cs) returns type Option[A].

4

There is also x.orElse(recur(cs)) for recur(cs) : Option[A].

regards,
Siddhartha

1 Like
5

I don’t have 'orElse`. Maybe that’s a useful 2.13 addition?

6

It is in scala 2.12.10 (I just checked). A lot of the non-breaking collection features were backported

2 Likes
7

According to the 2.6 docs it’s been there a long time. I wonder what I’m doing wrong?

8

oops, it works now. I’m not sure what I was doing wrong before. bizzare.
Thanks Siddhartha.

1 Like
9

use x.map

10

Sorry, I dont’ see how x.map helps? Can you explain more?

11

Yikes!
The following are NOT the same as they would appear. In fact the 1st one FAILS to be tail recursive. :frowning:

        @tailrec
        def recur(remaining: List[Card]): Option[Set[Card]] = {
          remaining match {
            case Nil => None
            case c :: cs =>
              growByOne(c :: cap, findCapExtensions(c, cap, deck - c))
                .orElse(recur(cs))
          }
        }

vs

        @tailrec
        def recur(remaining: List[Card]): Option[Set[Card]] = {
          remaining match {
            case Nil => None
            case c :: cs =>
              match growByOne(c :: cap, findCapExtensions(c, cap, deck - c)) {
                case None => recur(cs)
                case x@Some(_) => x
              }
          }
        }
12

I take it that you mean the first is no tail recursive, as the call recur(cs) is not in tail postion (as .orElse is applied to the result). As far as I can see, one needs an accumulator to make that tail recursive. My attempt is below, but I cannot test it due to missing definitions.

@annotation.tailrec
def recur(remaining: List[Card], ansOpt: Option[Set[Card]] = None): Option[Set[Card]] = 
     ansOpt.orElse(
            remaining match {
              case Nil => None
              case c :: cs =>
                recur(cs,  growByOne(c :: cap, findCapExtensions(c, cap, deck - c)))
            }
          )

regards,
Siddhartha

1 Like
13

The compiler says this is not tail recursive. in fact the call in tail position is a call to .orElse, not a call to recur. If the JVM supported real tail call optimization, then this call to .orElse in tail position could indeed be TC optimized.

14

Do you mean my code above? Unless one of the other functions refers to recur, I am surprised (and would be grateful if someone could clarify why not.

regards,
Siddhartha

15

isn’t orElse a method on option. That method needs to be called AFTER the pattern match and after recur returns. Right?

2 Likes
16

Right – this is pretty much the most common and easy-to-make mistake when writing tail recursion (heaven knows I do it all the time myself). As a rule of thumb, the recursive operation can’t be a parameter to another function, or it will foil the tail recursion.

2 Likes