Différence entre reduce et foldLeft / fold dans la programmation fonctionnelle (particulièrement Scala et Scala APIs)?

réduire vs foldLeft

une grande différence, non mentionnée dans aucune autre réponse de débordement de piles relative à ce sujet clairement, est que reduce doit être donnée un monoïde commutatif , c.-à-d. une opération qui est à la fois commutative et associative. Cela signifie que l'opération peut être parallélisée.

cette distinction est très importante pour le Big Data / MPP / distributed computing, et toute la raison pour laquelle reduce existe même. La collection peut être découpée et le reduce peut fonctionner sur chaque morceau, puis le reduce peut fonctionner sur les résultats de chaque morceau - en fait, le niveau de chunking ne doit pas arrêter un niveau profond. Nous pourrions couper chaque morceau. C'est pourquoi la sommation d'entiers dans une liste est O(log N) Si on lui donne un nombre infini de CPU.

si vous regardez juste les signatures il n'y a aucune raison pour que reduce existe parce que vous pouvez atteindre tout ce que vous pouvez avec reduce avec un foldLeft . La fonctionnalité de foldLeft est supérieure à celle de reduce .

mais vous ne pouvez pas mettre en parallèle un foldLeft , donc son runtime est toujours O(N) (même si vous vous nourrissez dans un monoïde commutatif). C'est parce qu'il est supposé que l'opération est pas un monoïde commutatif et donc la valeur cumulée est calculée par une série d'séquentielle agrégation.

foldLeft ne suppose ni commutativité ni associativité. C'est l'associativité qui donne la capacité de découper la collection, et c'est la commutativité qui rend le cumul facile parce que l'ordre n'est pas important (donc ce n'est pas important quel ordre pour agréger chacun des résultats de chacun des morceaux). La commutativité à proprement parler n'est pas nécessaire pour la parallélisation, par exemple les algorithmes de tri distribués, elle rend juste la logique plus facile parce que tu n'as pas besoin de donner un ordre à tes morceaux.

si vous avez un regard à la documentation Spark pour reduce il dit spécifiquement"... opérateur binaire commutatif et associatif "

http://spark.apache.org/docs/1.0.0/api/scala/index.html#org.apache.spark.rdd.RDD

Voici la preuve que reduce N'est pas seulement un cas spécial de foldLeft

scala> val intParList: ParSeq[Int] = (1 to 100000).map(_ => scala.util.Random.nextInt()).par

scala> timeMany(1000, intParList.reduce(_ + _))
Took 462.395867 milli seconds

scala> timeMany(1000, intParList.foldLeft(0)(_ + _))
Took 2589.363031 milli seconds

réduire vs pli

maintenant, c'est ici qu'il se rapproche un peu plus des racines mathématiques FP/, et un peu plus difficile à expliquer. Reduce est formellement défini comme faisant partie du paradigme MapReduce, qui traite des collections sans ordre (multisets), le pli est formellement défini en termes de récursion (voir catamorphisme) et suppose donc une structure / séquence aux collections.

il n'y a pas de fold méthode dans L'ébouillantage parce que sous le (strict) Carte réduire le modèle de programmation nous ne pouvons pas définir fold parce que les morceaux n'ont pas d'ordre et fold ne nécessite que l'associativité, pas la commutativité.

dit simplement, reduce fonctionne sans ordre de cumul, fold exige un ordre de cumul et c'est cet ordre de cumul qui nécessite une valeur zéro et non l'existence de la valeur zéro qui les distingue. À proprement parler reduce devrait travaille sur une collection vide, parce que sa valeur zéro peut être déduite en prenant une valeur arbitraire x puis en résolvant x op y = x , mais cela ne fonctionne pas avec une opération non commutative car il peut exister une valeur zéro gauche et droite qui sont distinctes (i.e. x op y != y op x ). Bien sûr, Scala ne prend pas la peine de travailler sur ce que cette valeur Zéro est que cela nécessiterait de faire quelques mathématiques (qui sont sans doute uncomputable), donc jette juste une exception.

il semble (comme c'est souvent le cas en étymologie) que cette signification mathématique originale a été perdue, puisque la seule différence évidente dans la programmation est la signature. Le résultat est que reduce est devenu un synonyme de fold , plutôt que de préserver son sens original de MapReduce. Maintenant, ces termes sont souvent utilisés de façon interchangeable et se comportent de la même façon dans la plupart des implémentations (en ignorant les collections vides). La bizarrerie est exacerbée par des particularités, comme dans Spark, qui nous allons maintenant aborder.

Donc Étincelle ne avoir une fold , mais l'ordre dans lequel les sous-résultats (un pour chaque partition) sont combinées (au moment de l'écriture) est du même ordre dans lequel les tâches sont terminées - et donc non-déterministe. Merci à @CafeFeed d'avoir souligné que fold utilise runJob , qui après avoir lu le code, j'ai réalisé que c'est non déterministe. Une autre confusion est créée par L'étincelle ayant un treeReduce mais pas treeFold .

Conclusion

il y a une différence entre reduce et fold même lorsqu'elle est appliquée à des séquences non vides. La première est définie comme faisant partie du paradigme de programmation MapReduce sur les collections avec un ordre arbitraire ( http://theory.stanford.edu / ~ sergei / papers / soda10-mrc.pdf ) et on devrait supposer que les opérateurs sont commutatifs en plus d'être associatifs à donner résultats déterministes. Ce dernier est défini en termes de catomorphismes et exige que les collections aient une notion de séquence (ou soient définies de façon récursive, comme des listes liées), donc ne nécessitent pas d'opérateurs commutatifs.

dans la pratique en raison de la nature non mathématique de la programmation, reduce et fold ont tendance à se comporter de la même manière, soit correctement (comme dans Scala), soit incorrectement (comme dans Spark).

Extra: mon avis sur la Spark API

mon opinion est que la confusion serait évitée si l'utilisation du terme fold était complètement abandonnée. Au moins spark a une note dans sa documentation:

cela se comporte un peu différemment des opérations de plis mises en œuvre pour collections non distribuées dans des langues fonctionnelles Comme le Scala.