Как получить причину завершения из рекурсивной функции? - PullRequest
Новая
       6

Как получить причину завершения из рекурсивной функции?

0 голосов
/ 20 сентября 2018

Предположим, что функция зациклена для получения числового результата.Цикл останавливается либо при достижении максимума итераций, либо при выполнении условия «оптимальности».В любом случае значение из токовой петли выводится.Каков функциональный способ получить как этот результат, так и причину остановки?

Для иллюстрации, вот моя реализация Scala примера "Square Roots" в 4.1 из 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)}  
  }

Например, чтобы найти квадратный корень из 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?Или другой функциональный подход будет работать лучше?

Ответы [ 2 ]

0 голосов
/ 20 сентября 2018

Просто верните логические значения, ничего не изменяя: 

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

print 

(2.05,false)
(2.0000000929222947,true)
0 голосов
/ 20 сентября 2018

Как правило, вам нужно вернуть значение, которое включает в себя причину остановки и результат.Использование предлагаемой подписи возврата (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)
  }
}
...