为什么以下Haskell代码挂起？

Question

我是Haskell的新手.我试图解决丢番图方程| x ^ yy ^ x | 对于给定的上界x,y <n,使用Haskell 是素数.

所以,我写了这个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,未注释)在GHCi中挂起n > 3.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

因此,您使用0in is_prime,从而也使用listprimesupto.这会导致永无止境的递归:

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

因此,请确保处理非正输入:

listprimesupto n | n <= 0 = []

is_prime n | n <= 1 = False