ArrayFoldLeft

De Leek Wars Wiki
Aller à : navigation, rechercher


arrayFoldLeft(Tableau array, Fonction f, ? v0) : ? result

variables Opérations

Réduit le tableau array [v1, v2, ..., vn] par la gauche en partant de la valeur v0 et en appliquant la fonction f. Équivaut à : 1 f(f(f(v0, v1), v2), ...)

Paramètres :

  • Tableau array : Tableau d'origine.
  • Fonction f : Fonction à appliquer.
  • ? v0 : Valeur de départ.

Retour :

  • ? result : Tableau réduit.



Exemples d'utilisation

Cette fonction est une alternative aux boucles. Par souci de clarté, il est souvent préférable de ne l'utiliser que pour remplacer des boucles simples. Je vais illustrer l'utilisation de cette fonction par quelques exemples.

Avec une fonction renvoyant un nombre

Premier exemple : calcul du produit des éléments d'un tableau.

function prod(array){
    return arrayMap(array, function(a,b){return a*b;}, 1);
}

Explication : arrayFoldLeft va calculer successivement plusieurs évaluations de la fonction f qu'on lui a donné :

- f (1, premier élément) : on obtient pour valeur celle dudit premier élément ;

- f (résultat précédent, second élément) : on obtient le produit des deux premiers éléments ;

- f (résultat précédent, troisième élément) : on obtient le produit des trois premiers éléments ;

et ainsi de suite ! On finit donc par avoir le produit de tous les éléments du tableau.


Second exemple (inutile en pratique puisque la fonction ArrayMin fait déjà l'affaire) : trouver le minimum dans un tableau.

function arrayMin(array){
    var firstElement = pop(array);
    return arrayFoldLeft(array, function(a,b){return a<b ? a : b;}, firstElement);
}

Explication : on commence par enlever le premier élément du tableau et le garder en mémoire. On peut alors commencer le Fold proprement dit. Ce Fold va prendre en entrée le tableau dont on cherche le minimum (privé de son premier élément), la fonction f valant function(a,b){return a<b ? a : b;} et le premier élément du tableau. Il va alors se passer les choses suivantes :

- on calcule f (firstElement, second élément du tableau) : f renvoie le plus petit des deux, on a trouvé le plus petit des deux premiers éléments du tableau ;

- on calcule f (résultat précédent, troisième élément du tableau) : f renvoie le plus petit, on a trouvé le plus petit des trois premiers éléments du tableau ;

- on continue jusqu'à la fin : on a alors trouvé le plus petit de tous les éléments du tableau !

Avec une fonction renvoyant un booléen

Écrivons une fonction qui teste s'il y a un élément négatif dans un tableau :

function hasNegativeElement(array){
    return arrayFoldLeft(array, function(bool, x){return bool || (x<0);}, false);
}

Explication : on a pour suite d'appels :

- f (false, premier élément) : on calcule false || (premier élément < 0), ce qui vaut true si le premier élément est négatif, et false sinon ;

- f (résultat précédent, second élément) : on calcule résultat précédent || (second élément < 0), ce qui vaut true si le résultat précédent valait déjà true ou si le second élément est négatif ;

- on continue !

Ce que calcule hasNegativeElement, c'est donc finalement false || (premier élément < 0) || ... || (dernier élément < 0), ce qui vaut bien true si et seulement si un élément du tableau est négatif.

Avec une fonction renvoyant un tableau

On peut par exemple recoder la fonction Reverse qui inverse l'ordre des éléments d'un tableau :

function reverse(array){
    return arrayFoldLeft(array, function(arr, element){unshift(arr,element); return arr;}, []);
}

Suite d'appels :

- f ([], premier élément) renvoie [premier élément] ;

- f (résultat précédent, second élément) renvoie [second élément, premier élément] ;

- f (résultat précédent, troisième élément) renvoie [troisième élément, second élément, premier élément] ;

- et ainsi de suite.

Voir aussi

ArrayFoldRight