Discussion du code iterateurs

Concepts

Les concepts abordés dans cet exemple sont:

• Discussion du code iterateurs
  • Concepts
  • Documentation
  • Discussion
    • Le trait itérateur
    • Les fonctions iter et collect
    • Quelques fonctions d'ordre supérieur sur les itérateurs
    • Performances et lazy evaluation
  • Rustlings
    • Les itérateurs

Documentation

Afin de compléter ce cours, je vous recommande la lecture des ressources suivantes :

• Traitements des collections avec de itérateurs en Rust
• Le trait Iterator en Rust
• Les méthodes du trait Iterator

Discussion

Le trait itérateur

L'itérateur est un patron de conception extrêment répandu en prorgrammation orientée objet. On le retrouve dans plusieurs langages comme par exemple python.

Le trait Iterator est défini ainsi en version simplifiée dans la documentation :

#![allow(unused)]
fn main() {
trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}
}

Un itérateur possède donc un élément courant et une méthode next() qui permet de passer à l'élément suivant, puis de retourner l'élément courant. Un itérateur peut-être fini ou infini. Il peut permettre par exemple de parcourir une collection ou de créer un compteur.

La documentation Rust offre un exemple d'implémentation d'itérateur assez accessible.

Les fonctions iter et collect

Le Rust propose des méthodes permettant de passer d'une collection à un itérateur assez facilement.

fn main(){
    let v : Vec<i32> = vec![1,2,3,4];
    let mut v_iter = v.iter();

    println!("{}", v_iter.next().unwrap());
    println!("{}", v_iter.next().unwrap());
    println!("{}", v_iter.next().unwrap());
    println!("{}", v_iter.next().unwrap());
    assert!(v_iter.next().is_none());
}

La méthode iter() des vecteurs permet de créer un itérateur à partir d'un vecteur. Il faut noter que v_iter est mutable, car son état interne est modifié par l'appel à la méthode next(). En effet, pour pouvoir avancer dans notre itérateur, nous utilisons la fonction next() qui avance l'élément courant d'une position et retourne une Option sur l'élément courant. Pour rappel, la signature de la méthode de next() est fn next(&mut self) -> Option<Self::Item>;.

Il est aussi possible de transformer un itérateur en collection à l'aide de la méthode collect(). La fonction from_fn() permet de créer un itérateur à l'aide d'une fonction :

fn main(){
  let mut count = 0;
  let even_counter = std::iter::from_fn(|| {
    count += 2;
    Some(count)
  });

  let v : Vec<i32> = even_counter.take(3).collect();
  println!("Les 3 premiers nombres paires sont {}, {}, {}", v[0], v[1], v[2])
}

Le code ci-dessus commence par créer un itérateur infini de nombres paires. Nous verrons plus-tard que les éléments de l'itérateur infini n'est pas généré immédiatement dans la section lazy-evaluation. Nous utilisons une variable mutable count, afin de générer les valeurs de notre itérateur. Notre closure va capturer cette variable et l'incrémenter de 2 à chaque appel et retourner la valeur courante encapsulée dans une Option.

Notre itérateur étant infini, nous devons le limiter à un nombre fini d'éléments avant de pouvoir récupérer une collection. Pour cela nous utilisons la méthode take() qui permet de limiter la taille de notre itérateur. Finalement, nous pouvons récupérer un vecteur d'entier à l'aide de la méthode collect().

Quelques fonctions d'ordre supérieur sur les itérateurs

L'intérêt principal des itérateurs en Rust réside dans ses fonctions d'ordre supérieur. Elle permettent de traiter des collections de manière efficaces en apportant des garanties notament en terme de concurrence. On retrouve notament le crate Rayon-rs qui permet d'effectuer des traitement en parallèle sans apporter de modifications majeures au code.

Ici, nous nous concentrerons sur les méthodes suivantes qui sont très communes dans les langages fonctionnels (pas toujours avec les mêmes noms) :

• map()
• filter()
• fold()
• zip()

Reprenons notre code de recherche du minimum d'une liste :

pub fn find_minimum(v: &Vec<i32>) -> Option<i32> {
    v.iter().fold(None, |acc, current| {
        let next_acc = if let Some(val) = acc {
            if val <= *current {
                val
            } else {
                *current
            }
        } else {
            *current
        };
        Some(next_acc)
    })
}

Notre fonction prend en argument un vecteur v que nous transformons en itérateur avec la méthode iter(). Pour trouver le minimum de notre itérateur, nous utilisons la méthode fold(). Cette méthode permet de réduire un itérateur en appliquant itérativement, une fonction qui prend deux arguments et qui retourne un seul élément. On se retrouve donc avec une seule valeur à la fin de la réduction.

La méthode fold() prend donc deux arguments. Le premier est la valeur d'initialisation de notre réduction. On parle parfois d'élément neutre, mais ce terme est plus restrictif qu'une simple valeur initiale.

L'élément neutre d'une opération est l'élément N qui si on lui applique l'opération avec n'importe quel autre élément x retourne cet élément x. Si nous prenons l'exemple de l'addition, l'élément neutre est 0, car : $$ 0 + x = x + 0 = x $$ et ce peu importe la valeur de x. Il est préférable d'utiliser un élément neutre, plutôt qu'une valeur quelconque pour l'initialisation de notre réduction. Sans rentrer dans les détails, qui dépassent le cadre de ce cours, les algoritmes parallèles de réduction reposent sur l'usage d'un élément neutre. Utiliser un élément neutre, vous permettra donc de parallèliser votre code bien plus simplement.

En l'occurence puisqu'on veut retourner une option, notre élément neutre est None.

Le deuxième argument de notre fonction fold() est l'opération de réduction que nous utiliserons pour trouver le minimum. Pour cela nous utilisons une closure. Cette dernière prend deux argument, un accumulateur (la valeur courante de la réduction) de type Option<i32> et un l'élément courant de l'itérateur qui est de type &i32. Notre closure va simplement retourner une Option contenant l'élément le plus petit entre la valeur actuelle de l'accumulateur et la valeur courante. Cette valeur devient la nouvelle valeur de l'accumulateur pour l'appel suivant.

Le résultat de la méthode fold() est la dernière valeur de l'accumulateur. Si l'itérateur est vide, la méthode fold() retournera la valeur d'initialisation. Dans notre cas, il s'agit d'une Option vide.

Pour illustrer l'usage de la méthode filter(), nous avons une fonction qui trouve le plus petit nombre pair dans un vecteur :

pub fn find_even_minimum(v: &Vec<i32>) -> Option<i32> {
    v.iter().filter(|i| *i % 2 == 0).fold(None, |acc, current| {
        let next_acc = if let Some(val) = acc {
            if val <= *current {
                val
            } else {
                *current
            }
        } else {
            *current
        };
        Some(next_acc)
    })
}

La méthode est similaire à la recherche du minimum, mais afin de garder uniquement les nombres pairs on ajoute la fonction filter(). Quand on ajoute ainsi une série de traitements à la suite, on parle de pipelines.

La fonction filter() prend une fonction en paramètre appelée prédicat. Un prédicat et une fonction qui prend un élément et retourne un booléen. Cette fonction va déterminer quels éléments conserver. Ici nous utilisons une closure qui retourne true si le nombre est pair. La méthode filter() va retourner un nouvel itérateur composé uniquement des éléments séléctionnés par le prédicat.

Pour finir, on recherche la valeur minimum de ce nouvel itérateur, de la même façon que dans l'exemple précédent, à l'aide de la méthode fold().

Essayons maintenant de résoudre un problème un peu plus complexe en ajoutant les méthodes zip() et map(). Nous aimerions trouver quel est l'élément le plus petit en valeur absolue d'un vecteur donné.

pub fn find_absolute_minimum(v: &Vec<i32>) -> Option<i32> {
    let signs = v.iter().map(|i| i.signum());
    let abs_values = v.iter().map(|i| i.abs());
    signs
        .zip(abs_values)
        .fold(None, |acc, (c_sign, c_abs_v)| {
            let next_acc = if let Some((sign, abs_v)) = acc {
                if abs_v <= c_abs_v {
                    (sign, abs_v)
                } else {
                    (c_sign, c_abs_v)
                }
            } else {
                (c_sign, c_abs_v)
            };
            Some(next_acc)
        })
        .map(|(sign, abs_v)| sign * abs_v)
}

La première étape consiste à créer deux itérateurs. Le premier contient le signe de chaque élément et le deuxième, la valeur absolue de chaque élément.

    let signs = v.iter().map(|i| i.signum());
    let abs_values = v.iter().map(|i| i.abs());

Pour obtenir ces itérateurs, nous allons transformer nos itérateurs obtenus avec iter() en utilsant la fonction map(). Cette méthode permet d'appliquer une même transformation sur tous les éléments d'un itérateur. Pour l'itérateur signs, on appelle la méthode signum() des i32, qui retourne 1 si le nombre est positif, 0 si le nombre est 0 et -1 si le nombre est négatif. Pour abs_values, nous utilisons la méthode abs() des i32, qui retourne la valeur absolue d'un nombre.

    signs
        .zip(abs_values)

Maintenant que nous avons nos deux itérateurs, nous aimerions pouvoir itérer sur les deux simultanément. Pour cela, nous pouvons utiliser la méthode zip(). Elle permet de transformer deux itérateurs, en un unique itérateur de tuple. Ici nous avons deux itérateurs de i32, qui deviennent donc un seul itérateur de type tuple (i32, i32).

        .fold(None, |acc, (c_sign, c_abs_v)| {
            let next_acc = if let Some((sign, abs_v)) = acc {
                if abs_v <= c_abs_v {
                    (sign, abs_v)
                } else {
                    (c_sign, c_abs_v)
                }
            } else {
                (c_sign, c_abs_v)
            };
            Some(next_acc)
        })

Ensuite avec fold(), il nous suffit de comparer les valeurs absolues et de retourner une option contenant le signe et la valeur absolue.

        .map(|(sign, abs_v)| sign * abs_v)

Pour finir, on utilise la méthode map() de notre Option<(i32,i32)> pour multiplier la valeur absolue par le signe. Ce qui nous donne au final une Option<i32> contenant notre résultat.

Performances et lazy evaluation

Les transformations sur les itérateurs sont en général aussi perfomantes qu'une simple boucle for. On peut voir par exemple ce benchmark dans le livre Rust. Si on ajoute la possibilité de parallèliser facilement un code basé sur les itérateurs, leur intérêt paraît évident.

Un des éléments qui explique les perfomances des itérateurs réside dans la lazy evaluation. Lorsqu'on appelle une opération de transformation sur un itérateur, la transformation n'est pas réalisée directement. C'est uniquement lorsqu'on appelle une fonction dite terminale, comme par exemple fold() ou collect() qui doivent produire un résulat. Les transformations intermédiaires peuvent ainsi souvent être fusionnés.

Ce qui veut dire par exemple que dans le code suivant,

fn main() {
  let v = vec![0,1,2,3,4,5];
  let it = v.iter().map(|x| x + 1).map(|x| x * 3).filter(|x| x % 2 == 1);
  let res : Vec<i32> = it.collect();
}

que tant que la fonction collect() n'a pas été appelée, alors aucune transformation n'est effectuée. Si vous ne nous croyez pas, un moyen simple de vous en convaincre, consiste à appliquer une série de transformation sur un itérateur infini et de mesurer la performance.

Rustlings

Les rustlings à faire dans ce chapitre sont les suivants:

Les itérateurs

$ rustlings run iterators1
$ rustlings run iterators2
$ rustlings run iterators3
$ rustlings run iterators4
$ rustlings run iterators5