How to get a termination reason from a recursive function?

Question

Suppose a function is looped to produce a numeric result. The looping is stopped either if the iterations maximum is reached or the "optimality" condition is met. In either case, the value from the current loop is output. What is a functional way to get both this result and the stopping reason?

For illustration, here's my Scala implementation of the "Square Roots" example in 4.1 of https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf.

object SquareRootAlg {
    def next(a: Double)(x: Double): Double = (x + a/x)/2
    def repeat[A](f: A=>A, a: A): Stream[A] = a #:: repeat(f, f(a))

    def loopConditional[A](stop: (A, A) => Boolean)(s: => Stream[A] ): A = s match {
          case a #:: t  if t.isEmpty => a
          case a #:: t => if (stop(a, t.head)) t.head else loopConditional(stop)(t)}  
  }

Eg, to find the square root of 4:

import SquareRootAlg._
val cond = (a: Double, b: Double) => (a-b).abs < 0.01
val alg = loopConditional(cond) _
val s = repeat(next(4.0), 4.0)

alg(s.take(3))  // = 2.05, "maxIters exceeded"
alg(s.take(5)) // = 2.00000009, "optimality reached"

This code works, but doesn't give me the stopping reason. So I'm trying to write a method

 def loopConditionalInfo[A](stop: (A, A)=> Boolean)(s: => Stream[A]):  (A, Boolean) 

outputting (2.05, false) in the first case above, and (2.00000009, true) in the second. Is there a way to write this method without modifying the next and repeat methods? Or would another functional approach work better?

Answer 1

Typically, you need to return a value that includes both a stopping reason and the result. Using the (A, Boolean) return signature you propose allows for this.

Your code would then become:

import scala.annotation.tailrec

object SquareRootAlg {
  def next(a: Double)(x: Double): Double = (x + a/x)/2
  def repeat[A](f: A=>A, a: A): Stream[A] = a #:: repeat(f, f(a))

  @tailrec // Checks function is truly tail recursive.
  def loopConditional[A](stop: (A, A) => Boolean)(s: => Stream[A] ): (A, Boolean) = {
    val a = s.head
    val t = s.tail
    if(t.isEmpty) (a, false)
    else if(stop(a, t.head)) (t.head, true)
    else loopConditional(stop)(t)
  }
}

Answer 2

Just return the booleans without modifying anything else:

object SquareRootAlg {
  def next(a: Double)(x: Double): Double = (x + a/x)/2
  def repeat[A](f: A => A, a: A): Stream[A] = a #:: repeat(f, f(a))

  def loopConditionalInfo[A]
    (stop: (A, A)=> Boolean)
    (s: => Stream[A])
  : (A, Boolean) = s match {
    case a #:: t if t.isEmpty => (a, false)
    case a #:: t => 
      if (stop(a, t.head)) (t.head, true) 
      else loopConditionalInfo(stop)(t)
  }
}

import SquareRootAlg._
val cond = (a: Double, b: Double) => (a-b).abs < 0.01
val alg = loopConditionalInfo(cond) _
val s = repeat(next(4.0), 4.0)

println(alg(s.take(3))) // = 2.05, "maxIters exceeded"
println(alg(s.take(5)))

prints

(2.05,false)
(2.0000000929222947,true)