如何从递归函数中获得终止原因？

Question

假设一个函数循环以产生数字结果.如果达到最大迭代或满足"最优"条件,则停止循环.在任何一种情况下,都会输出当前循环的值.获得这个结果和停止原因的功能方法是什么？

为了说明,这是我在https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf的 4.1中的"Square Roots"示例的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)
  }
}