在哈斯克尔组成楼层和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.

我刚刚完成了CS的第二年并完成了基础PL课程.我听说过,但还没有得到类型.我尝试阅读一些haskell教程,但这一切都超越了我的脑海.

PS - 我也不明白monad是什么.(我的搜索出现的很多其他问题都谈到了这些问题)

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"

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(没有Floating实例)到的函数Integer,你必须首先将你的参数转换为Floating,这可以通过使用fromIntegral:

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

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

这是道关,绝对差方面.它仍然是相对于数字本身的相当好的近似值,因此您可以将其用作算法的快速确定的起点,以找到确切的结果.您可以使用Integers 实现Newton/Raphson(在本例中为AKA Heron):

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,因此必须防止卡在无限递归中.