Forum de mathématiques - Bibm@th.net

Je viens de me rendre compte que je me suis foiré sur la fin de mon dernier message x'). Je viens donc de le compléter !

Étant donné que @yoshi ne semble pas avoir été en mesure de remettre ma solution, la revoici, toujours en Haskell

a) Comme déjà indiqué la première fois, cette solution n'est pas optimale mais répond à la question de construire nous même l'algorithme.

b)

Pourquoi ? Je t'ai dis que tu sembles pouvoir installer le paquet ghc.

Juste avant de partir en cours, j'ai refait le benchmark avec arithmoi… résultat : 18 ms en moyenne pour générer la liste des premiers qui nous intéressent ! 15 fois plus rapide que la version naïve et 2 fois plus rapide que la version Python et sans autre tips and tricks.

Sur ce, je vais en cours !

Je sais...

Ce n'est pas ce que j'ai fais.

T'as rien lu enfaite ?

Comme indiqué, j'ai cherché ici à convertir ce qui est déjà fait en Python. C'est justement parce que je ne vais pas m'amuser à refaire expressément chaque étape entre $\sqrt{n}$ et $\sqrt{2\times n}$, que je détaille le plus possible ce qu'il se passe pour que tu puisses ensuite t'amuser à modifier des trucs comme tu le veux sans l'aide de personne.

Tout vient à point à qui sait attendre.

Partie A : un monde à découvrir

Un langage de programmation tout en un

Le langage de programmation Haskell est en quelque sorte une plateforme toute en un. Une fois celui-ci installé, nous retrouverons sur notre ordinateur les quelques outils suivants :

• GHC : The Glasgow Haskell Compiler ;

• GHCi : L'interpreteur interactif ;

• Les paquets Haskell les plus utiles ;

• Un gestionnaire de projet.

Pour installer Haskell, deux options s'offrent à vous, le télécharger depuis le site du projet ou l'installer depuis le gestionnaire de paquet de votre système d'exploitation préféré :

Pour s'assurer que tout fonctionne, demandons à ghc, le compilateur d'Haskell, de nous afficher son numéro de version. Ceci se réalise à l'aide de la commande qui suit :

Le numéro de version pouvant évidemment varier selon votre installation.

Étant donné qu'à ce stade tout devrait fonctionner, créons d’emblée notre premier programme : le bien connu "hello, world!". Pour ce faire, ouvrons notre éditeur de texte préféré afin d'y écrire le code suivant :

que nous allons enregistrer dans un fichier main.hs.

Afin d’exécuter ce programme, nous allons devoir le compiler. La compilation consiste à transformer un programme textuel adapté à la compréhension des humains, du moins ceux formés pour ça, en un programme exécutable composé de 0 et de 1, adapté à la compréhension de l'ordinateur afin que ce dernier sache quelles opérations utiliser pour réaliser les tâches qui lui sont demandées.
Pour ce faire, ouvrez votre terminal et placez-vous dans le dossier contenant le fichier main.hs que vous venez de créer. Lorsque vous y êtes, lancez la commande suivante

Bravo ! Vous venez d'obtenir votre premier programme en Haskell ! Vous voyez, ce n'était pas bien difficile ! À présent, il ne nous reste plus qu'à l'exécuter. Pour ce faire, tout en restant dans le même dossier, lancez la commande suivante :

Il nous est déjà possible de remarquer deux trois faits intéressants.

• La ligne

  -- Mon premier programme

  n'a pas été exécuté. Ceci est dû au fait que -- est la marque démarrant un commentaire qui sera ignoré par le compilateur.

• Comme en C, C++, Java, Rust, ou encore Python, la fonction main est le point d'entré disant au compilateur où démarrer le programme.

• La fonction print affiche les guillemets autour de notre chaine de caractères. Nous expliquerons ce dernier fait plus loin.

Vous vous demandez peut-être s'il est possible de demander au compilateur d'enregistrer l'exécutable dans un fichier au nom spécifique. Sachez que c'est effectivement possible avec -o. Pour ce faire, procédez ainsi :

Vous pouvez alors exécuter le programme comme suit :

Intéressons-nous à présent au deuxième outil que nous utiliserons dans ce premier post : ghci. Comme indiqué dans l'introduction, ghci est un interpréteur intéractif, c'est-à-dire qu'il exécutera chacune de nos lignes de code au fur et à mesure que nous lui donnerons. Pour lancer ghci rien de plus simple :

Comme pour n'importe quel interpréteur, nous pouvons donc donner du code à ghci afin qu'il l'exécute. Voici quelques exemples :

Comme nous pouvons le voir, ghci exécute nos lignes de codes sans se poser de question tant que celles-ci sont valides et font sens pour lui. Les deux premiers exemples montrent qu'il est possible d'ajouter ou omettre les espaces non significatifs. Le troisième exemple montre un fait surprenant pour une personne venant d'un autre langage de programmation. Haskell est capable de gérer de nombres extrêmement grands ! En effet, nous pouvons même aller plus loin, par exemple :

Bien évidement, vous pouvez mettre le nombre arbitrairement élevé de votre choix. En réalité, là où d'autres langages de programmation considèrent les nombres comme étant des entités vivantes dans un espace délimité en mémoire, int8 pour des entiers sur 8 bits, int16 pour des entiers sur 16 bits, int32 pour des entiers sur 32 bits, etc… Haskell, dispose d'une entité Integer qui se rapproche de la définition mathématique de nombre entier : n'importe quelle suite de chiffre de n'importe quelle longueur. Nous expliquerons dans le prochain post les différences avec les entiers que l'on retrouve dans d'autres langages de programmation.

Bien entendu, ghci gère les variables et les fonctions où, à nouveau, il est possible d'ajouter ou omettre des espaces non significatifs.

ghci est de plus un formidable outil en mesure d'importer les fonctions de vos fichiers afin de les utiliser. Pour ce faire rendez-vous dans le dossier contenant un de vos fichiers Haskell. Nous supposerons ici que nous voulons importer le fichier main.hs. Lancez alors ghci et effectuez les manipulations suivantes

Maintenant que tout a été chargé, il est possible d'exécuter la fonction main que nous avons écrite plus tôt

Petit exercice : Modifier la fonction main dans main.hs de sorte que vous puissiez afficher "Bonjour [votre pseudo]" dans ghci.
Comme nous ne savons toujours pas composer des chaines de caractères avec des variables, nous devons nous contenter d'écrire une fonction à usage unique :

puis nous chargeons et lançons le tout dans ghci

Finalement, pour quitter ghci, tapez ce qui suit

Les bases de la programmation fonctionnelle et d'Haskell

Nous savons à présent utiliser les outils de base d'Haskell, il est donc grand temps d'apprendre à programmer avec celui-ci. Toute fois, avant de s’aventurer plus loin, il va nous falloir nous poser une question primordiale : qu'est-ce qu'une application ?

Si vous avez fait quelques maths, vous savez connaissez alors la définition suivante:

qu'il est possible réécrire de manière plus digeste comme cela :

Mais alors pourquoi parler d'application ? Cela est dû au fait que la programmation fonctionnelle fait en réalité plus référence à ce qu'on appelle application en français. Ainsi, les langages de programmations fonctionnels et a fortiori Haskell, suivent tous cette définition que l'on peut aussi désigner à l'aide des règles suivantes :

• Toute application doit prendre un argument ;

• Toute application doit retourner une valeur ;

• Toute valeur retournée par une application doit être unique.

Cette dernière règle est connue sous le doux nom de principe de transparence référentielle.

Néanmoins, afin de ne pas être trop perdu avec les différentes ressources disponibles,
admettons à présent que le mot fonction correspond à une application.

Commençons avec l'exemple le plus simple qui soit, la fonction identité. Pour ce faire, lancez ghci et entrez le code suivant :

Cette fonction identity accepte un argument x et nous le retourne sans rien y faire.

Nous remarquons ici une des premières forces du langage Haskell : l'inférence de types. En effet, comme nous pouvons le voir, il nous est possible de donner à la fonction identity n'importe quel argument, qu'il soit un nombre, une chaine de caractères ou encore une liste. Le compilateur sera en mesure de déterminer le bon type à appliquer le moment venu sans que l'on ait besoin de l'expliciter nous-même.

Dirigeons nous à présent vers l'utilisation de variables. Pour cela, écrivons les lignes suivantes dans le fichier main.hs :

que nous compilons ensuite de la manière suivante :

Horreur, cela ne compile pas ! Au vue de ce que l'on sait déjà, saurez-vous expliquer pourquoi ?
Il faut savoir que les variables en Haskell ne sont en rien… variable ! Si celles-ci l'étaient, cela violerait le principe d'unicité. Visualisez donc une variable Haskell comme une définition d'une valeur donnée. Un peu comme on définit $\pi = 3.1415...$. Il ne viendrait à l'idée de personne de modifier la valeur de $\pi$. C'est en quelque sorte ce qu'il se passe en Haskell.

Petite note subsidiaire:
Comme il est assez pénible de relancer l'interpréteur ghci
à chaque fois que l'on veut faire des testes quelconques,
celui-ci permet de redéfinir les variables.
Ainsi, le code précédent fonctionne dans ghci.

À la conquête des nombres premiers !

Mettons à présent à profit tout ce que nous avons vu plus haut afin de générer la liste des nombres premiers jusqu'à $\lfloor\sqrt{2\times n}\rfloor$.

Premièrement, commençons par mettre à profit le côté lazy d'Haskell afin de ne pas nous soucier des ressources. Ainsi donc, créons une liste infinie de nombre premier.

Afin de tester ce bout de code, il nous faut charger le fichier dans ghci et lancer appeler la fonction. Pour ce faire, enregistrez le code précédant dans un fichier primes.hs puis lancez ghci. Une fois ceci fait, charger le contenu de ce fichier primes.hs dans ghci de la manière suivante :

Mais que se passe-t-il ? Pourquoi une erreur s'affiche-t-elle ? Eh bien cela est dû au fait que notre fonction sieve s'attend à recevoir une liste en paramètre. Nous expliquerons pourquoi juste après. Pour l'heure, écrivons une nouvelle fonction qui appelle sieve et lui passe en paramètre la liste infinie [2..] de la façon suivante :

Nous pouvons à présent utiliser la fonction primeNumbers comme suit:

Comme nous pouvons le voir, nous obtenons bel et bien une liste infinie ne contenant que les nombres premiers. C'est très bien, mais vous vous retrouvez sans doute pantois avec votre terminal inaccessible. Pour interrompre cette interminable liste, faites ctrl-c.

Afin de ne pas attendre indéfiniment la liste infinie de nombre premiers, choissons de n'en garder que quelques-un. Pour ce faire, utilisons la fonction Haskell take :

Avant d'aller plus loin, essayons de comprendre comment fonctionne la fonction sieve :

Haskell applique le pattern matching x:xs à cette liste : ainsi pour la liste [2..], x=2 et xs=[3,4,5,...]; avant d'évaluer ce qu'il reste de xs de la façon suivante

Petite subtilité ici, xp `mod` x > 0 est ce qu'on appelle un filtre.
C'est à dire que l'on filtre les éléments de sorte à ne garder que ceux
qui répondent à la condition $xp > 0 [x]$.

On évalue donc xs qui commence avec xp=3 or xp=3 passe le filtre. On se retrouve à présent à passer récursivement la liste [3..] à sieve.

x:xs avec x=3 et xs=[4,5,6,...].

Rebelote

et ainsi de suite. Finalement, on trouve tous les nombres premiers par récursion.

Intéressons-nous à présent à récuperer les nombres premiers qui nous intéressent, ceux qui sont inférieurs ou égaux à $\lfloor\sqrt{2\times n}\rfloor$. Pour ce faire, utilisons cette fois-ci la fonction Haskell takeWhile au sein de la fonction suivante :

Cette fonction eratosthenes s'utilise alors comme suit :

À quoi ressemble donc notre code jusqu'à maintenant ? Eh bien, il est composé des trois lignes suivantes :

Comment cela peut aussi bien fonctionner ? Pour cela il nous faut expliquer takeWhile. takeWhile est une fonction bien utile qui retourne une liste composer de tout les éléments correspondant au filtre passé en paramètre. Ce filtre est, ici, <= floor . sqrt $ 2*n, ce que l'on peut lire

Arrêtons-nous un instant et demandons-nous si ce programme s'effectue rapidement. Pour ce faire, compilons le programme suivant à l'aide de ghc :

À présent, testons !

18 ms pour générer les nombres premiers jusqu'à $\lfloor\sqrt{2\times 3000}\rfloor$...

404 ms pour générer les nombres premiers jusqu'à $\lfloor\sqrt{2\times 999999999}\rfloor$ ! Ça va pas du tout ! C'est beaucoup trop lent ! Peut-on rendre tout ceci plus rapide ? Oui, c'est possible ! Nous allons voir comment dans le post suivant.

Ce n'est que mon avis, mais selon moi… tu risques de te briser la nuque en tombant des nues si tu te rates avec cette mentalité.

Envoie. Je n'aurai pas le temps tout de suite mais je te fais ça d'ici deux trois jours max. ;)

Essaie plus, alors.

Ouais, donc ça ne te sert à rien… tu sais, tu as des personnes qui sont actuellement dans des facs pourries mais qui vont devenir profs dans le supérieur.

De toutes façons comme je l'ai dis plusieurs fois, si tu passes ta vie à te comparer aux autres mais pas à bosser, tu n'y arriveras pas : on ne peut pas apprendre, passer les concours et enseigner à ta place.

Oh effectivement, j'ai tapé ça un peu rapidement et ai inversé $k$ et $n$ pour l'arrangement.

Pour le nombre de combinaisons, cela fait bien longtemps qu'une bonne partie de la littérature française utilise, elle aussi, la notation ${n \choose k}$.

Non. Clairement tu n'y arriveras pas. Non pas parce que tu n'as pas les capacités intellectuelles pour y arriver, mais parce que tu as décidé de te prendre la tête pour rien. D'autant que tu te concentres sur les mathématiques comme si c'était le Saint Graal à obtenir alors que si ça se trouve tu n'es pas fait pour ça et que tu serais meilleur comme informaticien ou comme ingénieur matériaux. Qui sait ? Personne, pas même toi, car tu t'aveugles avec tes idioties.

C'est pourquoi, je te le dis, tu ferais bien d'arrêter de te prendre la tête comme ça et commencer à bosser tes cours (tous) et tes exercices (tous) afin d’améliorer ton niveau et voir où tu réussis.

S'il s'avère que c'est en Mathématiques, tant mieux. S'il s'avère que c'est en Physique, tant mieux aussi et dirige-toi en Physique. S'il s'avère que c'est en Informatique, tant mieux bis bis et dirige-toi vers l'Informatique. Bref, tu as compris l'idée.