12

这是我正在尝试做的事情：

isPrime :: Int -> Bool
isPrime x = all (\y -> x `mod` y /= 0) [3, 5..floor(sqrt x)]

（我知道我不是在检查除以二——请忽略它。）这是我得到的：

No instance for (Floating Int)
  arising from a use of `sqrt'
Possible fix: add an instance declaration for (Floating Int)
In the first argument of `floor', namely `(sqrt x)'
In the expression: floor (sqrt x)
In the second argument of `all', namely `[3, 5 .. floor (sqrt x)]'

我已经花了好几个小时尝试我能想到的所有方法来使用 sqrt 的一些变体来制作这个列表，包括像这样的废话

intSqrt :: Int -> Int
intSqrt x = floor (sqrt (x + 0.0))

似乎 (sqrt 500) 工作正常，但 (sqrt x) 坚持 x 是一个浮点数（为什么？），并且我找不到将 Int 转换为实数（为什么？）的函数。

我不想要一种测试素数的方法，我想了解如何解决这个问题。为什么这么难？

4

2 回答 2

21

与大多数其他语言不同，Haskell 严格区分整数和浮点类型，并且不会隐式地将一种转换为另一种。有关如何显式进行转换的信息，请参见此处。甚至还有一个sqrt例子:-)

其根本原因是隐式转换和 Haskel（相当复杂但非常酷）类系统的结合会使类型重构变得非常困难——可能它会将其延伸到机器可以完成的程度之外。语言设计者认为获得算术类型类是值得的，因为必须明确指定转换。

于 2011-08-09T19:59:25.377 回答
19

您的问题是，尽管您尝试以各种方式修复它，但您没有尝试做某事x，这正是您的问题所在。让我们看看类型sqrt：

Prelude> :t sqrt
sqrt :: (Floating a) => a -> a

另一方面，x是一个Int，如果我们向 GHCi 询问关于 的信息Floating，它会告诉我们：

Prelude> :info Floating
class (Fractional a) => Floating a where
  pi :: a
  <...snip...>
  acosh :: a -> a
    -- Defined in GHC.Float
instance Floating Float -- Defined in GHC.Float
instance Floating Double -- Defined in GHC.Float

所以唯一的类型Floating是Floats 和Doubles。我们需要一种将 a 转换Int为 a的方法Double，就像floor :: (RealFrac a, Integral b) => a -> b另一个方向一样。每当你有这样的类型问题时，你可以问Hoogle，这是一个用于搜索类型的 Haskell 搜索引擎。不幸的是，如果你搜索Int -> Double，你会得到糟糕的结果。但是，如果我们放松我们正在寻找的东西呢？如果我们搜索Integer -> Double，我们会发现有一个函数fromInteger :: Num a => Integer -> a，这几乎正是您想要的。而如果我们把我们的类型一路放宽(Integral a, Num b) => a -> b，你会发现有一个函数fromIntegral :: (Integral a, Num b) => a -> b。

因此，要计算整数的平方根，请使用floor . sqrt $ fromIntegral x或使用

isqrt :: Integral i => i -> i
isqrt = floor . sqrt . fromIntegral

您正在为输出的正确方向考虑问题sqrt；它返回一个浮点数，但你想要一个整数。然而，在 Haskell 中，没有子类型或隐式转换的概念，因此您还需要更改输入sqrt。

为了解决您的其他一些问题：

intSqrt :: Int -> Int
intSqrt x = floor (sqrt (x + 0.0))

您将此称为“废话”，因此很明显您不希望它起作用，但是为什么不呢？好吧，问题在于(+)有类型Num a => a -> a -> a——你只能添加两个相同类型的东西。这通常很好，因为这意味着您不能将复数添加到 5×5 实数矩阵；但是，由于0.0必须是 的实例Fractional，因此您将无法将其添加到x :: Int.

似乎 (sqrt 500) 工作正常……</p>

这是有效的，因为类型500不是您所期望的。让我们问问我们值得信赖的伙伴 GHCi：

Prelude> :t 500
500 :: (Num t) => t

事实上，所有整数文字都有这种类型；它们可以是任何类型的数字，因为Num该类包含 function fromInteger :: Integer -> a。因此，当您编写时sqrt 500，GHC 意识到500需要满足（并且由于默认规则500 :: (Num t, Floating t) => t，它会隐式选择Double类似的数字类型）。同样，上面有 type ，这要归功于's功能。0.0Fractional t => tFractionalfromRational :: Rational -> a

…但是 (sqrt x) 坚持 x 是一个 Floating …</p>

见上文，我们在其中查看sqrt.

……我找不到将 Int 转换为真实的函数……。

好吧，你现在有一个：fromIntegral。我不知道你为什么找不到它；显然，由于函数的泛型类型，Hoogle 给出的结果比我预期的要差得多。

为什么这么难？

我希望它不再是了，现在你有了fromIntegral。

于 2011-08-09T21:15:20.970 回答