Comment pourrait-on implémenter une liste de nombres premiers dans Haskell afin qu'ils puissent être récupérés paresseusement? Je ne connais pas encore Haskell et j'aimerais en savoir plus sur les utilisations pratiques de la fonctionnalité d'évaluation paresseuse.Liste paresseuse des nombres premiers
Voici une courte fonction Haskell que de nombres premiers énumère Literate Programs:
primes :: [Integer]
primes = sieve (2 : [3, 5..])
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
Apparemment, cela est pas le Crible d'Eratosthène (merci, Landei). Je pense que c'est toujours un exemple instructif qui montre que vous pouvez écrire du code court très élégant dans Haskell et qui montre comment le choix de la mauvaise structure de données peut gravement nuire à l'efficacité.
Veuillez lire ceci et repenser votre réponse: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf – Landei
La "mauvaise structure de données" (c'est-à-dire la liste) n'a rien à voir avec ça l'inefficacité * extrême * du code (O (n^2), * dans les n premiers nombres produits *), qui est le résultat du déclenchement prématuré des filtres sur chaque prime nouvellement trouvé au lieu de sur son * carré *. Avec la création de filtres [correctement reportée] (http://www.haskell.org/haskellwiki/Prime_numbers#Postponed_Filters), elle tourne à peu près à O (n^1.4..1.45) (dans 'n' nombres premiers produits), tout comme toute autre division d'essai normale. –
Le lien vers [alphabétisation] (http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29) est rompu. – ThreeFx
Il existe un certain nombre de solutions pour la génération paresseuse de séquences premières directement dans le wiki haskell. La première et la plus simple est la Postponed Turner sieve: (ancienne révision ... NB)
primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]
-- or: filter ((/=0).(`rem`p)) t
where (h,~(_:t)) = span (< p*p) xs
Je vous suggère de prendre l'une des mises en œuvre de cet article: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
Très intéressant, j'avais réfléchi pendant un moment à la simplicité de la doublure et je l'ai trouvé vraiment en contraste avec ma propre expérience de mise en place d'un tamis ... ils ont triché! Je suis assez frustré de ne pas l'avoir noté aussi: p –
La réponse acceptée de @nikie n'est pas très efficace, il devient relativement lent après quelques milliers, mais la réponse de @sleepynate est bien meilleure. Il m'a fallu un certain temps pour comprendre, est donc ici le même code, mais seulement avec des variables nommées plus clairement:
lazyPrimes :: [Integer]
lazyPrimes = 2: 3: calcNextPrimes (tail lazyPrimes) [5, 7 .. ]
where
calcNextPrimes (p:ps) candidates =
let (smallerSquareP, (_:biggerSquareP)) = span (< p * p) candidates in
smallerSquareP ++ calcNextPrimes ps [c | c <- biggerSquareP, rem c p /= 0]
L'idée principale est que les candidats pour les prochains nombres premiers contiennent déjà pas de chiffres qui sont divisibles par tout premier moins que le premier premier donné à la fonction. Alors que si vous appelez
calcNextPrimes (5:ps) [11,13,17..]
la liste des candidats contient aucun numéro, qui est divisible par 2 ou 3, cela signifie que le premier candidat non-prime sera 5 * 5, la cause sont déjà éliminés 5* 2 et 5 * 3 et 5 * 4. Cela vous permet de prendre tous les candidats, qui sont plus petits que le carré de 5 et les ajouter tout de suite aux nombres premiers et tamiser le reste pour éliminer tous les nombres divisibles par 5.
Quelque chose comme http://stackoverflow.com/questions/1764163/help-explain-this-morceau-de-haskell-code-that-outputs-a-stream-of-primes – kennytm
Pensez http://hackage.haskell.org/package/primes –
Bien au contraire: c'est une tâche difficile de créer une liste de nombres premiers non-paresseux dans Haskell – vpolozov