Haskell n'évalue pas paresseusement takeWhile

Question

isqrt :: Integer -> Integer 
isqrt = floor . sqrt . fromIntegral 

primes :: [Integer] 
primes = sieve [2..] where 
sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0] 

primeFactors :: Integer -> [Integer] 
primeFactors n = takeWhile (< n) [x | x <- primes, n `mod` x == 0] 

Voici mon code. Je pense que vous avez deviné ce que j'essaie de faire: Une liste de facteurs premiers d'un nombre donné utilisant une liste infinie de nombres premiers. Mais ce code ne s'évalue pas paresseusement.

Lorsque j'utilise ghci et :l mycode.hs et entrer primeFactors 24, le résultat est [2, 3 (et le curseur clignote toujours là) il n'y a pas plus rapide Prelude>. Je pense qu'il y a un problème là-bas. Qu'est-ce que je fais mal?

Merci.

Answer 1

takeWhile ne se termine jamais pour les arguments composites. Si n est composite, il n'a pas de facteurs premiers >= n, donc takeWhile va juste rester là.

Appliquer takeWhile à la liste des nombres premiers, puis filtrer le résultat avec n mod x, comme ceci:

primeFactors n = [x | x <- takeWhile (<= n) primes, n `mod` x == 0] 

(<= est utilisé au lieu de < pour l'exactitude maximale, de sorte que les facteurs premiers d'un nombre premier serait composé de ce nombre).

Answer 2

Avoir une illustration de ce qui se passe:

http://sketchtoy.com/67338195

Answer 3

Votre problème n'est pas directement takeWhile, mais la compréhension de la liste.

[x | x <- primes, n `mod` x == 0] 

Pour n = 24, nous obtenons 24 `mod` 2 == 0 et 24 `mod` 3 == 0, de sorte que la valeur de cette compréhension de la liste commence par 2 : 3 : .... Mais considérons la partie ....

La compréhension de la liste doit continuer à tirer des valeurs de primes et de vérifier 24 `mod` x == 0. Comme il n'y a plus de facteurs premiers de 24, rien ne passera jamais ce test et sera émis comme la troisième valeur de la compréhension de la liste. Mais puisqu'il y a toujours un autre prime à tester, il ne s'arrêtera jamais et conclura que le reste de la liste est vide. Parce que cela est évalué paresseusement, si vous demandez seulement les deux premiers éléments de cette liste, alors tout va bien. Mais si votre programme a besoin d'un troisième élément (ou même juste pour savoir s'il y a ou un troisième élément), alors la compréhension de la liste tournera pour toujours en essayant d'en trouver une.

takeWhile (< 24) conserve les éléments de son argument jusqu'à ce qu'il en trouve un autre que < 24. 2 et 3 tous les deux passer ce test, donc takeWhile (< 24) besoin de savoir ce que le troisième élément de la compréhension de la liste est.

Mais ce n'est pas vraiment un problème avec takeWhile; le problème est que vous avez écrit une liste de compréhension pour trouver tous les facteurs premiers (et rien d'autre), puis essayez d'utiliser un filtre sur les résultats de cela pour couper l'exploration infinie de tous les nombres premiers supérieurs qui ne peut pas être des facteurs.Cela n'a pas vraiment de sens si vous arrêtez d'y penser; par définition tout ce qui n'est pas un facteur premier ne peut pas être un élément de cette liste, donc vous ne pouvez pas filtrer les non-facteurs plus grands que n de cette liste. Au lieu de cela, vous devez filtrer l'entrée à la compréhension de cette liste afin qu'elle n'essaie pas d'explorer un espace infini, comme le montre la réponse de @ n.m.