FoldLeft en utilisant FoldRight dans scala

CE code chaînera plusieurs objets de fonction ensemble, une fonction pour chaque élément de la liste. Voici un exemple qui le montre plus clairement.

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

Vous pouvez l'imaginer comme une liste liée d'objets de fonction. Lorsque vous transmettez une valeur, elle "circule" à travers toutes les fonctions. C'est un peu comme la programmation de flux de données.

Je viens de faire cet exercice, et je voudrais partager comment je suis arrivé à une réponse (fondamentalement la même que ce qui est dans la question, seules les lettres sont différentes), dans l'espoir que cela peut être utile à quelqu'un.

En arrière-plan, commençons par ce que font foldLeft et foldRight. Par exemple, le résultat de foldLeft sur la liste [1, 2, 3] avec l'opération * et la valeur de départ z est la valeur ((z * 1) * 2) * 3

Nous pouvons penser à foldLeft comme consommant des valeurs de la liste de manière incrémentielle, de gauche à droite. En d'autres termes, nous commençons d'abord par la valeur z (ce qui serait le résultat si la liste était vide), puis nous révélons à foldLeft que notre liste commence par 1 et la valeur devient z * 1, puis foldLeft voit notre liste suivante a 2 et la valeur devient (z * 1) * 2, et finalement, après avoir agi sur 3, elle devient la valeur ((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

Cette valeur finale est la valeur que nous voulons atteindre, sauf (comme l'exercice nous le demande) en utilisant foldRight à la place. Maintenant, notez que, tout comme foldLeft consomme des valeurs de la liste, de gauche à droite, foldRight consomme des valeurs de la liste de droite à gauche. Donc sur la liste [1, 2, 3],

• ce foldRight agira sur 3 et [quelque chose], donnant un [résultat]
• ensuite, il agira sur 2 et le [résultat], donnant [result2]
• enfin, il agira sur 1 et [result2] donnant l'expression finale
• nous voulons que notre expression finale soit (((z * 1) * 2) * 3

En d'autres termes: en utilisant foldRight, nous arrivons d'abord à ce que le résultat serait si la liste est vide, alors le résultat si la liste ne contenait que [3], alors le résultat si la liste [2, 3], et enfin le résultat pour la liste [1, 2, 3].

C'est-à-dire, ce sont les valeurs que nous aimerions atteindre, en utilisant foldRight:

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

, Donc nous avons besoin d'aller à partir de z à (z * 3) à (z * 2) * 3 à ((z * 1) * 2) * 3.

En tant que valeurs , nous ne pouvons pas faire ceci: il n'y a pas de moyen naturel de passer de la valeur (z * 3) à la valeur (z * 2) * 3, pour une opération arbitraire *. (Il y a pour la multiplication car c'est commutatif et associatif, mais nous n'utilisons que * pour représenter une opération arbitraire.)

Mais fonctions de, nous pouvons être en mesure de le faire! Nous devons avoir une fonction avec un "espace réservé" ou un "trou": quelque chose qui prendra z et le mettra à la bonne place.

• par exemple, après la première étape (après avoir agi sur 3), nous avons la fonction d'espace réservé z => (z * 3). Ou plutôt, en tant que fonction doit prendre des valeurs arbitraires et nous avons utilisé z pour une valeur spécifique, écrivons ceci comme t => (t * 3). (Cette fonction appliquée à l'entrée z donne la valeur (z * 3).)
• après la deuxième étape (après avoir agi sur 2 et le résultat) nous avons la fonction d'espace réservé t => (t * 2) * 3 peut-être?

Pouvons - nous passer de la première fonction d'espace réservé à la suivante? Laissez

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

Qu'est-Ce que f2, en termes de f1?

f2(t) = f1(t * 2)

Oui, nous pouvons! Donc la fonction que nous voulons prend 2 et f1 et donne f2. Nous allons appelez ça g. Nous avons g(2, f1) = f2 où f2(t) = f1(t * 2), ou en d'autres termes

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

Voyons si cela fonctionnerait si nous le faisions avancer: l'étape suivante serait g(1, f2) = (t => f2(t * 1)) et le RHS est le même que t => f1((t * 1) * 2)) ou t => (((t * 1) * 2) * 3).

On dirait que ça marche! Et enfin, nous appliquons z à ce résultat.

Quelle devrait être l'étape initiale? Nous appliquons g sur 3 et f0 pour obtenir f1, où f1(t) = t * 3 tel que défini ci-dessus, mais également f1(t) = f0(t * 3) de la définition de g. On dirait qu'on a besoin de f0 pour être la fonction identité.

Reprenons.

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

Et enfin, nous appliquons f3 sur z et obtenir l'expression que nous voulons. Tout fonctionne. Alors

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

Ce qui signifie f3 = foldRight(xs, f0)(g)

Soit g, cette fois, au lieu de x * y utilisation d'une fonction arbitraire s(x, y):

• premier arg à g est de type A
• deuxième arg à {[48] } est du type de ces f, qui est B => B
• donc le type de g est (A, (B=>B)) => (B=>B)

• , Donc g est:

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

Mettre tout cela ensemble

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

À ce niveau de travail à travers le livre, je préfère en fait cette forme car elle est plus explicite et plus facile à comprendre. Mais pour se rapprocher de la forme de la solution, nous pouvons intégrer les définitions de f0 et g (nous n'avons plus besoin de déclarer le type de g car il est entré dans foldRight et le compilateur l'infère), donnant:

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)

, Qui est exactement ce qui est en question, juste avec des symboles différents. De même pour foldRight en termes de foldLeft.

Les auteurs du livre fournissent une bonne explication sur leur pagegithub/fpinscala .