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

Question

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

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

Mais, dans la Raquette, (foldl - 0 '(1 2 3 4)) est de 2, parce que la Raquette "intelligemment" calcule comme ceci: (4 - (3 - (2 - (1 - 0)))), ce qui en effet est de 2.

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

(define (flip bin-fn)
  (lambda (x y)
    (bin-fn y x)))

puis nous avons pu dans la Raquette d'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: Pourquoi est - foldl dans la raquette défini dans un tel impair (non standard et non intuitives) manière, différemment que dans toute autre langue?

Answer 1

• Le Haskell définition n'est pas uniforme. Dans la Raquette, la fonction à deux plis ont le même ordre d'intrants, et, par conséquent, vous pouvez simplement remplacer foldl par foldr et obtenir le même résultat. Si vous le faites avec les Haskell version, vous obtiendrez un résultat différent (généralement).

• C'est le sous-produit de nice où vous êtes invités à choisir ce soit foldl ou foldr selon leurs différences sémantiques. Ma conjecture est que, avec Haskell commande, vous êtes susceptibles de choisir en fonction de l'opération. Vous avez un bon exemple de cela: vous avez utilisé foldl parce que vous voulez soustraire chaque numéro, et c'est une telle "évidence", choix qu'il est facile de négliger le fait qu' foldl est généralement un mauvais choix dans un paresseux de la langue.

• Une autre différence est que le Haskell version est plus limitée que la Raquette version de la manière habituelle: il fonctionne exactement sur une entrée de la liste, alors que la Raquette peut accepter n'importe quel nombre de listes. De ce fait, il est plus important d'avoir un uniforme argument de commande pour la fonction d'entrée).

• Enfin, il est faux de supposer que la Raquette divergé à partir de "de nombreuses autres langages fonctionnels", depuis pliage est loin d'être un nouveau truc, et de la Raquette a des racines qui sont beaucoup plus anciennes que Haskell (ou ces autres langues). La question peut donc aller dans l'autre sens: pourquoi est-Haskell foldl défini d'une manière étrange? (Et non, (-) n'est pas une bonne excuse.)

Answer 2

"différemment que dans toute autre langue"

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

Answer 3

De Racket foldl et foldr (et de SRFI-1 fold et fold-right ) ont la propriété

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

Je suppose que l'ordre des arguments a été choisi pour cette raison.

Answer 4

De la Raquette, de la documentation, de la description de l' foldl:

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

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

l'entrée lst sont parcourus de gauche à droite

Et

foldl processus de la lst dans la constante de l'espace

Je vais spéculer sur la façon dont la mise en œuvre pour que pourrait ressembler, avec une seule liste pour des raisons de simplicité:

(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 gauche à droite de la traversée et de la constante de l'espace sont remplies (avis de la queue de la récursivité en 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 le 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 façon:

(proc acc (car lst))

Ensuite, le résultat serait:

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

Mon point est, la documentation foldl ne pas faire d'hypothèses sur l'ordre d'évaluation des arguments pour proc, il n'a qu'à garantir que la constante de l'espace est utilisé et que les éléments de la liste sont évaluées de gauche à droite.

Comme une note de côté, vous pouvez obtenir l'évaluation souhaitée pour que votre expression en écrivant ceci:

(- 0 1 2 3 4)
> -10