Réimplémentation de LINQ to Objects : partie 13 - « Aggregate »

EDIT : j'ai dû modifier ce billet en profondeur depuis qu'un second bogue a été découvert… Pour faire simple, mon implémentation de la première surcharge était complètement fausse.

Mon tweet de la nuit dernière demandant quel opérateur implémenter ensuite s'est conclu par une victoire de l'opérateur Aggregate, alors, allons-y !

Aggregate a trois surcharges, dont deux correspondent à des valeurs par défaut des paramètres de la troisième.

public static TSource Aggregate<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, TSource, TSource> func) 

public static TAccumulate Aggregate<TSource, TAccumulate>( 
    this IEnumerable<TSource> source, 
    TAccumulate seed, 
    Func<TAccumulate, TSource, TAccumulate> func) 

public static TResult Aggregate<TSource, TAccumulate, TResult>( 
    this IEnumerable<TSource> source, 
    TAccumulate seed, 
    Func<TAccumulate, TSource, TAccumulate> func, 
    Func<TAccumulate, TResult> resultSelector)

Aggregate est une méthode d'extension qui fonctionne selon le principe d'exécution immédiate et retourne un résultat simple. Son comportement général est le suivant :

• on commence avec une graine. Pour la première surcharge, elle est « remplacée » par la première valeur de la séquence d'entrée. La graine est utilisée comme la première valeur de l'accumulateur ;
• pour chaque élément de la liste, on applique la fonction d'agrégation qui prend en paramètre la valeur courante de l'accumulateur et la nouvelle valeur récupérée, et retourne une nouvelle valeur pour l'accumulateur ;
• une fois que la séquence d'entrée est épuisée, on applique éventuellement une fonction de projection finale pour obtenir un résultat. Si aucune projection n'a été précisée, nous pouvons imaginer que la fonction identité a été fournie.

Les signatures donnent l'impression que tout est plus compliqué qu'il n'y paraît à cause des différents types de paramètres impliqués. Vous pouvez considérer les surcharges comme si vous traitiez trois types différents, même si les deux premières ont effectivement moins de types de paramètres :

• TSource est toujours le type des éléments de la séquence ;
• TAccumulate est le type de l'accumulateur, et donc de la graine. Pour la première surcharge où aucune graine n'est fournie, TAccumulate est identique à TSource ;
• TResult est le type de retour quand il y a une projection finale impliquée. Pour les deux premières surcharges, TResult est effectivement identique à TAccumulate (à nouveau, pensez à une « projection identité » par défaut si rien d'autre n'est précisé).

Dans la première surcharge qui utilise le premier élément de la séquence comme graine, une exception de type InvalidOperationException est levée si la séquence d'entrée est vide.

Évidemment, la validité des arguments est relativement simple à tester : source, func et resultSelector ne peuvent pas être null. Il y a cependant deux approches différentes pour tester les cas de succès.

Nous pourrions déterminer exactement quand un délégué doit être appelé et avec quelles valeurs - simuler effectivement chaque étape de l'itération. Ce serait contraignant, mais néanmoins une manière très robuste de procéder.

L'approche alternative consiste à sélectionner un échantillon de données et une fonction d'agrégation, produire le résultat et vérifier qu'il correspond à la valeur attendue. Si le résultat a peu de risque d'être produit par chance, c'est probablement suffisant et beaucoup plus simple à implémenter. Voici un exemple pour le test le plus compliqué qui comporte une graine et une projection finale :

[Test] 
public void SeededAggregationWithResultSelector() 
{ 
    int[] source = { 1, 4, 5 }; 
    int seed = 5; 
    Func<int, int, int> func = (current, value) => current * 2 + value; 
    Func<int, string> resultSelector = result => result.ToInvariantString(); 
    // First iteration: 5 * 2 + 1 = 11 
    // Second iteration: 11 * 2 + 4 = 26 
    // Third iteration: 26 * 2 + 5 = 57 
    // Result projection: 57.ToString() = "57" 
    Assert.AreEqual("57", source.Aggregate(seed, func, resultSelector)); 
}

Maintenant, je dois l'admettre, je n'effectue pas des tests exhaustifs - j'utilise les mêmes types pour TSource et TAccumulate - mais franchement, ils me confortent dans l'idée que mon implémentation est correcte.

EDIT : ma projection finale appelle maintenant ToInvariantString. Elle devait simplement appeler ToString, mais comme j'ai maintenant été persuadé que pour certaines cultures cela ne nous donnerait pas le bon résultat, j'ai implémenté une méthode d'extension qui signifie concrètement que x.ToInvariantString() est équivalent à x.ToString(CultureInfo.InvariantCulture). De cette façon, nous n'avons plus à nous inquiéter des cultures avec des représentations numériques différentes, etc.

Juste pour le plaisir de l'exhaustivité (je me suis autopersuadé d'améliorer ce code en écrivant le billet), voici un exemple qui additionne des entiers, mais résulte en un long, de sorte que le résultat est plus grand que Int32.MaxValue. Je ne me suis pas encombré ici d'une projection finale.

[Test] 
public void DifferentSourceAndAccumulatorTypes() 
{ 
    int largeValue = 2000000000; 
    int[] source = { largeValue, largeValue, largeValue }; 
    long sum = source.Aggregate(0L, (acc, value) => acc + value); 
    Assert.AreEqual(6000000000L, sum); 
    // Just to prove we haven't missed off a zero... 
    Assert.IsTrue(sum > int.MaxValue);  
}

Depuis ma première version de ce billet, j'ai également ajouté des tests concernant des séquences vides (pour lesquelles la première surcharge devrait lever une exception) et un test qui vérifie le fait que la première surcharge utilise le premier élément de la séquence comme graine plutôt que la valeur par défaut du type des éléments de la séquence d'entrée.

Soit, assez de tests ! Voyons ce qu'il en est avec le vrai code…

Je m'interroge toujours quant à l'efficacité d'implémenter une méthode en fonction d'une autre, lorsque j'y suis confronté, mais à cet instant, mon sentiment est que c'est une bonne idée lorsque :

• vous implémentez un opérateur en réutilisant une surcharge du même opérateur. En d'autres termes, aucun opérateur inattendu n'apparaîtra dans la pile d'invocation de l'appelant ;
• il n'y a aucune dégradation significative des performances à procéder ainsi ;
• le comportement observé est exactement le même, y compris en ce qui concerne la validation des arguments ;
• le code final est plus simple à comprendre (évident).

Contrairement à ce que j'avais écrit dans une version précédente de ce billet, la première surcharge ne peut être implémentée en se basant sur la deuxième ou la troisième, à cause de son comportement vis-à-vis de la graine et des séquences vides.

public static TSource Aggregate<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, TSource, TSource> func) 
{ 
    if (source == null) 
    { 
        throw new ArgumentNullException("source"); 
    } 
    if (func == null) 
    { 
        throw new ArgumentNullException("func"); 
    } 

    using (IEnumerator<TSource> iterator = source.GetEnumerator()) 
    { 
        if (!iterator.MoveNext()) 
        { 
            throw new InvalidOperationException("Source sequence was empty"); 
        } 
        TSource current = iterator.Current; 
        while (iterator.MoveNext()) 
        { 
            current = func(current, iterator.Current); 
        } 
        return current; 
    } 
}

Cela à cependant toujours du sens de partager l'implémentation entre la deuxième et la troisième surcharge. Les alternatives sont : implémenter la seconde surcharge en fonction de la troisième (en lui fournissant une fonction identité de projection) ou implémenter la troisième surcharge en fonction de la deuxième (en invoquant simplement la seconde surcharge, puis en appliquant la projection). Évidemment, appliquer une projection identité non-nécessaire engendre une pénalité au niveau de la performance, mais c'est une pénalité minuscule. Donc, laquelle est la plus lisible ? Je n'arrive pas à me décider. J'aime le code où différentes méthodes invoquent une méthode « centrale » où tout le vrai code est situé (ce qui suggère d'implémenter la seconde surcharge en fonction de la troisième), mais en même temps, je reste persuadé que le rôle de l'opérateur Aggregate reste d'obtenir la valeur finale de l'accumulateur avec la touche supplémentaire, dans la troisième surcharge, d'une projection. Je suppose que cela dépend de la façon dont vous considérez la projection finale : comme un élément à part entière ou comme une étape supplémentaire.

Pour l'instant, je m'en suis tenu à l'approche « placer toute la logique à un seul endroit ».

public static TAccumulate Aggregate<TSource, TAccumulate>( 
    this IEnumerable<TSource> source, 
    TAccumulate seed, 
    Func<TAccumulate, TSource, TAccumulate> func) 
{ 
    return source.Aggregate(seed, func, x => x); 
} 

public static TResult Aggregate<TSource, TAccumulate, TResult>( 
    this IEnumerable<TSource> source, 
    TAccumulate seed, 
    Func<TAccumulate, TSource, TAccumulate> func, 
    Func<TAccumulate, TResult> resultSelector) 
{ 
    if (source == null) 
    { 
        throw new ArgumentNullException("source"); 
    } 
    if (func == null) 
    { 
        throw new ArgumentNullException("func"); 
    } 
    if (resultSelector == null) 
    { 
        throw new ArgumentNullException("resultSelector"); 
    } 
    TAccumulate current = seed; 
    foreach (TSource item in source) 
    { 
        current = func(current, item); 
    } 
    return resultSelector(current); 
}

L'essentiel du « vrai travail » réside dans la validation des arguments. L'itération est presque douloureusement simple.

La morale du jour est de lire soigneusement la documentation, car quelquefois il y a un comportement inattendu à implémenter. Je ne sais toujours pas vraiment pourquoi cette différence existe entre les comportements… J'ai le sentiment que la première surcharge devrait se comporter comme la deuxième, avec simplement une graine par défaut. EDIT : il semble qu'il faille vraiment lire soigneusement la documentation, mot à mot ; sinon vous pourriez publier une gaffe embarrassante dans un billet de blog. <soupir>

La seconde morale devrait porter sur l'utilisation de l'opérateur Aggregate. C'est un opérateur vraiment générique, et vous pouvez implémenter de nombreux autres opérateurs (Sum, Max, Min, Average, etc.) en l'utilisant. D'une certaine façon, c'est l'équivalent scalaire de l'opérateur SelectMany, en ce qui concerne sa versatilité. Peut-être que je montrerai des implémentations d'opérateurs futurs en utilisant Aggregate…

Pour la suite, j'ai eu des demandes pour certains opérateurs ensemblistes (Distinct, Union, etc.). Je les regarderai probablement prochainement.

Merci à Jon Skeet de m'avoir autorisé à traduire son article Reimplementing LINQ to Objects : Part 13 - Aggregate.

Merci à Thomas Levesque (tomlev) pour sa relecture technique toujours bienvenue.

Merci à milkoseck pour la relecture orthographique de ce document.