Solutionnaire des exercices pour apprivoiser la généricité et les λ

Ce qui suit se veut un solutionnaire possible pour les exercices pour apprivoiser la généricité et les λ avec C# que vous trouverez sur exercice-apprivoiser-genericite-lambda.html

EX00 – Énoncé

Écrivez l'algorithme Permuter<T>(ref T a, ref T b) qui permutera les valeurs de a et de b, de telle sorte que le programme suivant :

static void Main()
{
   int i0 = 2, i1 = 3;
   Console.WriteLine($"Avant permutation : {i0}, {i1}");
   Permuter(ref i0, ref i1);
   Console.WriteLine($"Après permutation : {i0}, {i1}");
   double d0 = 2.5, d1 = 3.5;
   Console.WriteLine($"Avant permutation : {d0}, {d1}");
   Permuter(ref d0, ref d1);
   Console.WriteLine($"Après permutation : {d0}, {d1}");
   string s0 = "allo", s1 = "toi";
   Console.WriteLine($"Avant permutation : \"{s0}\", \"{s1}\"");
   Permuter(ref s0, ref s1);
   Console.WriteLine($@"Après permutation : ""{s0}"", ""{s1}""");
}

... affiche ce qui suit :

Avant permutation : 2,3
Après permutation : 3,2
Avant permutation : 2.5,3.5
Après permutation : 3.5,2.5
Avant permutation : "allo","toi"
Après permutation : "toi","allo"

EX00 – Solution

C'est assez simple :

static void Permuter<T>(ref T a, ref T b)
{
   T temp = a;
   a = b;
   b = temp;
}

Notez que le code générique avec C# s'applique typiquement sur des types références (des class), ce qui signifie qu'en général, cette fonction permutera des références passés par référence.

À quoi ça sert au juste?

Permuter deux variables est une opération fondamentale, qui intervient dans une vaste gamme d'algorithmes (incluant à peu près tout ce qui ressemble à un tri).

EX01 – Énoncé

Écrivez l'algorithme Transformer<T,U>(List<T> src, Func<T,U> fct) qui retourne une List<U> contenant un équivalent des éléments de la List<T> reçue en paramètre, mais transformés par application de la fonction fct, de telle sorte que le programme suivant :

static void Main()
{
   var lst0 = new List<int>(){ 2,3,5,7,11 };
   var lst1 = Transformer(lst0, x => -1.0 * x * x);
   foreach(double x in lst1)
      Console.Write($"{x} ");
   Console.WriteLine();
   foreach(string s in Transformer(new List<string>(){ "j'aime", "mon", "prof" }, s => s.ToUpper() + "!"))
      Console.Write($"{s} ");
   Console.WriteLine();
   List<(bool signe, int val)> lst2 = Transformer(new List<int>() {2, -3, 5, -7, 11}, n => ((Math.Sign(n) < 0), (int)Math.Abs(n)));
   foreach(var p in lst2)
      Console.WriteLine($"{(p.signe? "moins" : "plus")} {p.val}");
}

... affiche ce qui suit :

-4 -9 -25 -49 -121 
J'AIME! MON! PROF!
plus 2
moins 3
plus 5
moins 7
plus 11

EX01 – Solution

C'est plus simple qu'il n'y paraît :

static List<U> Transformer<T,U>(List<T> src, Func<T,U> fct)
{
   var dest = new List<U>();
   foreach (T obj in src)
      dest.Add(fct(obj));
   return dest;
}

L'idée est d'appliquer la fonction à chaque T de la liste source, et de déposer le U résultat dans la liste de destination (transformant ainsi chaque T en un U.

À quoi ça sert au juste?

C'est une fonction extrêmement utile. Quelques cas :

• Prendre une liste de personnes et obtenir une liste de leurs noms
• Prendre une liste de paires (clé, valeur) et obtenir une liste des seules clés
• Prendre une liste de salariés et obtenir une liste de salariés mais avec un salaire accru de 4%
• Prendre une liste de mots et obtenir une liste de longueurs de mots, etc.

EX02 – Énoncé

Écrivez l'algorithme SupprimerDoublons<T>(List<T> src) qui reçoit en paramètre une List<T> préalablement triée (il s'agit d'une précondition de la fonction), et retourne une List<T> contenant les mêmes valeurs que la List<T> originale, mais exempte de doublons, de telle sorte que le programme suivant :

static void Afficher<T>(List<T> lst)
{
   foreach(T obj in lst)
      Console.Write($"{obj} ");
   Console.WriteLine();
}
public static void Main()
{
   Afficher(SupprimerDoublons(new List<int>()));
   Afficher(SupprimerDoublons(new List<int>(){ 2 }));
   Afficher(SupprimerDoublons(new List<int>(){ 2, 2 }));
   Afficher(SupprimerDoublons(new List<int>(){ 2,3,3,3,5,7,11 }));
   Afficher(SupprimerDoublons(new List<int>(){ 2,2,3,5,5,7,11 }));
   Afficher(SupprimerDoublons(new List<int>(){ 2,3,5,7,7,11 }));
   Afficher(SupprimerDoublons(new List<int>(){ 2,3,5,7,11,11 }));
}

... affiche ce qui suit (notez la première ligne qui est vide, car nous avons supprimé les doublons... d'une séquence vide!) :

2 
2 
2 3 5 7 11 
2 3 5 7 11 
2 3 5 7 11 
2 3 5 7 11

EX02 – Solution

Ça peut donner quelque chose comme ceci :

static List<T> SupprimerDoublons<T>(List<T> lst) where T : IComparable
{
   if (lst.Count == 0) return lst; // cas dégénéré
   var résultat = new List<T>();
   résultat.Add(lst[0]); // garanti correct à ce stade
   for (int i = 1; i != lst.Count; ++i)
      if (lst[i].CompareTo(lst[i - 1]) != 0)
         résultat.Add(lst[i]);
   return résultat;
}

Le cas de la liste vide est un cas dégénéré qui est traité séparément du reste. Une fois ce cas traité, le premier élément est conservé d'office, puis tous les éléments subséquents sont examinés. Un élément n'est conservé que s'il est distinct de son prédécesseur (suffisant dû à la précondition à l'effet que la liste en entrée soit triée au préalable). J'ai utilisé l'exigence à l'effet que T soit IComparable pour éviter de passer par le Equals() de object (lent et lourd).

Remarquez que la liste passée en entrée n'est pas modifiée (heureusement!).

À quoi ça sert au juste?

Opérer sur une séquence de valeurs sans doublons est un prérequis pour plusieurs autres algorithmes.

EX03 – Énoncé

Écrivez l'algorithme Cumuler<T,U>(List<T> src, Func<U,T,U> accum, U init) qui reçoit en paramètre une List<T>, une fonction applicable à un U et à un T et retournant un U, de même qu'une valeur initiale de type U, et retourne l'accumulation , de telle sorte que le programme suivant :

public static void Main()
{
   Console.WriteLine($"1+2+3+4+5 == {Cumuler(new List<int>(){1,2,3,4,5}, (x,y) => x+y, 0)}");
   Console.WriteLine($"1*2*3*4*5 == {Cumuler(new List<int>(){1,2,3,4,5}, (x,y) => x*y, 1.0)}");
   Console.WriteLine($"min(2,-3,5,-7,11) == {Cumuler(new List<int>(){2,-3,5,-7,9}, (x,y) => Math.Min(x,y), int.MaxValue)}");
   var mots = new List<string>() { "yo", "man", "genre" };
   Console.Write("La somme des longueurs des mots (");
   foreach (string s in mots)
      Console.Write($"{s} ");
   Console.WriteLine($"\b) est : {Cumuler(mots, (lg, s) => lg + s.Length, 0)}");
}

... affiche ce qui suit :

1+2+3+4+5 == 15
1*2*3*4*5 == 120
min(2,-3,5,-7,11) == -7
La somme des longueurs des mots (yo man genre) est : 10

EX03 – Solution

C'est plus simple qu'il n'y paraît :

static U Cumuler<T,U>(List<T> src, Func<U,T,U> accum, U init)
{
   foreach (T obj in src)
      init = accum(init, obj);
   return init;
}

L'idée est de cumuler (ici, à même la variable init) les résultats d'appels successifs à accum appliquée à ce cumul et aux éléments de src.

À quoi ça sert au juste?

C'est un algorithme extrêmement polyvalent. Outre les cas évidents (somme de valeurs, produit de valeurs), il permet :

• D'identifier le plus mauvais payeur d'une liste de clients
• De repérer la plus haute température enregistrée dans une liste de données météo
• De calculer la somme des points d'une liste de joueurs de hockey, etc.

EX04 – Énoncé

Écrivez la fonction Trouver<T>(List<T> src, T val) qui retournera l'indice de la première occurrence de val dans src, ou -1 si aucune occurrence n'est trouvée.

EX04 – Solution

Simplement exprimé :

static int Trouver<T>(List<T> lst, T val) where T : IComparable
{
   for(int i = 0; i != lst.Count; ++i)
      if (val.CompareTo(lst[i]) == 0)
         return i;
   return -1;
}

Exiger que T soit IComparable évite la lourdeur de passer par object.Equals().

À quoi ça sert au juste?

Trouver la position de la première occurrence d'une valeur dans une séquence est une tâche très, très commune...

EX05 – Énoncé

Écrivez la fonction TrouverSi<T>(List<T> src, Func<T,bool> pred) qui retournera l'indice du premier élément de src satisfaisant le prédicat pred, ou -1 si aucun élément ne satisfaisant pred n'est trouvé.

EX05 – Solution

Simplement exprimé :

static int TrouverSi<T>(List<T> lst, Func<T,bool> pred)
{
   for(int i = 0; i != lst.Count; ++i)
      if (pred(lst[i]))
         return i;
   return -1;
}

Notez que le code est presque identique à celui de Trouver<T>(), plus haut, mais est plus général que ce dernier. Il est donc possible d'exprimer Trouver<T>() en termes de TrouverSi<T>() sans perte de vitesse :

static int Trouver<T>(List<T> lst, T val) where T : IComparable => TrouverSi(lst, x => val.CompareTo(x) == 0);

À quoi ça sert au juste?

Trouver la position de la première occurrence d'une valeur respectant un prédicat dans une séquence est une tâche très, très commune. Pensez à :

• Trouver la position du premier entier pair
• Trouver la position de la première référence nulle
• Trouver la position du premier monstre mort, etc.

EX06 – Énoncé

Écrivez la fonction Filtrer<T>(List<T> src, T val) qui retournera une List<T> contenant les mêmes éléments que src, dans le même ordre, à ceci près que toutes les occurrences de la valeur val en auront été supprimées.

EX06 – Solution

Simplement exprimé :

static List<T> Filtrer(List<T> src, T val) where T : IComparable
{
   var dest = new List<T>();
   foreach(T obj in src)
      if (obj.CompareTo(val) != 0)
         dest.Add(obj);
   return dest;
}

En gros, filtrer les occurrences de val signifie ne conserver que les valeurs qui ne sont pas égales à val.

Remarquez que la liste passée en entrée n'est pas modifiée (heureusement!).

À quoi ça sert au juste?

Éliminer une valeur indésirée d'une séquence de valeurs est une tâche récurrente.

EX07 – Énoncé

Écrivez la fonction FiltrerSi<T>(List<T> src, Func<T,bool> pred) qui retournera une List<T> contenant les mêmes éléments que src, dans le même ordre, à ceci près que tous les éléments respectant le prédicat pred auront été supprimés.

EX07 – Solution

Simplement exprimé :

static List<T> FiltrerSi(List<T> src, Func<T,bool> pred)
{
   var dest = new List<T>();
   foreach(T obj in src)
      if (!pred(obj))
         dest.Add(obj);
   return dest;
}

En gros, filtrer les occurrences satisfaisant pred signifie ne conserver que les valeurs qui ne satisfont pas pred.

Remarquez que la liste passée en entrée n'est pas modifiée (heureusement!).

Notez que le code est presque identique à celui de Filtrer<T>(), plus haut, mais est plus général que ce dernier. Il est donc possible d'exprimer Filtrer<T>() en termes de FiltrerSi<T>() sans perte de vitesse :

static List<T> Filtrer<T>(List<T> lst, T val) where T : IComparable => FiltrerSi(lst, x => val.CompareTo(x) == 0);

À quoi ça sert au juste?

Éliminer une valeur indésirée d'une séquence de valeurs est une tâche récurrente :

• Éliminer toutes les références nulles
• Éliminer tous les entiers négatifs
• Éliminer tous les monstres morts, etc.

EX08 – Énoncé

Écrivez la fonction Concaténer<T>(List<T> lst0, List<T> lst1) qui retournera une List<T> contenant les mêmes éléments que lst0, dans l'ordre, suivis des éléments de lst1, dans l'ordre.

EX08 – Solution

Exprimé simplement :

static List<T> Concaténer<T>(List<T> lst0, List<T> lst1)
{
   var lst = new List<T>();
   for(T obj in lst0) lst.Add(obj);
   for(T obj in lst1) lst.Add(obj);
   return lst;
}

Remarquez que les listes passées en entrée ne sont pas modifiées (heureusement!).

À quoi ça sert au juste?

Concaténer des séquences est une opération fondamentale, et naturelle avec des string. Cette fonction généralise la solution à l'ensemble des List<T>.

EX09 – Énoncé

Écrivez la fonction Remplacer<T>(List<T> src, T pré, T post) qui retournera une List<T> contenant les mêmes éléments que src, dans l'ordre, mais dont chaque occurrence de pré aura été remplacée par post.

EX09 – Solution

Exprimé simplement :

static List<T> Remplacer<T>(List<T> src, T pré, T post) where T : IComparable
{
   var dest = new List<T>();
   foreach(T obj in src)
      dest.Add (obj.CompareTo(pré) == 0? post : obj); // ou utiliser un if ... else
   return dest;
}

Remarquez que la liste passée en entrée n'est pas modifiée (heureusement!).

Les plus astucieuses et les plus astucieux auront remarqué que cette fonction est, en fait, une transformation, et peut s'exprimer comme un appel à Transformer<T,U> :

static List<T> Remplacer<T>(List<T> src, T pré, T post) where T : IComparable
    => Transformer(src, x => x.CompareTo(pré) == 0? post : obj);

À quoi ça sert au juste?

Je suis certain que vous pouvez imaginer des cas où remplacer les occurrences d'une valeur par une autre dans une séquence est chose utile.

EX10 – Énoncé

EX10 – Écrivez la fonction RemplacerSi<T>(List<T> src, Func<T,bool> pred, T post) qui retournera une List<T> contenant les mêmes éléments que src, dans l'ordre, mais dont chaque élément satisfaisant le prédicat pred aura été remplacé par post.

EX10 – Solution

Exprimé simplement :

static List<T> RemplacerSi<T>(List<T> src, Func<T,bool> pred, T post)
{
   var dest = new List<T>();
   foreach(T obj in src)
      dest.Add (pred(obj)? post : obj); // ou utiliser un if ... else
   return dest;
}

Remarquez que la liste passée en entrée n'est pas modifiée (heureusement!).

Les plus astucieuses et les plus astucieux auront remarqué que cette fonction est, en fait, une transformation, et peut s'exprimer comme un appel à Transformer<T,U> :

static List<T> RemplacerSi<T>(List<T> src, Func<T,bool> pred, T post) where T : IComparable
    => Transformer(src, x => pred(x)? post : obj);

Notez que le code est presque identique à celui de Remplacer<T>(), plus haut, mais est plus général que ce dernier. Il est donc possible d'exprimer Remplacer<T>() en termes de RemplacerSi<T>() sans perte de vitesse :

static List<T> Remplacer<T>(List<T> lst, T pré, T post) where T : IComparable => RemplacerSi(lst, x => val.CompareTo(x) == 0, post);

À quoi ça sert au juste?

Je suis certain que vous pouvez imaginer des cas où remplacer les occurrences d'une valeur par une autre dans une séquence est chose utile.