在Haskell中组合floor和sqrt

Question

我是一名有帮助的助手，可以为您提供翻译。以下是您需要翻译的内容：

我只是自学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。

我刚刚完成了我的第二年计算机科学课程，并完成了基础的PL课程。我听说过类型，但还不太理解。我尝试阅读了一些Haskell教程，但这一切都超出了我的理解范围。

P.S. - 我也不明白Monad是什么。（我的搜索结果中有很多其他问题涉及到这个）

P.P.S. - 我的完整源代码

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"

- C.E.Sally

---

floor $ sqrt 意味着对函数 sqrt 求完平方根后再向下取整。你误将 floor 应用于函数 sqrt 上了。你需要的是函数复合。尝试使用 floor . sqrt. - Vitus

@Vitus：你本来可以把它作为答案的！ - gorlum0

好的，我的错；那确实可以解决。但是当我尝试编译它时，仍然存在问题。 - C.E.Sally

请记住，您可能实际上不想要 floor.sqrt 而是想要 intSqrt :: Integer -> Integer（或者实际上是 Natural -> Natural）。 sqrt 经过一个不精确的 Float 或 Double，考虑到素性测试通常使用非常大的数字，精度损失可能最终会影响您。但是再说一遍，您的算法并不特别适用于大数，所以您也许不用担心 :) - copumpkin

@copumpkin：谢谢！嗯...最终目标是让它能够处理非常大的数字，但我打算先从一个朴素的实现开始，然后再阅读一些数值分析方面的资料，再重新进行一遍。 - C.E.Sally

Answer 1

问题在于您尝试使用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 到 Integer 的函数（其中没有 Floating 实例），你需要先将参数转换为 Floating，可以使用 fromIntegral 来完成：

> :t floor . sqrt . fromIntegral
floor . sqrt . fromIntegral :: (Integral a, Integral c) => a -> c

- Cat Plus Plus

Answer 2

如 copumpkin 所指出的，将其转换为浮点数可能实际上是一个不好的想法，因为这会导致精度损失，并且因此在足够大的整数输入下，即使进行四舍五入，也可能产生错误的结果。

我假设你所处理的所有数字都至少小到有某个浮点表示形式，例如都 <10³⁰⁰。但是，例如

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

这个方法的绝对误差很大，但相对于数字本身来说确实是个不错的近似值，所以你可以将它作为算法的一个快速确定的起点来找到精确结果。您可以使用整数实现牛顿/拉夫逊（在这种情况下也称为海伦）：

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

在牛顿-拉夫逊纠正过程中，将除数始终保持不等于0是必要的，以防止进入无限递归的状态。

- leftaroundabout

---

+1 对于加入数值分析的内容 =)，但您能否解释一下这段代码的含义吗？
flip const "AND NOT:" (10^60) -- == (10^30)^2 "== (sqrt$10^60) ^ 2"
我不明白它是如何得出 (sqrt$10^60) ^ 2 的结果的（它确实是这个结果吗？） - C.E.Sally

不，不是的，很抱歉。这只是在(10^60)之前插入注释的愚蠢方式。已编辑。 - leftaroundabout