Pourquoi foldl est-il défini de manière étrange dans Racket?

Dans Haskell, comme dans de nombreux autres langages fonctionnels, la fonction foldl est définie de telle sorte que, par exemple, foldl (-) 0 [1,2,3,4] = -10 .

C’est correct, car foldl (-) 0 [1, 2,3,4] est, par définition, ((((0 - 1) - 2) - 3) - 4) .

Mais, dans Racket, (foldl - 0 '(1 2 3 4)) est 2, parce que Racket calcule “intelligemment” comme ceci: (4 - (3 - (2 - (1 - 0)))) 2.

Bien sûr, si nous définissons une fonction auxiliaire comme ceci:

 (define (flip bin-fn) (lambda (xy) (bin-fn yx))) 

alors on pourrait dans Racket obtenir le même comportement que dans Haskell: au lieu de (foldl - 0 '(1 2 3 4)) on peut écrire: (foldl (flip -) 0 '(1 2 3 4))

La question est la suivante: pourquoi foldl in racket est-il défini d’une manière aussi étrange (non standard et non intuitive) que dans une autre langue?

  • La définition de Haskell n’est pas uniforme . Dans Racket, la fonction des deux plis a le même ordre d’entrées et vous pouvez donc simplement remplacer foldl par foldr et obtenir le même résultat. Si vous faites cela avec la version Haskell, vous obtiendrez un résultat différent (généralement) – et vous pourrez le voir dans les différents types des deux.

    (En fait, je pense que pour faire une comparaison correcte, vous devriez éviter ces exemples numériques où les deux types de variables sont des entiers.)

  • Cela a le beau sous-produit où vous êtes invité à choisir soit foldl ou foldr fonction de leurs différences sémantiques. Je suppose que, avec la commande de Haskell, vous êtes susceptible de choisir en fonction de l’opération. Vous avez un bon exemple pour cela: vous avez utilisé foldl parce que vous voulez soustraire chaque nombre – et c’est un choix “évident” qu’il est facile de négliger le fait que foldl est généralement un mauvais choix dans un langage paresseux.

  • Une autre différence est que la version Haskell est plus limitée que la version Racket de la manière habituelle: elle fonctionne sur une seule liste d’entrée, alors que Racket peut accepter un nombre illimité de listes. Cela rend plus important d’avoir un ordre d’argument uniforme pour la fonction d’entrée).

  • Enfin, il est faux de supposer que Racket a divergé de “beaucoup d’autres langages fonctionnels”, car le pliage est loin d’être un nouveau truc, et Racket a des racines bien plus anciennes que Haskell (ou ces autres langages). La question pourrait donc aller dans l’autre sens : pourquoi le foldl d’Haskell est- foldl défini de manière étrange? (Et non, (-) n’est pas une bonne excuse.)

Mise à jour historique:

Comme cela semble déranger les gens encore et encore, j’ai fait un peu de travail de jambes. Ce n’est pas définitif en aucune façon, juste mes devinettes de seconde main. N’hésitez pas à le modifier si vous en savez plus, ou même mieux, envoyez un email aux personnes concernées et demandez. Plus précisément, je ne connais pas les dates auxquelles ces décisions ont été sockets. La liste suivante est donc en ordre approximatif.

  • Il y avait d’abord Lisp, et aucune mention de “pli” d’aucune sorte. Au lieu de cela, Lisp a reduce ce qui est très non uniforme, surtout si vous considérez son type. Par exemple :from-end est un argument de mot-clé qui détermine s’il s’agit d’une parsing à gauche ou à droite et utilise différentes fonctions d’accumulateur, ce qui signifie que le type d’accumulateur dépend de ce mot-clé. Cela s’ajoute aux autres hacks: généralement, la première valeur est extraite de la liste (sauf si vous spécifiez une :initial-value . Enfin, si vous ne spécifiez pas de :initial-value et que la liste est vide, la fonction sera appliquée à zéro pour obtenir un résultat.

    Tout cela signifie que la reduce est généralement utilisée pour ce que son nom suggère: réduire une liste de valeurs en une seule valeur, où les deux types sont généralement les mêmes. La conclusion ici est que cela sert une sorte de but similaire au pliage, mais ce n’est pas aussi utile que la construction d’itération de liste générique que vous obtenez avec le pliage. Je suppose que cela signifie qu’il n’y a pas de relation forte entre les opérations de reduce et de repli ultérieur.

  • Le premier langage pertinent qui suit Lisp et a un pli approprié est ML. Le choix qui a été fait ici, comme indiqué dans la réponse de newacct ci-dessous, était d’aller avec la version des types uniformes (c.-à-d. Ce que Racket utilise).

  • La prochaine référence est celle de Bird & Wadler, ItFP (1988), qui utilise différents types (comme dans Haskell). Cependant, ils notent en annexe que Miranda a le même type (comme dans Racket).

  • Miranda a plus tard changé l’ordre des arguments (c.-à-d. Déplacé de l’ordre Racket vers l’ordre Haskell). Plus précisément, ce texte dit:

    ATTENTION – cette définition de foldl diffère de celle des anciennes versions de Miranda. Celui-ci est le même que celui de Bird et Wadler (1988). L’ancienne définition avait les deux arguments de «op» inversés.

  • Haskell a pris beaucoup de choses de Miranda, y compris les différents types. (Mais bien sûr, je ne connais pas les dates, alors peut-être que le changement de Miranda était dû à Haskell.) En tout cas, il est clair à ce stade qu’il n’y avait pas de consensus.

  • OCaml est allé avec la direction de Haskell et utilise différents types

  • Je suppose que “Comment concevoir des programmes” (aka HtDP) a été écrit à peu près à la même période, et ils ont choisi le même type . Il n’y a cependant aucune motivation ou explication – et en fait, après cet exercice, il est simplement mentionné comme l’ une des fonctions intégrées .

    L’implémentation de Racket des opérations de pliage était, bien sûr, les “intégrés” mentionnés ici.

  • Puis est venu SRFI-1 , et le choix était d’utiliser la version de même type (comme Racket). Cette décision était une question de John David Stone, qui souligne un commentaire dans le SRFI qui dit

    Remarque: MIT Scheme et Haskell renversent les arguments de F pour leurs fonctions de reduce et de fold .

    Olin a plus tard parlé de ceci : tout ce qu’il a dit était:

    Bon point, mais je veux une cohérence entre les deux fonctions. valeur d’état d’abord: srfi-1, valeur d’état SML dernière: Haskell

    Notez en particulier son utilisation de la valeur d’ état , qui suggère une vue où les types cohérents sont un point peut-être plus important que l’ordre des opérateurs.

“différemment que dans toute autre langue”

En guise de contre-exemple, le ML standard (ML est un langage fonctionnel très ancien et influent) se foldl également de cette façon: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL

Les foldl et les foldr (ainsi que le fold et le fold-right SRFI-1 ) ont la propriété de

 (foldr cons null lst) = lst (foldl cons null lst) = (reverse lst) 

Je spécule que l’ordre des arguments a été choisi pour cette raison.

À partir de la documentation de Racket, la description de foldl :

 (foldl proc init lst ...+) → any/c 

Deux points d’intérêt pour votre question sont mentionnés:

les entrées sont parcourues de gauche à droite

Et

foldl traite les lsts dans un espace constant

Je vais spéculer sur la façon dont la mise en œuvre pourrait ressembler à cela, avec une liste unique pour simplifier:

 (define (my-foldl proc init lst) (define (iter lst acc) (if (null? lst) acc (iter (cdr lst) (proc (car lst) acc)))) (iter lst init)) 

Comme vous pouvez le voir, les exigences de traversée gauche-droite et d’espace constant sont remplies (notez la récursion de queue dans iter ), mais l’ ordre des arguments pour proc n’a jamais été spécifié dans la description. Par conséquent, le résultat de l’appel du code ci-dessus serait:

 (my-foldl - 0 '(1 2 3 4)) > 2 

Si nous avions spécifié l’ordre des arguments pour proc de cette manière:

 (proc acc (car lst)) 

Le résultat serait alors:

 (my-foldl - 0 '(1 2 3 4)) > -10 

Ce que je foldl dire, c’est que la documentation de foldl ne fait aucune hypothèse sur l’ordre d’évaluation des arguments pour proc , elle doit seulement garantir que l’espace constant est utilisé et que les éléments de la liste sont évalués de gauche à droite.

En tant que note d’accompagnement, vous pouvez obtenir l’ordre d’évaluation souhaité pour votre expression en écrivant simplement ceci:

 (- 0 1 2 3 4) > -10