Haskell - 从泛型到整数|使用'floor'时没有（RealFrac Integer）的实例

Question

我正在学习哈斯克尔。

我试图解决一个问题，你给出了一个数字（n），你必须找到一对（m，k），其中m ^ k将使n成为一个完美的力量。

如果存在自然数m> 1且k> 1使得m ^ k = n，则n是完美的幂。

这是我到目前为止所提出的

module Test where

isPerfectPowerOf :: (Floating p, Enum p, RealFrac p) => p -> Maybe [(p, p)]
isPerfectPowerOf i
        | null perfectList = Nothing
        | otherwise = Just perfectList
        where perfectList = filter (\(x, _) -> floor x == x) [(logBase x i, x) | x <- [2 .. (i - 1)]]

它的工作原理。但正如您所看到的，使用非常通用的类型。我想要的是与它合作

isPerfectPowerOf :: Integer -> Maybe [(Integer, Integer)]

因此，出于调试目的，我将此签名放在代码上，这给了我这些错误

severity: 'Error'
message: '    • No instance for (RealFrac Integer) arising from a use of ‘floor’
    • In the first argument of ‘(==)’, namely ‘floor x’
      In the expression: floor x == x
      In the first argument of ‘filter’, namely
        ‘(\ (x, _) -> floor x == x)’

severity: 'Error'
message: '    • No instance for (Floating Integer)
        arising from a use of ‘logBase’
    • In the expression: logBase x i
      In the expression: (logBase x i, x)
      In the second argument of ‘filter’, namely
        ‘[(logBase x i, x) | x <- [2 .. (i - 1)]]’

因此，如果我没有完全脱离标记，我将需要以某种方式对地板和logBase的输入进行正确分类。

floor :: (RealFrac a, Integral b) => a -> b

logBase :: Floating a => a -> a -> a

我应该怎么做呢？或者，如果不是问题可能是什么？

Answer 1

所以你试过：

perfectList :: Integer -> [(Integer, Integer)]
perfectList i = filter (\(x, _) -> floor x == x) [(logBase x i, x) | x <- [2 .. (i - 1)]]

（为了简洁起见，我将在这里处理perfectList。请注意，在Maybe中转换为isPerfectPowerOf可能是多余的，因为Maybe结果的虚无等同于列表的空虚。）

这会导致您引用的两种类型错误。第一个出现是因为floor的论证必须是某种RealFrac类型，而Integral不是其中之一。类似地，出现第二个错误是因为logBase获取并返回某些Floating类型的值（因此您不仅需要将参数转换为浮点数，还需要将结果转换回Integer）。执行这些调整会导致：

perfectList :: Integer -> [(Integer, Integer)]
perfectList i = fmap (\(k, x) -> (floor k, x))
    . filter (\(k, _) -> fromIntegral (floor k) == k)
    $ [(logBase (fromIntegral x) (fromIntegral i), x) | x <- [2 .. (i - 1)]]

（请注意，为了清楚起见，我已重命名了您的日志变量;您可能还想要交换对中元素的顺序。）

由于您已经使用了列表推导，因此更容易将fmap和filter移入其中：

perfectList :: Integer -> [(Integer, Integer)]
perfectList i = [(k', x) | x <- [2 .. (i - 1)]
    , let k = logBase (fromIntegral x) (fromIntegral i), let k' = floor k
    , fromIntegral k' == k
    ]

最后，使用floor检查浮点数是否“真的”是一个圆数并不完全可靠：

GHCi> fromIntegral (floor (logBase 2 (2**29))) == logBase 2 (2**29)
False

既然如此，最终更健全的方法将是切换到一种算法，该算法在整个过程中使用整数算法找到完美的幂，从而完全避免浮点。 （虽然我怀疑你自己想要实现它，但对于现成的解决方案，请检查Math.NumberTheory.Powers module from the arithmoi package。）