代码之家 › 专栏 › 技术社区 › Andrzej Doyle

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

integer haskell debugging

Andrzej Doyle · 技术社区 · 15 年前

首先,为这个模糊的标题道歉,但我不确定 确切地 我要问的是(!)。

在大学里遇到Haskell之后,我最近开始愤怒地使用它,所以我正在努力解决这个问题 Project Euler 作为一个扩展的你好世界的问题,真的。我在我的一个答案中遇到了一个错误,它似乎暗示了对语言的一个基本部分的误解,而且这不是我从教程中得到的答案,也不是我知道的足以开始搜索的东西。

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

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 ,因此这似乎肯定意味着某种基于空间的约束(即最大正符号整数)。然而:

这个数字只出现在less-than谓词中,我知道它至少在某些情况下起作用。当然,当它应用于列表的元素时,它不应该关心它们来自哪里?只看第一个元素,我知道谓词为输入返回true 2 当它来自 filter even [2..] ; 我知道那个 素数 退货

2 回复 | 直到 15 年前

sepp2k 15 年前

haskell中有两种内置的积分类型: Int 和 Integer 整数 是默认值,没有限制。但是它是有界的。因为你在用 内景 isPrime 内景 溢出。如果你改变了 isPrime公司 到 Integer -> Bool 或者更好 Integral a => a -> Bool (阅读:一个函数,可以采取任何形式的 Integral 值并返回 Bool

重要的是要带走这里(除了 内景 和 )4000000000的类型取决于它的使用方式。如果它用作接受 内景 ,这将是一个 内景 (在32位系统上它会溢出)。如果它用作接受 ,这将是一个 整数 (永远不要溢出)。如果它被用作一个函数的参数 ,这也将是一个 整数 因为 整数 是的默认实例 .

BMeph 15 年前

这是一个简单的答案(我认为已经有部分答案了)——“过早的专业化”。

定义的第一部分类型签名指定:

isPrime :: Int -> Bool

Int 不仅仅是一种“捷径”的说法 Integer - ! 作为一个吹毛求疵的人(这反过来又会让其他人撕碎这里的许多地方,在我不准确的地方),有从未 2 “-它必须是Int类型,因为这就是您指定函数的方式(将2与函数的参数进行比较) n 你只能比较同一类型的值,所以你的 2 被“压”到 内景 类型。

哦,作为一个警告,Int类型是一个充满了角落大小写可能性的类型。如果您的系统是在64位环境中构建的,那么 内景 也将基于64位表示,并且您的示例将最多使用2^63-1,而不是像您的示例那样使用2^31-1。请注意我的措辞:我有一台64位计算机,带有MS Windows操作系统,这意味着还没有一个官方的64位MinGW工具链——我的操作系统是64位的,但我的GHC版本是用32位库编译的,所以它是基于32位的 内景 s。当我使用Linux时,即使是在虚拟机中,它也有一个64位的工具链,所以 内景 s是64位。如果你用过其中一种,你可能根本就没有注意到这种行为!

所以,我想这只是在考虑你的类型时要小心的另一个原因(尤其是在哈斯克尔,无论如何……)