Recurrent call to a function until it returns None

Question

I often encounter a pattern so I was wondering if there is any convenient method in Scala library for it.

Let it be a function f: A => Option[B]. I would like to do a recurrent call to f beginning with a starting x, f(f(f(x).get).get...), until f returns None and keep the last non-None value.

I wrote an implementation for this:

@tailrec
def recurrentCallUntilNone[B](f: B => Option[B], x: B): B = f(x) match {
  case Some(y) => recurrentCallUntilNone(f, y)
  case None => x
}

Is this already implemented in the standard library?

A usage example for this could be for a list (Zipper) which keeps the current position. By calling next, None is returned if there are no elements after the current position or an Option for the same list, but with current position incremented. By using the above method, an end method can be constructed that seeks the list to the end.

Answer 1

What you are doing looks like a very specific type of trampoline. The more general case uses functions wrapped in case classes instead of an Option and supports different argument and return types.

As Calin-Andrei points out trampolines are available in the standard library using the TailCalls object.

From the first link:

def even2(n: Int): Bounce[Boolean] = {
  if (n == 0) Done(true)
  else Call(() => odd2(n - 1))
}
def odd2(n: Int): Bounce[Boolean] = {
  if (n == 0) Done(false)
  else Call(() => even2(n - 1))
}
trampoline(even2(9999))

sealed trait Bounce[A]
case class Done[A](result: A) extends Bounce[A]
case class Call[A](thunk: () => Bounce[A]) extends Bounce[A]

def trampoline[A](bounce: Bounce[A]): A = bounce match {
  case Call(thunk) => trampoline(thunk())
  case Done(x) => x
}

Now with the standard library

import scala.util.control.TailCalls._

def even2(n: Int): TailRec[Boolean] = {
  if (n == 0) done(true)
  else tailcall(odd2(n - 1))
}
def odd2(n: Int): TailRec[Boolean] = {
  if (n == 0) done(false)
  else tailcall(even2(n - 1))
}
even2(9999).result

Answer 2

How about:

Stream.iterate(Some(x)) { x => x.flatMap(f _) }.takeWhile { _.isDefined }.last

UPDATE

Or even neater IMHO (only single traversal):

val result = {
  val xs = Stream.iterate(Some(x)) { x => x.flatMap(f _) }
  (xs zip xs.tail) collectFirst {
    case (Some(x), None) => x
  } get
}

Note that it is safe to call collectFirst because we cannot start with a None (otherwise an infinite loop would be possible).

Answer 3

in case of a beauty contest, you can build a function that transforms an existing one into the monster you were talking about through the use of currying.

def composeUntilTheEnd[B](f: Option[B] => Option[B])(x: Option[B]): Option[B] = 
        if (f(x) != None) composeUntilTheEnd(f)(f(x))
        else x

def ff = composeUntilTheEnd((x:Option[Int]) => x)_

Now calling ff you get the intended behaviour.

Answer 4

If you want you could create a steam from you options and then use stream functions on it to get the last defined element. (Or rather the last defined element before the undefined element)

def options[B](f: B => Option[B], initialValue: Option[B]): Stream[Option[B]] = {
  initialValue #:: options(f, initialValue.map(f(_)).flatten)
}

options.takeWhile(_.isDefined).last