在Haskell中获取一个数的除数列表的问题

Question

这不是一个重复的问题阅读下面…

我声明以下函数:

divisors x = [(a, x/a) | a <- [2..(sqrt x)], x `mod` a == 0]

我想要得到的是x的因数:包含(n, k)的元组列表，例如n * k = x

例子:

> divisors x
[(1,10), (2, 5)]

为什么上面的代码不能工作?

它给出了错误:

*Main> divisors 10
<interactive>:1:0:
    Ambiguous type variable `t' in the constraints:
      `Floating t'
        arising from a use of `divisors' at <interactive>:1:0-10
      `Integral t'
        arising from a use of `divisors' at <interactive>:1:0-10
    Probable fix: add a type signature that fixes these type variable(s)

我已经尝试手动设置函数的签名，但没有成功…

Answer 1

问题是sqrt返回Floating a，而您在查找除数时实际上只想要整数。您可以通过ceiling, floor或round将Floating a转换为Integral a。我将使用ceiling，因为我不确定使用floor或average是否会跳过除数。

sqrt函数也只接受浮点数，所以你必须在给它之前把整数转换成浮点数(这可以用fromIntegral完成)。

还可以使用/，它也适用于浮点数。使用div更好，因为它适用于整数(必要时四舍五入)。

divisors x = [(a, x `div` a) | a <- [2..(ceiling $ sqrt $ fromIntegral x)], x `mod` a == 0]

这样，divisors 10将给出[(2,5)](您的代码阻止(1,10)的情况发生-我猜这是故意的)。不幸的是，您将获得重复，例如divisors 12将返回[(2,6),(3,4),(4,3)]，但如果这是一个问题，应该不会太难修复。

Answer 2

如果您要求输入类型:

就可以看到问题了

 divisors :: (Integral t, Floating t) => t -> [(t, t)]

然后检查哪些东西同时是Integral和Floating:

 Prelude> :info Floating
 class Fractional a => Floating a where
 instance Floating Float -- Defined in GHC.Float
 instance Floating Double -- Defined in GHC.Float

和

 Prelude> :info Integral
 class (Real a, Enum a) => Integral a where
 instance Integral Integer -- Defined in GHC.Real
 instance Integral Int -- Defined in GHC.Real

因此，它既不能是Int、Integer、Float或Double。你有麻烦了…

值得庆幸的是，我们可以在类型之间进行转换，因此当sqrt需要float而mod需要Integral(顺便说一下，rem更快)时，我们可以，例如，取消浮点除法:

 divisors :: Integer -> [(Integer, Integer)]
 divisors x = [(a, x `div` a) | a <- [2..ceiling (sqrt (fromIntegral x))], x `rem` a == 0]
 > divisors 100
 [(2,0),(4,0),(5,0),(10,0)]

但是，您需要仔细考虑在通过sqrt…

Answer 3

在Haskell中，整数除法和小数除法是不同的运算，并且有不同的名称。斜杠操作符/用于小数除法。整数除法由div或quot完成(两者之间的区别与涉及负数时的行为有关)。

尝试用

替换x/a

x `quot` a

。

编译器错误准确地告诉您:您有时将类型视为整数(通过使用mod)，有时将类型视为小数(通过使用/)，并且不确定如何选择像这两种类型一样的类型。

你会有一个类似的问题与sqrt，一旦排序，虽然。同样，对于类型是整型还是(在这种情况下)浮点型，您需要保持一致。为了找到可能的除数，取值范围应该是小于浮点数的最大整数，因此考虑使用floor (sqrt (fromIntegral x)))。fromIntegral将x(必须具有整型)转换为另一种类型——在本例中，它将默认为Double。然后floor将Double的结果转换回整型。

Answer 4

不使用平方根来限制搜索，您可以允许推导式在无限列表中取值，并使用takeWhile在余数大于除数时停止搜索:

divisors x = takeWhile (uncurry (<=)) [(a, x `div` a) | a <- [1..], x `mod` a == 0]
> divisors 100
[(1,100),(2,50),(4,25),(5,20),(10,10)]

注意:你原来的例子显示(1,10)是10的divisors之一，所以我从1开始理解，而不是2。

嗯，它会搜索平方根以外的元素，直到找到上面的下一个因子。

这个怎么样:

divisors x = [(a, x `div` a) | a <- takeWhile ((<= x) . (^2)) [1..], x `mod` a == 0]