Utilisation pratique du pli / réduire dans les langages fonctionnels

Question

Fold (alias reduce) est considérée comme une fonction d'ordre supérieur très important. Map peut être exprimée en termes de fold ( voir ici ). Mais il semble plus que pratique pour academical moi. Une utilisation typique pourrait être d'obtenir la somme, ou d'un produit, ou un maximum de chiffres, mais ces fonctions acceptent généralement un certain nombre d'arguments. Alors, pourquoi (fold + 0 '(2 3 5)) d'écriture lorsque (+ 2 3 5) fonctionne très bien. Ma question est, dans quelle situation est-il plus facile ou plus fold naturelle à l'utilisation?

Answer 1

Le point de fold est qu'il est plus abstrait. Ce n'est pas que vous pouvez faire des choses que vous ne pouviez pas avant, il est que vous pouvez les faire plus facilement.

L'utilisation d'un fold, vous pouvez généraliser toute fonction qui est défini sur deux éléments à appliquer à un nombre arbitraire d'éléments. Ceci est une victoire, car il est généralement beaucoup plus facile à écrire, tester, maintenir et modifier une seule fonction qui applique deux arguments que d'une liste. Et il est toujours plus facile d'écrire, tester, maintenir, etc. fonction d'une simple, au lieu de deux avec des fonctionnalités similaires, mais-pas tout à fait.

Depuis fold (et pour cette matière, map, filter et amis) ont un comportement bien défini, il est souvent beaucoup plus facile de comprendre le code en utilisant ces fonctions que récursion explicite.

En fait, une fois que vous avez une version, vous obtenez l'autre « gratuitement ». En fin de compte, vous finissez par faire moins de travail pour obtenir le même résultat.

Answer 2

Voici quelques exemples simples où reduce fonctionne très bien.

Trouvez la somme des valeurs maximales de chaque sous-liste

Clojure:

user=> (def x '((1 2 3) (4 5) (0 9 1)))
#'user/x
user=> (reduce #(+ %1 (apply max %2)) 0 x)
17

Racket:

> (define x '((1 2 3) (4 5) (0 9 1)))
> (foldl (lambda (a b) (+ b (apply max a))) 0 x)
17

Construire une carte à partir d'une liste

Clojure:

user=> (def y '(("dog" "bark") ("cat" "meow") ("pig" "oink")))
#'user/y
user=> (def z (reduce #(assoc %1 (first %2) (second %2)) {} y))
#'user/z
user=> (z "pig")
"oink"

Pour un exemple plus compliqué de clojure avec reduce, consultez ma solution aux problèmes projet Euler 18 et 67 .

Voir aussi: réduire par rapport à appliquer

Answer 3

Dans les fonctions communes Lisp n'accepte pas d'arguments.

Il y a une constante définie dans chaque implémentation Common Lisp CALL-ARGUMENTS-LIMITE , qui doit être 50 ou plus.

Cela signifie que toute fonction écrite portably devrait accepter au moins 50 arguments. Mais il pourrait être seulement 50.

Cette limite existe pour permettre à des compilateurs optimisés éventuellement utiliser des systèmes d'appel et de ne pas fournir le cas général, où un nombre illimité d'arguments pourrait être passé.

Ainsi, pour traiter de très grandes (plus de 50 éléments) des listes ou des vecteurs dans le code portable Common Lisp, il est nécessaire d'utiliser des constructions itération, réduire, carte et similaire. Ainsi, il est également nécessaire de ne pas utiliser de (apply '+ large-list) (reduce '+ large-list), mais l'utilisation.

Answer 4

1. Votre exemple (+ 2 3 4) ne fonctionne que parce que vous savez le nombre d'arguments au préalable. Plie les travaux sur les listes dont la taille peut varier.

2. fold / reduce est la version générale du motif "cdr-ment une liste". Chaque algorithme qui est sur le traitement tous les éléments d'une séquence dans l'ordre et calculer une valeur de retour de qui peut être exprimé avec elle. Il est essentiellement la version fonctionnelle de la boucle foreach.

Answer 5

code à l'aide est généralement fois difficile à lire. Voilà pourquoi les gens préfèrent carte, filtre, existe, somme, etc.-lorsqu'ils sont disponibles. Ces jours, je suis avant tout écrire compilateurs et interprètes; voici quelques façons que j'utilise fois:

• Calculer l'ensemble des variables libres pour une fonction, expression, ou le type
• Ajouter un paramètres de fonction à la table des symboles, par exemple, pour le contrôle de type
• Accumulate la collection de tous sensibles messages d'erreur générés à partir d'une séquence de définitions
• Ajoutez toutes les classes prédéfinies à un interpréteur Smalltalk au démarrage

Ce que toutes ces utilisations ont en commun est qu'ils accumuler des informations sur une séquence dans une sorte de ensemble ou dictionnaire . Éminemment pratique.

Answer 6

Voici un exemple que personne d'autre encore mentionné.

En utilisant une fonction avec une petite interface bien définie comme « pli », vous pouvez remplacer cette mise en œuvre sans casser les programmes qui l'utilisent. Vous pouvez, par exemple, faire une version distribué qui fonctionne sur des milliers de PC , donc un algorithme de tri qui l'utilisaient deviendrait un distribué sorte, etc. Vos programmes deviennent plus robuste, plus simple et plus rapide .

Votre exemple est triviale: + prend déjà un certain nombre d'arguments, va rapidement peu de mémoire, et a déjà été écrit et par celui qui a écrit débogué votre compilateur. Ces propriétés ne sont pas souvent le cas des algorithmes nécessaires pour exécuter.