Higher order tail recursive function needs to terminate early

Question

Not sure this exact case has been dealt with before, so here goes.

I have a higher order tail recursive function, which more or less does what I need. It takes a function as one of its arguments.

Currently, if the function returns a left, my recursive function will continue to iterate.

So, what I'm struggling with is how to write it in such a way that, should my function return a left, the recursive function stops iterating.

  def recusriveFunc[T](data: List[T])(acc: Acc)(f : (Acc, T) => Acc): Acc = {
    @tailrec
    def inner(acc: Acc, remaining: List[T]): Acc = {
      if (remaining.isEmpty)
        acc
      else {
        val newAcc: Acc = f(acc, remaining.head)
        inner(newAcc, remaining.tail)
      }
    }
        inner(acc, data)
  }

Kolmar Kolmar · Accepted Answer · 2018-11-02T15:18:54

Assuming that EitherAcc is Either[String, Unit], you can add a check for a failed test acc.isLeft to the condition that ends recursion:

def inner(acc: EitherAcc, remaining: List[T]): EitherAcc = {
  if (remaining.isEmpty || acc.isLeft)
  //                    \___________/ <- additional condition
    acc
  else {
    val newAcc: EitherAcc = f(acc, remaining.head)
    inner(newAcc, remaining.tail)
  }
}

Also, note that you can express yout isPos function with the filterOrElse method of Either:

def isPos(ea: EitherAcc, t: Int): EitherAcc =
  ea.filterOrElse(_ => t > 0, s"$t is not positive")

Higher order tail recursive function needs to terminate early

1 Answers