6

我只是在学习haskell（我自己，为了好玩）而且我碰壁了。

我的问题：

如何定义函数

flrt = (floor . sqrt)

当我在文件中尝试并编译时，GCHi 抱怨以下内容：

AKS.hs:11:9:
    No instance for (RealFrac Integer)
      arising from a use of `floor'
    Possible fix: add an instance declaration for (RealFrac Integer)
    In the first argument of `(.)', namely `floor'
    In the expression: (floor . sqrt)
    In an equation for `flrt': flrt = (floor . sqrt)

AKS.hs:11:17:
    No instance for (Floating Integer)
      arising from a use of `sqrt'
    Possible fix: add an instance declaration for (Floating Integer)
    In the second argument of `(.)', namely `sqrt'
    In the expression: (floor . sqrt)
    In an equation for `flrt': flrt = (floor . sqrt)

我不明白为什么生成的函数不仅仅是 Int -> Int。

我刚刚完成了 CS 的第二年并完成了基础 PL 课程。我听说过，但还不太了解类型。我尝试阅读了一些 haskell 教程，但这一切都超出了我的想象。

PS - 我也不明白什么是单子。（我的搜索出现的许多其他问题都谈到了这些）

PPS - 我的完整来源

bar = \a b -> if (2^a) > b
                then (a-1)
                else bar (a+1) b
foo = bar 1

flrt :: Integer -> Integer
flrt = (floor . sqrt)

aks target = if (target < 2)
                then putStr "Not a Prime.\n\n"
                else if elem (mod target 10) [0,2,4,5,6,8]
                        then putStr "Composite\n\n"
                        else if (elem target) [a^b | a <- [3,5..(flrt target)], b <- [1.. (foo target)]]

                                then putStr "Composite\n\n"--}
                            else 
                            putStr "filler"
4

2 回答 2

9

问题是您试图Integer用作输入。Haskell 是强类型的，这意味着没有任何类型的隐式强制或转换。查看您尝试编写的函数的签名：

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

在 GHC 推断的函数签名处：

> :t floor . sqrt
floor . sqrt :: (RealFrac b, Integral c, Floating b) => b -> c

因此，要拥有一个从Integer（没有Floating实例）到的函数Integer，您必须首先将您的参数转换为Floating，这可以通过使用来完成fromIntegral：

> :t floor . sqrt . fromIntegral
floor . sqrt . fromIntegral :: (Integral a, Integral c) => a -> c
于 2012-06-02T15:15:00.110 回答
5

正如 copumpkin 所说，在此处转换为浮点实际上可能不是一个好主意，因为这会导致精度损失，因此即使进行舍入，对于足够大的整数输入也可能会产生不正确的结果。

我假设您正在处理的所有数字至少足够小，以至于它们有一些浮点表示，例如，所有数字都 < 10 300。但是，例如

Prelude> round(sqrt.fromInteger$10^60 :: Double) ^ 2
1000000000000000039769249677312000395398304974095154031886336
Prelude>  {-   and not   -}     10^60    {-  == (10^30)^2 == (sqrt$10^60) ^ 2  -}
1000000000000000000000000000000000000000000000000000000000000

就绝对差异而言，这是遥不可及的。相对于数字本身，它肯定是一个相当好的近似值，因此您可以将其用作算法快速确定的起点，以找到准确的结果。您可以使用 s 实现 Newton/Raphson（在本例中为 AKA Heron）Integer：

flrt :: Integer -> Integer  -- flrt x ≈ √x,  with  flrt x^2 ≤ x < flrt(x+1)^2
flrt x = approx (round . (sqrt::Double->Double) . fromInteger $ x)
   where approx r
            | ctrl <= x, (r+1)^2 > x  = r
            | otherwise               = approx $ r - diff
          where ctrl = r^2
                diff = (ctrl - x) // (2*r)    -- ∂/∂x x² = 2x

         a//b = a`div`b + if (a>0)==(b>0) then 1 else 0   -- always away from 0

这现在可以按需要工作：

*IntegerSqrt> (flrt $ 10^60) ^ 2
1000000000000000000000000000000000000000000000000000000000000

在 Newton-Raphson 校正中总是远离 0 的除法在这里是必要的，以防止陷入无限递归。

于 2012-06-02T20:11:35.240 回答