fonction élém aucune liste limite

Question

liste compréhension haskell

paar = [(a,b) | a<-[a | a<-[1..], mod a 3 == 0], b<-[b*b | b<-[1..]]] 

a = diviseur 3 b = carré

Les éléments doivent être construits par ordre équitable.

le test> élém (9, 9801) doit être vrai

mon erreur

principal> élém (9, 9801) Test

ERREUR - Collecte des ordures ménagères ne récupérer suffisamment d'espace

Comment puis-je l'implémenter avec l'argument diagonal de Cantor?

thx

Answer 1

Voici un classement alternatif de la même liste (par la suggestion de Hammar):

-- the integer points along the diagonals of slope -1 on the cartesian plane, 
-- organized by x-intercept 
-- diagonals = [ (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ... 
diagonals = [ (n-i, i) | n <- [0..], i <- [0..n] ] 

-- the multiples of three paired with the squares 
paar = [ (3*x, y^2) | (x,y) <- diagonals ] 

et en action:

ghci> take 10 diagonals 
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)] 
ghci> take 10 paar 
[(0,0),(3,0),(0,1),(6,0),(3,1),(0,4),(9,0),(6,1),(3,4),(0,9)] 
ghci> elem (9, 9801) paar 
True 

En utilisant un chemin diagonale pour parcourir toutes les valeurs possibles, nous garantir que nous atteignons chaque point fini en temps fini (bien que certains points soient encore en dehors des limites de la mémoire). Comme le souligne Hammar dans son commentaire, ce n'est pas suffisant, car il faudra encore une durée infinie pour obtenir une réponse False.

Cependant, nous avons un ordre sur les éléments de paar, à savoir (3*a,b^2) vient avant (3*c,d^2) lorsque a + b < c + d. Donc, pour déterminer si une paire donnée (x,y) est en paar, nous avons seulement à vérifier paires (p,q) tandis que p/3 + sqrt q <= x/3 + sqrt y.Pour éviter d'utiliser les numéros Floating, nous pouvons utiliser une condition légèrement plus lâche, à savoir p <= x || q <= y. Certainement p > x && q > y implique p/3 + sqrt q > x/3 + sqrt y, donc cela comprendra toujours des solutions possibles, et il est garanti pour se terminer.

On peut donc construire cette vérification dans

-- check only a finite number of elements so we can get a False result as well 
isElem (p, q) = elem (p,q) $ takeWhile (\(a,b) -> a <= p || b <= q) paar 

et de l'utiliser:

ghci> isElem (9,9801) 
True 
ghci> isElem (9,9802) 
False 
ghci> isElem (10,9801) 
False 

Answer 2

Pas tout à fait sûr de ce que votre objectif est ici, mais voici la raison pour laquelle votre code explose.

Prelude> let paar = [(a,b) | a<-[a | a<-[1..], mod a 3 == 0], b<-[b*b | b<-[1..]]] 
Prelude> take 10 paar 
[(3,1),(3,4),(3,9),(3,16),(3,25),(3,36),(3,49),(3,64),(3,81),(3,100)] 

avis vous générez toutes les paires (3, ?) avant tout autre. La fonction elem fonctionne en recherchant linéairement cette liste depuis le début. Comme il y a un nombre infini de paires (3, ?), vous n'atteindrez jamais les (9, ?).

En outre, votre code est probablement maintenu à paar quelque part, ce qui l'empêche d'être collecté. Cela se traduit par elem (9, 9801) paar prenant non seulement un temps infini mais aussi un espace infini, conduisant à l'accident que vous avez décrit. En fin de compte, vous devrez probablement adopter une autre approche pour résoudre votre problème. Par exemple, quelque chose comme ceci:

elemPaar :: (Integer, Integer) -> Bool 
elemPaar (a, b) = mod a 3 == 0 && isSquare b 
    where isSquare = ... 

Ou bien comprendre une autre stratégie de recherche que la recherche linéaire tout droit à travers une liste infinie.