scala - ¿No es ese código en el estilo recursivo de la cola?

functional-programming tail-recursion

Question

Soy algo nuevo para Scala al probarlo mientras leo Beggining Scala de David Pollack. Él define una función recursiva simple que carga todas las cadenas del archivo:

def allStrings(expr: => String): List[String] = expr match {
    case null => Nil
    case w => w :: allStrings(expr)
}

Es elegante e impresionante, excepto que arrojó una excepción StackOverflow cuando intenté cargar un gran archivo de diccionario.

Ahora, por lo que sé, Scala admite la recursividad de cola, por lo que la llamada a la función no podría desbordar la pila, probablemente el compilador no lo reconozca. Así que después de buscar en Google intenté la anotación @tailrec para ayudar al compilador, pero decía

error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
def allStrings(expr: => String): List[String] =

¿Estoy entendiendo mal la recursividad de la cola? ¿Cómo arreglo este código?

Answer 1

No es cola recursiva (y nunca puede ser) porque la operación final no es una llamada recursiva a allStrings , es una llamada al método :: .

La forma más segura de resolver esto es con un método anidado que usa un acumulador:

def allStrings(expr: => String) = {
  @tailrec
  def inner(expr: => String, acc: List[String]): List[String] = expr match {
    case null => acc
    case w => inner(expr, w :: acc)
  }
  inner(expr, Nil)
}

En este caso particular, también puede elevar el acumulador a un parámetro en allStrings , darle un valor predeterminado de Nil y evitar la necesidad de un método interno. Pero eso no siempre es posible, y no se puede llamar muy bien desde el código Java si le preocupa la interoperabilidad.

Answer 2

Scala solo puede optimizar esto si la última llamada es una llamada al método en sí.

Bueno, la última llamada no es a allStrings , sino al método :: (cons).

Una forma de hacer que esta cola sea recursiva es agregar un parámetro de acumulador, por ejemplo:

def allStrings(expr: => String, acc: List[String] = Nil): List[String] =
  expr match {
    case null => acc
    case w => allStrings(expr, w :: acc)
  }

Para evitar que el acumulador se filtre en la API, puede definir el método recursivo de cola como método anidado:

def allStrings(expr: => String) = {
  def iter(expr: => String, acc: List[String]): List[String] =
    expr match {
      case null => acc
      case w => iter(expr, w :: acc)
    }
  iter(expr, Nil)
}