¿Cómo puedo entender este ejemplo de recursión en Scala?

Tengo el siguiente método en Scala que utiliza la recursión:

def foldLeft[Result](initial:Result, op:(Result, Elem) => Result) : Result = {
   if (isEmpty)
     initial
   else
    tail.foldLeft(op(initial,head), op)

Sin embargo, no entiendo cómo funciona la recursión en la última línea. Parece un poco convocado para mí porque el dobleizquierda se llama en la cola de una lista antes de que se haga otra cosa. ¿Cómo se ven los niveles de recursión aquí?

¿Puede alguien explicar cómo funciona esto exactamente?

Pregunta hecha hace 3 años, 4 meses, 29 días - Por binarybuilder

3 Respuestas:

• No estoy seguro de lo que quieres decir con "el dobleizquierda se llama en la cola de una lista antes de que se haga otra cosa". Llamada tail.foldLeft es la última cosa hecha (en el caso de una lista no vacía.

  Scala (como la mayoría de los idiomas en uso amplio hoy) utiliza un estricto estrategia para evaluar una aplicación de la función (Haskell es probablemente el lenguaje más utilizado que utiliza una estrategia no restrictiva, y Scala es probablemente el lenguaje más utilizado que apoya directamente la exclusión de la estrategia estricta). Esto significa que cuando se aplica una función, los argumentos son completamente evaluados y luego pasan a la función.

  Por lo tanto, es absolutamente correcto imaginar el compilador traduciendo el código en la pregunta al equivalente en Scala:

  if (isEmpty) {
    initial
  } else {
    val _arg1 = op(initial, head)
    tail.foldLeft(_arg1, op)
  }
  

  Por ejemplo

  List(1, 2, 3, 4).foldLeft(0, _ + _)
  

  evaluaría en (porque List(1, 2, 3, 4) no está vacía)

  List(2, 3, 4).foldLeft(1, _ + _)
  

  y luego hacia (desde entonces) List(2, 3, 4) no está vacía)

  List(3, 4).foldLeft(3, _ + _)
  

  y luego hacia (desde entonces) List(3, 4) no está vacía)

  List(4).foldLeft(6, _ + _)
  

  y luego hacia (desde entonces) List(4) no es vacío; y suponiendo que usted está usando Nil para representar la lista vacía)

  Nil.foldLeft(10, _ + _)
  

  y luego hacia (desde entonces) Nil está vacía)

  10
  

  Respondida el Dec 17, 2020 a las 00:26 - por bughunterx

  Votos positivos: 0 | Votos negativos: 0

  Votar positivo

  Votar negativo

---

• Claro, te puedo explicar cómo funciona la recursión en este ejemplo de Scala.

  En el método foldLeft, se realiza una operación de plegado en una lista recursivamente. El método toma dos parámetros: initial, que es el valor inicial del plegado, y op, que es una función que define la operación a realizar en cada elemento de la lista.

  En la última línea tail.foldLeft(op(initial,head), op), la recursión se lleva a cabo llamando al método foldLeft en la cola de la lista (tail). Lo que hace esta llamada es aplicar la operación op al valor actual acumulado (initial) y el siguiente elemento de la lista (head), y luego pasar ese valor acumulado actualizado junto con la función op a la llamada recursiva en la cola de la lista (tail).

  En cada llamada recursiva, el valor acumulado se actualiza con el resultado de aplicar la operación op al valor actual y el siguiente elemento de la lista. Este proceso continúa hasta que la lista esté vacía, en cuyo caso se devuelve el valor acumulado final.

  En resumen, la recursión en este ejemplo se realiza de manera acumulativa, aplicando la operación definida por la función op en cada elemento de la lista y actualizando el valor acumulado en cada paso. La recursión termina cuando la lista está vacía y se devuelve el valor acumulado final.

  Respondida el Dec 18, 2020 a las 00:29 - por Gpt

  Votos positivos: 0 | Votos negativos: 0

  Votar positivo

  Votar negativo

---

• Cómo funciona la recursión en el ejemplo de Scala:

  La función foldLeft implementa el pliegue por la izquierda para una lista, reduciendo iterativamente la lista de elementos a un único resultado.

  Explicación de la última línea:

  scala
  tail.foldLeft(op(initial,head), op)
  

  Esta línea invoca recursivamente foldLeft en la cola de la lista (el resto de la lista sin el elemento principal). Como argumento inicial, proporciona el resultado de aplicar op al initial y al head de la lista actual.

  Niveles de recursión:

  El método se llama inicialmente en la lista completa, con initial como argumento inicial. Para cada elemento en la lista, se llama recursivamente a foldLeft en la cola de la lista. El argumento inicial para cada llamada recursiva es el resultado de aplicar op al argumento inicial anterior y al elemento actual. La recursión continúa hasta que se alcanza el elemento final de la lista. En ese punto, el argumento inicial de la llamada final se devuelve como el resultado.

  Ejemplo:

  Supongamos que tenemos la lista List(1,2,3) y queremos sumar todos sus elementos usando foldLeft:

  Inicialmente, se llama a foldLeft en toda la lista con initial=0. La primera llamada recursiva se realiza en List(2,3) con initial=1. La segunda llamada recursiva se realiza en List(3) con initial=3. La tercera llamada recursiva se realiza en List() con initial=6. Como List() está vacía, se devuelve initial=6. Las llamadas recursivas anteriores devuelven este valor, resultando en un resultado final de 6.

  Conclusión:

  La recursión en la última línea permite que foldLeft reduzca iterativamente la lista aplicando repetidamente la operación especificada (op) a cada elemento y el argumento inicial acumulado. El proceso continúa hasta que se alcanza el elemento final y se devuelve el resultado acumulado.

  Respondida el Dec 18, 2020 a las 00:33 - por Gemini

  Votos positivos: 0 | Votos negativos: 0

  Votar positivo

  Votar negativo

---