Bonchour,

Sur le site officiel de Haskell il y a ce code

primes = filterPrime [2..] 
  where filterPrime (p:xs) = 
          p : filterPrime [x | x <- xs, x `mod` p /= 0]

Et j'ai une idée de comment il marche, mais j'aimerais quand même beaucoup que quelqu'un m'explique exactement son fonctionnement.

Merci.

Alors alors...

[2..] crée une liste infinie d'entiers, avec un pas de 1, en partant de 2 (inclu). Comme presque tout en Haskell est fainéant par défaut, les éléments de la liste ne sont pas évalués tant qu'on en a pas besoin, donc c'est juste un "glaçon" en mémoire qui contient le potentiel d'une liste infinie d'entiers.

Du coup, filterPrime [2..] appelle la fonction filterPrime avec cette liste. On déduit donc que filterPrime est de type [a] -> ? pour le moment.

filterPrime est d'ailleurs locale à primes, donc on en fait la définition dans le where. Là, on dit qu'elle prend une liste en argument, et on effectue une déconstruction par pattern matching sur cette liste. (p:xs) dit "on prends le premier élément de la liste et on le stocke dans 'p', et on prends le reste (peu importe la taille, mais au moins 1) pour le mettre dans 'xs'".

Le coeur de la fonction est ensuite récursif. On construis une liste en ajoutant 'p' au début, puis on ajoute d'autres éléments avec l'opérateur :. Note que l'opérateur ':' a pour type a -> [a] -> [a] : il prend un élément et une liste de ce même type d'élément, et retourne la liste avec cet élément en tête. Comme 'p' est un entier (au premier tour, il sera égal à 2), on déduis par la suite que filterPrime renvoit [Integer]. On a assez d'infos pour avoir la signature de type de filterPrimes, qui est [Integer] -> [Integer], et donc de primes, qui est [Integer].
Reprenons à l'opérateur ':' ; on ajoute donc 'p' à une liste construite par l'appel à filterPrime, mais cette fois on filtre la liste qu'on renvoit. On utilise une liste en compréhension, qui dit "construis-moi une liste d'entiers à partir de tous les entiers restants dans ma liste d'origine (xs), sauf que tu me gardes que les entiers qui sont pas divisibles par la tête de liste de ma liste d'origine (p)".
C'est efficace, parce que si des nombres dans la liste xs sont divisibles par p, ça veut dire que ce sont des multiples de p. Sachant que p >= 2, s'ils sont divisibles par ce p, c'est qu'ils ne sont pas uniquement divisibles par eux-même, et qu'ils ne sont donc pas premiers : on s'en débarrasse. Au tour suivant, le nombre 'p' est égal au plus petit nombre non multiple du précédent 'p', et on recommence.
Et on recommence, et on a une jolie liste infinie de nombres premiers.

En pratique c'est un code clair et concis, mais pas très optimisé. Y'a moyen d'accélérer le tout avec de très simples assertions.

[EDIT : devancé... de 3h j'ai été distrait par des animaux en ballons à là moitié du message]

Alors déjà un détail : c'est un exemple "jouet", dans le sens où il est concis, élégant et utile pour expliquer les concepts qu'il y a derrière, mais il ne faut pas l'utiliser tel quel si tu veux vraiment manipuler des nombres premiers : c'est très inefficace.

Ensuite, il y a deux niveaux de compréhension de ce code.
- Il y a plusieurs abstractions mathématiques en jeu, si tu comprends bien ce qu'elles veulent dire, tu dois pouvoir comprendre ce que fait le code, pourquoi ça marche, et être capable de réutiliser tout ça dans d'autres cas sans problèmes. C'est la compréhension "haut niveau", c'est suffisant pour écrire du code qui marche, c'est fait pour te simplifier la vie.
- D'autre part, tu peux te demander comment le programme fait ça exactement, qu'est-ce qu'il se passe sous le tapis. Ça te permet de mieux évaluer la complexité de ton programme, le temps que ça va mettre à s'exécuter. C'est la compréhension "bas niveau", moins joli à voir. Normalement ce n'est pas ça qu'il faut avoir en tête lorsque tu écris des programmes, il vaut mieux se laisser guider par les abstractions et laisser la magie s'opérer. Mais parfois, on ne peut pas y échapper et il faut ouvrir le capot.

Le haut niveau :

J'imagine que tu as à peu près compris comment ça marche : c'est très proche de la méthode du crible d’Ératosthène (si tu ne connais pas : https://fr.wikipedia.org/wiki/Crible_d'%C3%89ratosth%C3%A8ne regarde l'animation, ça explique bien).

- [2..], ça désigne la liste infinie de tous les entiers en partant de 2 : [2, 3, 4, 5, 6, 7, ...]. On ne se demande pas pour l'instant comment l'ordinateur peut gérer des listes infinies, on est dans l'explication abstraite. Tout ce qui nous intéresse, c'est que ça se comporte comme si on manipulait vraiment une liste infinie.

- [x | x <- xs, x `mod` p /= 0], c'est comme en mathématiques ce qu'on écrirait "{x ∈ xs | x mod p ≠ 0}", avec la notation ensembliste. C'est la liste obtenue à partir de la liste xs, en ne gardant que les éléments x tels que x mod p ≠ 0 (donc, les éléments qui ne sont pas multiples de p).

Donc primes va être obtenu en donnant cette liste infinie en argument à la fonction filterPrime. Que fait donc cette fonction ?
En fait on définit uniquement filterPrime (p:xs), c'est à dire qu'on spécifie juste ce qu'elle fait sur une liste de la forme (p:xs). En effet vu qu'on va manipuler des listes infinies, on se fiche de ce qu'il se passe sur la liste vide, notre liste ne sera jamais vide.
Donc quand on a une liste (p:xs) en entrée, on va renvoyer une liste dont la tête est "p", et la queue de la liste est filterPrime [x | x <- xs, x `mod` p /= 0]. On prend donc le premier élément "p" de notre liste, on retire tous les multiples de p qui apparaissent dans le reste de la liste, et on rappelle récursivement la fonction filterPrime sur la nouvelle liste ainsi obtenue.
C'est grosso modo ce que fait l'algorithme du crible d’Ératosthène : on commence avec un grand tableau qui contient tous les nombres à partir de 2, puis on répète "prendre le premier élément du tableau, et barrer tous ses multiples".

Au final, primes est une liste infinie qui contient tous les nombres premiers.

Bas niveau :

Maintenant, j'imagine que ta question portait surtout sur "que fait l'ordinateur quand il exécute ce code ?".

La principale difficulté, c'est la manipulation de listes infinies. Bien entendu, l'ordinateur ayant une mémoire finie, on ne peut stocker que des structures de données finies : listes, piles, tableau, arbres, graphes...
En fait, on sait aussi dans une certaine mesure manipuler des structures de données infinies : ici, l'exemple des listes infinies, mais on pourrait aussi avoir des arbres infinis, etc.

[Si ce paragraphe est du charabia, saute le]
Je ne sais pas si tu connais le principe d'''induction'', c'est ainsi qu'on définit des structures comme les listes, les arbres, les entiers naturels... Par exemple l'ensemble des listes d'éléments de A est le plus ''petit'' ensemble X qui contient nil, et qui contient cons a x pour chaque a ∈ A et x ∈ X. On appelle ça une définition inductive, nil et cons sont appelés des ''constructeurs''. On a défini les listes en disant comment on peut ''construire'' une liste : soit c'est la liste vide, soit on l'obtient en rajoutant un élément "a" à une autre liste déjà construite.
Au contraire, les structures de données infinies sont définie par ''coinduction''. Par exemple, l'ensemble des listes infinies d'éléments de A est défini comme le plus ''grand'' ensemble X tel que pour tout élément x ∈ X, on puisse calculer head x ∈ A et tail x ∈ X. Ici, head et tail sont des ''destructeurs''. On a donc défini les listes infinies en précisant comment on peut observer / utiliser ces listes, en les détruisant en une tête, et une queue.

Comment on se débrouille en Haskell pour manipuler des données infinies ?
A l'aide de ce qu'on appelle l'évaluation paresseuse ("lazy"). L'idée, c'est qu'on ne calcule pas tout de suite les choses, on garde en mémoire quels sont les calculs qui restent à faire, et on ne les effectue que lorsqu'on en a besoin.
Par exemple une liste infinie ne peut pas être stockée en entier en mémoire. A la place, on se retient juste la façon d'en calculer la tête, et la façon d'en calculer la queue. Par exemple, [2..] peut être définie à partir d'une fonction listFrom n qui donne la liste infinie des entiers à partir de n :

 listFrom n =
    n : listFrom (n+1)

Donc la tête de liste c'est n, et la queue c'est une boite noire listFrom (n+1) qu'on n'évaluera que lorsqu'on en aura besoin.

Si on reprend ton code :

primes = filterPrime [2..] 
  where filterPrime (p:xs) = 
          p : filterPrime [x | x <- xs, x `mod` p /= 0]

Quand tu définis primes, rien n'est calculé : on garde juste en mémoire les calculs qu'il faudra faire lorsqu'on voudra s'en servir.
Si on veut la tête de la liste, ça va regarder la tête de [2..] qui est donc 2, et renvoyer 2.
Si on veut l'élément suivant, ça va commencer à faire des calculs : on calcule la queue de [2..] ("xs" dans le code) qui va être [3..], après quoi il va falloir commencer à retirer les éléments qui sont multiples de 2, et réappliquer filterPrime sur le résultat. Bien sur, on n'effectue aucun de ces calculs en entier : on ne les fait que jusqu'à avoir trouvé le prochain élément, et on s'arrête.

Du coup, imaginons qu'on arrive au sixième élément de la liste, qui est 29, on aura empilé tout plein de calculs à faire pour trouver le suivant : d'abord on ajoute 1 (le "listFrom") on obtient 30, on vérifie qu'il ne soit pas multiple de 2 (ça rate, on passe au suivant), on ajoute 1 ("listFrom") on obtient 31, on vérifie qu'il ne soit pas multiple de 2 (ça passe), on vérifie qu'il ne soit pas multiple de 3 (ça passe), puis de 5, puis de 7, 11, 13, 19, 23, 29, et là on annonce enfin fièrement que l'élément suivant de la liste est 31.

Du coup, on a un truc qui ressemble à une liste, mais en fait dès qu'on fait des appels à "head" et "tail" dessus, ça fait tout plein de calculs pour pouvoir renvoyer un résultat. Et plus on avance dans la liste, plus on se accumule de calculs "restant à faire".

Une remarque qu'on peut faire, c'est que c'est beaucoup moins efficace que le crible d’Ératosthène implémenté de manière classique. Normalement, quand on arrive à "17", on barre tous les multiples de 17 : 17, 34, 51, 68... plus on avance et plus on fait de grands pas. Ici, on va regarder tous les nombres qui suivent et faire à chaque fois une division pour tester si c'est un multiple de 17 : c'est franchement inefficace, d'une part parce que les divisions c'est plus lourd que les additions, mais surtout parce qu'on va faire beaucoup plus de tests que nécessaire.

D'accord merci beaucoup. Je voulais bien avoir les 2 versions. Je suis un débutant en Haskell (mais pas un débutant complet, j'ai lu Learn you a haskell for great good et quelque tutoriel). Je suis capable de résoudre des problèmes mathématiques simple, mais pas toujours de manière idiomatique (Exemple projet Euler) et quand je regarde des solutions idiomatiques certaine partit me semble un peu obscur. Tu as des conseils pour comprendre un bout de code dont je en suis pas sûr du fonctionnement?

En tous, cas merci beaucoup!

Si tu cherches un autre débutant pour explorer Haskell et la programmation fonctionnelle en général je suis là.