如何正确定义Haskell函数isPrime？

Question

我正在尝试创建一个基本函数来测试Haskell中整数的素数.我有一些代码可以在临时意义上工作,但在我尝试将其传递给函数时会继续收到错误消息.请注意,我正在GHCi中直接编写定义,使用:{和:}.

我们的想法是创建一个N modulo {所有整数直到舍入sqrt(N)}的列表,然后测试结果列表中除初始索引之外的零.以下四个功能都有效:

rndRoot :: (Floating a, Integral c, RealFrac a) => a -> c
rndRoot = round . sqrt

oneToRndRoot :: (Floating a, Integral t, RealFrac a) => a -> [t]
oneToRndRoot x = [1..rndRoot(x)]

modulo x y
  | n < 0 = x
  | otherwise = modulo n y
  where n = x - y

mapMod x = map (modulo x)

这也有效:

mapMod 49 (oneToRndRoot 49)

然而,虽然repl接受这个定义而没有抱怨......

mapModToRndRoot x = mapMod x $ oneToRndRoot x

...当我尝试使用它时,它会吐出以下错误消息:

Prelude> mapModToRndRoot 39

<interactive>:475:1:
    No instance for (Floating a0) arising from a use of ‘it’
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Floating Double -- Defined in ‘GHC.Float’
      instance Floating Float -- Defined in ‘GHC.Float’
    In the first argument of ‘print’, namely ‘it’
    In a stmt of an interactive GHCi command: print it

似乎工作正常的临时解决方案只是使用两个参数而不是重复相同的参数

mapModToRndRoot2 x y = map (modulo x) (oneToRndRoot y)

Prelude> mapModToRndRoot2 33 33
[0,1,0,1,3,3]

Answer 1

检查类型mapModToRndRoot给出以下内容:

mapModToRndRoot :: (Floating a, Integral a, RealFrac a) => a -> [a]

于是,打电话mapModToRndRoot 39,我们就需要一个数字类型分配给字面39即是一个实例RealFrac,Integral和Floating.但是,没有Prelude数字类型满足所有这三个约束,因此我们得到编译错误.

另一方面,mapMod 49 (oneToRndRoot 49)工作得很好.注意下面lambda的类型:

\x y -> mapMod x (oneToRndRoot y)
  :: (RealFrac a, Integral b, Floating a) => b -> a -> [b]

通过使用两个文字,GHC能够为每个文本分配不同的类型,以满足类型类约束.

编辑:这是@duplode建议的解决方案:

rndRoot :: (Integral a) => a -> a
rndRoot = round . sqrt . fromIntegral

我的原始建议fromIntegral . round . sqrt容易受到使用浮点运算所带来的所有常见的困难.

编辑:正如@WarrickMacmillan指出的那样,签名oneToRndRoot也必须改变.以下是完整注释的整个工作程序.

rndRoot :: Integral a => a -> a
rndRoot = round . sqrt . fromIntegral

oneToRndRoot :: Integral a => a -> [a]
oneToRndRoot x = [1..rndRoot(x)]

modulo :: (Ord p, Num p) => p -> p -> p
modulo x y
  | n < 0 = x
  | otherwise = modulo n y
  where n = x - y

mapMod :: (Num b, Ord b) => b -> [b] -> [b]
mapMod x = map (modulo x)

mapModToRndRoot :: Integral a => a -> [a]
mapModToRndRoot n = mapMod n (oneToRndRoot n)