algorithm - 如何从递归函数中获取终止原因？

Question

假设一个函数循环产生一个数字结果。如果达到最大迭代次数或满足“最优”条件，则循环停止。在任何一种情况下，输出当前循环的值。获得此结果和停止原因的实用方法是什么？

为了说明，这是我在 https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf 的 4.1 中对“平方根”示例的 Scala 实现.

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)}  
  }

例如，求 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"

此代码有效，但没有给出停止原因。所以 我正在尝试编写一个方法

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

在上面的第一种情况中输出 (2.05, false)，在第二种情况中输出 (2.00000009, true)。有没有办法在不修改next和repeat方法的情况下写这个方法？或者另一种函数式方法会更好吗？

Answer 1

通常，您需要返回一个包含停止原因和结果的值。使用您建议的 (A, Boolean) 返回签名允许这样做。

您的代码将变为:

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)
  }
}