在 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，而在查找除数时您实际上只需要整数。您可以将浮动 a 转换为带有 ceiling、floor 或 round 的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 也不能​​是双倍的。你有麻烦了...

值得庆幸的是，我们可以在类型之间进行转换，因此虽然 sqrt 需要浮动，而 mod 需要积分（顺便说一句，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)]

但是，您需要认真思考在通过 sqrtsqrt 将整数类型转换为浮点时您真正想要做什么代码>...

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的除数之一，所以我从1开始理解> 代替<代码>2。

嗯，这确实会搜索超出平方根的范围，直到遇到上面的下一个因子。

这个怎么样：

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