Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Rust permet de passer en paramètre à une fonction le type de la valeur passée en argument ; une telle fonction se nomme une fonction générique.

Pour illustrer cette possibilité nous allons écrire un programme de tri selon l’algorithme de tri par insertion, et montrer qu’il peut trier aussi bien des listes de nombres que des listes de caractères, ou des listes de chaînes de caractères. Précisons que les listes de Rust sont en fait plutôt des vecteurs, et que les prédicats de comparaison qui s’appliquent aux nombres s’appliquent aussi aux caractères :

  1. fn main() {
  2.     let mut liste_de_nombres = vec![34, 50, 25, 100, 65];
  3.     let resultat = tri_insertion(&mut liste_de_nombres);
  4.     println!("La liste de nombres triée est {:?}", resultat);
  5.  
  6.     let mut liste_de_caracteres = vec!['y', 'm', 'a', 'q'];
  7.     let resultat = tri_insertion(&mut liste_de_caracteres);
  8.     println!("La liste de caractères triée est {:?}", resultat);
  9.  
  10.     let mut liste_de_chaines = vec!["Xen", "Alia", "Zorro", "Nur"];
  11.     let resultat = tri_insertion(&mut liste_de_chaines);
  12.     println!("La liste de chaînes triée est {:?}", resultat);
  13.  
  14.     let mut liste_un = vec![1];
  15.     let resultat = tri_insertion(&mut liste_un);
  16.     println!("La liste de un caractère triée est {:?}", resultat);
  17.  
  18.     let mut liste_zero : Vec<i32> = vec![];
  19.     let resultat = tri_insertion(&mut liste_zero);
  20.     println!("La liste de zéro caractère triée est {:?}", resultat);
  21. }
  22.  
  23. fn tri_insertion<T: Clone + std::cmp::PartialOrd>(liste: &mut [T])
  24.                                                   -> &[T] {
  25.     if liste.len() < 2 {return liste};
  26.     for i in 1..liste.len() {
  27.         let mut j = 0;
  28.         while j < i && &liste[j] < &liste[i] {
  29.             j += 1;
  30.         }
  31.         let mut k = i;
  32.         let s = liste[i].clone();
  33.         while k > j {
  34.             liste[k] = liste[k - 1].clone();
  35.             k -= 1;
  36.         }
  37.         liste[j] = s;
  38.     }
  39.     liste
  40. }

Télécharger

La déclaration de la fonction tri_insertion indique qu’elle est générique en fonction du type T. Cette fonction attend comme argument une référence à un vecteur modifiable d’objets de type T, et renvoie un résultat de même type.

Dans le corps de la fonction, pour trier la liste, nous devrons en comparer les éléments entre eux, ce qui impose une restriction sur le type T : il faut que la comparaison ait un sens pour les éléments du type, ce que nous indiquons par la mention std::cmp::PartialOrd, ce qui limite T aux types pour lesquels existe une implémentation de cette crate (Cargo nous a aimablement indiqué la mention à ajouter à notre code, ici comme pour la restriction suivante).

Nous devrons aussi permuter certains éléments de la liste, en affectant la valeur d’un élément de la liste à la position d’un autre élément, or cela pose des problèmes de possession, parce que, comme le dit le message d’erreur, move occurs because `liste[_]` has type `T`, which does not implement the `Copy` trait. Qu’à cela ne tienne, nous créerons une copie de l’élément à déplacer par la méthode clone(), ce qui impose une restriction supplémentaire au type T : qu’il existe une implémentation de clone() pour ses éléments, ce que l’on indique par la mention Clone dans la déclaration, qui s’écrit donc désormais :

  1. fn tri_insertion<T: Clone + std::cmp::PartialOrd>

Le reste de la fonction est l’implémentation classique de l’algorithme, qui donne les résultats suivants :

  1. $ cargo run
  2.    Compiling tri_insertion v0.1.0 (.../Tri/tri_insertion)
  3.     Finished dev [unoptimized + debuginfo] target(s) in 0.85s
  4.      Running `target/debug/tri_insertion`
  5. La liste de nombres triée est [25, 34, 50, 65, 100]
  6. La liste de caractères triée est ['a', 'm', 'q', 'y']
  7. La liste de chaînes triée est ["Alia", "Nur", "Xen", "Zorro"]
  8. La liste de un caractère triée est [1]
  9. La liste de zéro caractère triée est []

Télécharger

On observe que les temps de compilation sont assez longs : le compilateur Rust vérifie beaucoup de choses, ce qui impose au programmeur un travail conséquent pour satisfaire ses exigences. La rétribution de ces efforts consiste en ceci qu’une fois accepté par le compilateur, le programme a toutes les chances d’être rapide et, de surcroît, juste, en évitant la plupart des vérifications et des erreurs à l’exécution. C’est en ceci que Rust ressemble à Ada.