帮助在Haskell中调试大量的意外takeWhile行为

Question

首先,道歉模糊的冠军,但我不知道究竟我问这里有什么(!).

在大学遇到Haskell之后,我最近开始在愤怒中使用它,所以我正在努力解决Project Euler问题,作为扩展的Hello World.我遇到一个错误在我的答案,这似乎暗示了语言的基本组成部分的误解之一,它不是我可以从教程工作了,也没有什么我有足够的了解,以启动谷歌搜索.

问题本身的简要描述 - 解决方案与素数有关,所以我想要一个无限的素数列表,我实现了(没有优化!)因此:

isPrime :: Int -> Bool
isPrime n = isPrime' 2 n
            where isPrime' p n | p >= n           = True
                               | n `mod` p == 0  = False
                               | otherwise       = isPrime' (p+1) n

primes :: [Int]
primes = filter isPrime [2..]

由于无限列表的评估可能有点繁琐,我当然会使用惰性求值来确保只需要我想要的位来进行评估.所以,举例来说,我可以向GHCI询问小于100的素数:

*Main> takeWhile (< 100) primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

现在这里是我根本不理解的部分 - 当上限变得足够大时,我根本得不到答案.特别是:

*Main> takeWhile (< 4000000000) primes
[]

这takeWhile本身不是问题,也不是部分应用的功能,takeWhile (< 4000000000) [2..]正如我所期望的那样.使用过滤器(在定义中primes)不是问题,因为它takeWhile (< 4000000000) (filter even [2..])也会返回预期的结果.

通过二进制搜索,我发现有效的最大上限是2^31 - 1,所以这肯定会暗示某种基于空间的约束(即最大正有符号整数).然而:

1. 我的印象是Haskell对整数的大小没有语言限制,并且它们仅受可用内存量的限制.
2. 这个数字只出现在小于谓词中,我知道至少在某些情况下,这个谓词可以正常工作.当它被应用于列表的元素时,它应该不关心它们来自何处？仅仅看第一个元素,我知道谓词在输入2时返回true filter even [2..]; 我知道这primes将返回2作为其第一个元素.那么我的列表怎么可能是空的,这个谓词如何失败"对于某些2的值"？

任何想法都会感激不尽,因为我没有足够的经验知道从哪里开始.感谢您抽出宝贵时间来了解一下.

Answer 1

haskell中有2种内置整数类型:Int和Integer.Integer是默认值并且无限制.Int然而是有限的.由于您明确使用Int的类型为isPrime4000000000用作Int和溢出.如果更改的类型isPrime来Integer -> Bool甚至更好Integral a => a -> Bool(阅读:可以采取任何形式的函数Integral值,并返回一个Bool)如预期,它会工作.

重要的是要拿走这里(比之间的差异等Int而Integer)是40亿的类型取决于如何使用它.如果它被用作带有a的函数的参数Int,它将是一个Int(并且在32位系统上它将溢出).如果它被用作一个带有a的函数的参数Integer,它将是一个Integer(并且永远不会溢出).如果它被用作任何类型的函数的参数Integral,它也将是Integer因为Integer是默认实例Integral.