Почему следующий код Haskell висит?

Question

Я новичок в Haskell. Я пытался решить диофантовое уравнение | x^y-y^x | является простым, используя Haskell, для заданной верхней границы x, y < n.

Итак, я написал этот Haskell код:

-- list of primes 
listprimesupto :: Integral a => a -> [a] 
listprimesupto 1 = [] 
listprimesupto 2 = [2] 
listprimesupto n = let halflstprimes = (listprimesupto (n `div` 2)) 
        in halflstprimes++[i|i<-[((n `div` 2)+1)..n], (length [x|x<-halflstprimes, (i `mod` x) == 0])==0 ] 

-- is prime? 
is_prime :: Integral a => a -> Bool 
is_prime 1 = False 
is_prime n = let halflstprimes = (listprimesupto (n `div` 2)) 
      in (length [x|x<-halflstprimes, (n `mod` x) == 0])==0   

-- solve |x^y - y^x| == prime 
xy_yx_p :: Integral t => t -> [(t, t)] 
--xy_yx_p n = [(x,y)|x<-[2..n], y<-[2..n], x < y, (abs (x^y-y^x)) `elem` (listprimesupto (n^3))] -- version 1, works but upper limit too small 
xy_yx_p n = [(x,y)|x<-[2..n], y<-[2..n], x < y, (let t=abs (x^y-y^x) in is_prime t)==True] -- version 2, hangs for n>3 ... 

xy_yx_p n (версия 2, раскомментировать) нависает для п> 3, в GHCi. Ctrl-C даже не работает. Я должен убить ghc из Activity Monitor (я нахожусь на Mac).

Любая идея, что я делаю неправильно в xy_yx_p? Остальные две функции работают нормально.

Заранее спасибо.

Answer 1

Итак, если он висит за n = 4, что такого особенного в этом случае? Ну, это t. Для x = 2 и y = 4, вы получите

t = abs (2^4 - 4^2) 
    = abs (16 - 16 ) 
    = abs 0 
    = 0 

Таким образом, вы используете 0 в is_prime, и тем самым в listprimesupto. Это приводит к нескончаемой рекурсии:

listprimesupto 0 = let halflstprimes = (listprimesupto (0 `div` 2)) 
        in -- ..... 

поэтому убедитесь, что вы справляетесь неположительные входы:

listprimesupto n | n <= 0 = [] 

is_prime n | n <= 1 = False