Recurrent call to a function until it returns None

functional-programming, scala

Solution

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

Problem

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.

Original source