FoldLeft usando FoldRight en scala

functional-programming currying

Question

Mientras revisaba la programación funcional en Scala , encontré esta pregunta:

¿Puedes doblar hacia la derecha en términos de foldRight? ¿Qué tal si fuera de la otra manera?

En la solución proporcionada por los autores, han proporcionado una implementación de la siguiente manera:

def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

  def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
    foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

¿Puede alguien ayudarme a rastrear a través de esta solución y hacerme entender cómo esto implementa el plegamiento en términos de foldr y viceversa?

Gracias

Answer 1

Acabo de hacer este ejercicio y me gustaría compartir cómo llegué a una respuesta (básicamente lo mismo que en la pregunta, solo las letras son diferentes), con la esperanza de que pueda ser útil para alguien.

Como fondo, comencemos con lo que foldLeft y foldRight hacen. Por ejemplo, el resultado de foldLeft en la lista [1, 2, 3] con la operación * y el valor inicial z es el valor ((z * 1) * 2) * 3

Podemos pensar en foldLeft como valores de consumo de la lista de forma incremental, de izquierda a derecha. En otras palabras, inicialmente comenzamos con el valor z (que es el resultado si la lista estuviera vacía), luego revelamos a foldLeft que nuestra lista comienza con 1 y el valor se convierte en z * 1 , luego foldLeft ve nuestra lista el siguiente tiene 2 y el valor se convierte en (z * 1) * 2 , y finalmente, después de actuar en 3, se convierte en el valor ((z * 1) * 2) * 3 .

                             1    2    3
Initially:               z
After consuming 1:      (z * 1)
After consuming 2:     ((z * 1) * 2
After consuming 3:    (((z * 1) * 2) * 3

Este valor final es el valor que queremos lograr, excepto (como lo solicita el ejercicio) en foldRight lugar, usar foldRight . Ahora note que, al igual que foldLeft consume los valores de la lista de izquierda a derecha, foldRight consume los valores de la lista de derecha a izquierda. Así que en la lista [1, 2, 3],

• Este foldRight actuará en 3 y [algo], dando un [resultado]
• Entonces actuará sobre 2 y el [resultado], dando [resultado2]
• Finalmente actuará sobre 1 y [result2] dando la expresión final.
• Queremos que nuestra expresión final sea (((z * 1) * 2) * 3

En otras palabras: utilizando foldRight , primero llegamos a lo que sería el resultado si la lista estuviera vacía, luego el resultado si la lista contenía solo [3], luego el resultado si la lista fuera [2, 3] y finalmente el el resultado para la lista es [1, 2, 3].

Es decir, estos son los valores a los que nos gustaría llegar, utilizando foldRight :

                             1    2    3
Initially:                             z
After consuming 3:                 z * 3
After consuming 2:           (z * 2) * 3
After consuming 1:     ((z * 1) * 2) * 3

Así que necesitamos ir de z a (z * 3) a (z * 2) * 3 a ((z * 1) * 2) * 3 .

Como valores , no podemos hacer esto: no hay una forma natural de pasar del valor (z * 3) al valor (z * 2) * 3 , para una operación arbitraria * . (Hay para la multiplicación, ya que es conmutativo y asociativo, pero solo estamos usando * para representar una operación arbitraria).

¡Pero como funciones podemos ser capaces de hacer esto! Necesitamos tener una función con un "marcador de posición" o "agujero": algo que tome z y lo coloque en el lugar adecuado.

• Por ejemplo, después del primer paso (después de actuar en 3) tenemos la función de marcador de posición z => (z * 3) . O más bien, como una función debe tomar valores arbitrarios y hemos estado usando z para un valor específico, escribamos esto como t => (t * 3) . (Esta función aplicada en la entrada z da el valor (z * 3) .)
• Después del segundo paso (después de actuar sobre 2 y el resultado) tenemos la función de marcador de posición t => (t * 2) * 3 tal vez?

¿Podemos pasar de la función del primer marcador de posición a la siguiente? Dejar

      f1(t) = t * 3
and   f2(t) = (t * 2) * 3

¿Qué es f2 en términos de f1 ?

f2(t) = f1(t * 2)

¡Si podemos! Así que la función que queremos toma 2 y f1 y da f2 . Llamemos a esto g . Tenemos g(2, f1) = f2 donde f2(t) = f1(t * 2) o en otras palabras

g(2, f1) = 
    t => f1(t * 2)

Veamos si esto funcionaría si lo llevamos adelante: el siguiente paso sería g(1, f2) = (t => f2(t * 1)) y el RHS es igual que t => f1((t * 1) * 2)) o t => (((t * 1) * 2) * 3) .

¡Parece que funciona! Y finalmente aplicamos z a este resultado.

¿Cuál debería ser el paso inicial? Aplicamos g en 3 y f0 para obtener f1 , donde f1(t) = t * 3 como se definió anteriormente, pero también f1(t) = f0(t * 3) de la definición de g . Así que parece que necesitamos que f0 sea ​​la función de identidad.

Vamos a empezar de nuevo.

Our foldLeft(List(1, 2, 3), z)(*) is ((z * 1) * 2) * 3
Types here: List(1, 2, 3) is type List[A]
             z is of type B
             * is of type (B, A) -> B
             Result is of type B
We want to express that in terms of foldRight
As above:
 f0 = identity. f0(t) = t.
 f1 = g(3, f0). So f1(t) = f0(t * 3) = t * 3
 f2 = g(2, f1). So f2(t) = f1(t * 2) = (t * 2) * 3
 f3 = g(1, f2). So f3(t) = f2(t * 1) = ((t * 1) * 2) * 3

Y finalmente aplicamos f3 en z y obtenemos la expresión que queremos. Todo funciona. Asi que

f3 = g(1, g(2, g(3, f0)))

que significa f3 = foldRight(xs, f0)(g)

Definamos g , esta vez en lugar de x * y usando una función arbitraria s(x, y) :

• primer arg a g es de tipo A
• segundo arg a g es del tipo de estos f ''s, que es B => B
• Entonces el tipo de g es (A, (B=>B)) => (B=>B)

• Así que g es:

  def g(a: A, f: B=>B): B=>B = 
      (t: B) => f(s(t, a))

Poniendo todo esto junto

def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B = {
    val f0 = (b: B) => b

    def g(a: A, f: B=>B): B=>B =
        t => f(s(t, a))

    foldRight(xs, f0)(g)(z)
}

En este nivel de trabajo a través del libro, en realidad prefiero este formulario, ya que es más explícito y más fácil de entender. Pero para acercarnos a la forma de la solución, podemos alinear las definiciones de f0 y g (ya no necesitamos declarar el tipo de g como entrada para foldRight y el compilador lo infiere), dando:

def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B =
  foldRight(xs, (b: B) => b)((a, f) => t => f(s(t, a)))(z)

que es exactamente lo que está en la pregunta, solo con diferentes símbolos. Del mismo modo para foldRight en términos de foldLeft.

Answer 2

Echemos un vistazo a

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

(El otro pliegue es similar). El truco es que durante la operación de plegado correcto, no generamos el valor final del tipo B En su lugar, construimos una función de B a B El paso de plegado toma un valor de tipo a: A y una función g: B => B y produce una nueva función (b => g(f(b,a))): B => B Esta función se puede expresar como una composición de g con f(_, a) :

  l.foldRight(identity _)((a,g) => g compose (b => f(b,a)))(z);

Podemos ver el proceso de la siguiente manera: Para cada elemento a de l tomamos la aplicación parcial b => f(b,a) , que es una función B => B Luego, compose todas estas funciones de tal manera que la función correspondiente al elemento más a la derecha (con el que comenzamos el recorrido) está en el extremo izquierdo de la cadena de composición. Finalmente, aplicamos la función compuesta grande en z . Esto da como resultado una secuencia de operaciones que comienza con el elemento situado más a la izquierda (que está en el extremo derecho de la cadena de composición) y termina con la más a la derecha.

Actualización: como ejemplo, examinemos cómo funciona esta definición en una lista de dos elementos. Primero, reescribiremos la función como

def foldLeftViaFoldRight[A,B](l: List[A], z: B)
                             (f: (B,A) => B): B =
{
  def h(a: A, g: B => B): (B => B) =
    g compose ((x: B) => f(x,a));
  l.foldRight(identity[B] _)(h _)(z);
}

Ahora vamos a calcular lo que pasa cuando lo pasamos List(1,2) :

List(1,2).foldRight(identity[B] _)(h _)
  = // by the definition of the right fold
h(1, h(2, identity([B])))
  = // expand the inner `h`
h(1, identity[B] compose ((x: B) => f(x, 2)))
  =
h(1, ((x: B) => f(x, 2)))
  = // expand the other `h`
((x: B) => f(x, 2)) compose ((x: B) => f(x, 1))
  = // by the definition of function composition
(y: B) => f(f(y, 1), 2)

Aplicando esta función a z rendimientos.

f(f(z, 1), 2)

según sea necesario.

Answer 3

Ese código está encadenando varios objetos de función, una función para cada elemento de la lista. Aquí hay un ejemplo que muestra eso más claramente.

val f = (a: Int, b: Int) => a+b
val list = List(2,3,4)
println(list.foldLeft(1)(f))

val f1 = (b: Int) => f(b, 2)
val f2 = (b: Int) => f(b, 3)
val f3 = (b: Int) => f(b, 4)
val f4 = (b: Int) => b

val ftotal = f1 andThen f2 andThen f3 andThen f4
println(ftotal(1))

Puedes imaginarlo como una lista enlazada de objetos de función. Cuando se pasa un valor, "fluye" a través de todas las funciones. Es un poco como la programación de flujo de datos.

Answer 4

Los autores del libro proporcionan una buena explicación en su página de github/fpinscala .