Primes en Haskell

Question

J'apprends Haskell, et j'ai essayé de générer une liste infinie de nombres premiers, mais je n'arrive pas à comprendre ce que ma fonction fait mal.

La fonction :

prime = 2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..]

Je pense que c'est le init prime mais ce qui est étrange, c'est que même si je fixe une limite supérieure à l'intervalle ( 5..10 par exemple), la fonction boucle indéfiniment et n'obtient jamais de résultat pour les éléments suivants prime !! 2

Pouvez-vous me dire ce que je fais de mal ?

Answer 1

Et bien, pour commencer, regardons ce que init pour une liste finie :

init [1] == []
init [1,2] == [1]
init [1,2,3] == [1,2]

ok, donc ça nous donne tout sauf le dernier élément de la liste.

Alors, qu'est-ce que init primes ? Eh bien, prime sans le dernier élément. Espérons que si nous implémentons prime correctement, il ne devrait pas ont un dernier élément (parce qu'il y a une infinité de nombres premiers !), mais plus important encore, nous n'avons pas besoin de nous en préoccuper pour l'instant car nous n'avons pas la liste complète de toute façon - nous ne nous intéressons qu'aux deux premiers éléments après tout, donc pour nous c'est à peu près la même chose que prime lui-même.

Maintenant, en regardant all : Qu'est-ce que ça fait ? Eh bien, il prend une liste et un prédicat et nous dit si tous les éléments de la liste satisfont le prédicat :

all (<5) [1..4] == True
all even [1..4] == False

cela fonctionne même avec des listes infinies !

all (<5) [1..] == False

Alors, qu'est-ce qui se passe ici ? Eh bien, voici la chose : cela fonctionne avec des listes infinies... mais seulement si nous pouvons réellement évaluer la liste jusqu'au premier élément de la liste qui viole le prédicat ! Voyons si cela est vrai ici :

all (\y -> (mod 5 y) > 0) (init prime)

afin de savoir si 5 est un nombre premier, il faudrait vérifier s'il existe un nombre dans le nombre premier moins le dernier élément du nombre premier qui le divise. Voyons si on peut le faire.

Maintenant, regardons la définition de prime, nous obtenons

all (\y -> (mod 5 y) > 0) (2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..])

Donc, pour déterminer si 5 est un nombre premier, il suffit de vérifier si c'est le cas :

1. divisible par 2 - ce n'est pas le cas, continuons.
2. divisible par 3 - toujours pas
3. divisible par ... ? Eh bien, nous sommes en train de vérifier quel est le 3ème nombre premier, donc nous ne savons pas encore...

et c'est là le cœur du problème. Avec cette logique, pour déterminer le troisième nombre premier, il faut connaître le troisième nombre premier ! Bien sûr, logiquement, nous avons en fait Ne le fais pas. Nous ne voulons pas du tout vérifier ce point, nous devons seulement vérifier si l'un des éléments suivants plus petit les nombres premiers sont des diviseurs du candidat actuel.

Alors comment s'y prendre ? Eh bien, nous allons devoir changer notre logique, malheureusement. Une chose que nous pouvons faire est d'essayer de nous souvenir du nombre de nombres premiers que nous avons déjà, et de ne prendre que le nombre dont nous avons besoin pour notre comparaison :

prime = 2 : 3 : morePrimes 2 [5..]
  morePrimes n (x:xs)
    | all (\y -> mod x y > 0) (take n prime) = x : morePrimes (n+1) xs
    | otherwise                              = morePrimes n xs

Alors, comment ça marche ? Eh bien, il fait essentiellement ce dont nous venons de parler : Nous nous souvenons du nombre de nombres premiers que nous avons déjà (en commençant par 2 parce que nous savons que nous avons au moins [2,3] en n . Nous vérifions ensuite si notre prochain nombre premier est divisible par l'un des nombres premiers suivants n que nous connaissons déjà en utilisant take n et si c'est le cas, nous savons que c'est notre prochaine étape importante et nous devons l'augmenter. n - sinon, nous continuons.

Il y a aussi la forme plus connue inspirée par le tamis d'Eratosthène (mais pas tout à fait la même) :

prime = sieve [2..] where
  sieve (p:xs) = p : sieve (filter (\x -> mod x p > 0) xs)

Alors, comment ça marche ? Eh bien, encore une fois avec une idée similaire : Nous savons que le prochain nombre premier doit être non divisible par tout nombre premier précédent. Alors, que faisons-nous ? Eh bien, en commençant par 2 nous savons que le premier élément de la liste est un nombre premier. Nous éliminons ensuite tous les nombres divisibles par ce nombre premier en utilisant la méthode suivante filter . Et ensuite, le prochain élément de la liste sera à nouveau un nombre premier (parce que nous ne l'avons pas jeté), et nous pourrons donc répéter le processus.

Ce ne sont pas des phrases toutes faites comme celle que vous espériez.

Answer 2

Si le code dans l'autre réponse est restructuré sous l'identité

[take n primes | n <- [0..]]  ==  inits primes

on obtient finalement

import Data.List
              -- [ ([], 2), ([2], 3), ([2,3], 5), ... ]
primes = 2 : [ c | (ps, p) <- zip (inits primes) primes,  
                   c <- take 1 [c | c <- [p+1..], 
                                    and [mod c p > 0 | p <- ps]]]

En l'améliorant encore de manière algorithmique, elle devient

primes = 2 : [ c | (ps, r:q:_) <- zip (inits primes)                  -- [] [3,4,...]
                                      (tails $ 3 : map (^2) primes),  -- [2] [4,9,...]
                   c <- [r..q-1], and [mod c p > 0 | p <- ps]]        -- [2,3] [9,25,...]