在haskell中组成floor和sqrt [英] composing floor and sqrt in haskell

问题描述

我的问题：

我只是在学习haskell（我自己，为了好玩）。 b
$ b

如何定义一个函数

  flrt =（floor。sqrt）
  

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

  AKS.hs：11：9：
由于使用floor引起的（RealFrac Integer）
没有实例
可能的修正：为（RealFrac Integer）添加实例声明
在'（。）'的第一个参数中，即'floor'
在表达式中：（floor。sqrt）
 In 'flrt'的等式：flrt =（floor。sqrt）
 
 AKS.hs：11：17：
没有使用（浮点整数）
的实例`sqrt'
可能的修正：为（Floating Integer）
添加一个实例声明在'（。）'的第二个参数中，即`sqrt'
在表达式中：（floor。sqrt ）
在等式中`flrt'：flrt =（floor。 sqrt）
  

我不明白为什么结果函数不只是Int - > Int。

我刚完成我的第二学年，完成了基础PL课程。我听说过，但还没有完全获得类型。我试着阅读了一些haskell的教程，但它都超出了我的头。

- 我也不明白monad是什么。 （我搜索出来的很多其他问题都谈到了这些）

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

  bar = \ a b  - >如果（2 ^ a）> b 
 then（a-1）
 else bar（a + 1）b 
 foo = bar 1 
 
 flrt :: Integer  - >整数
 flrt =（floor。sqrt）
 
 aks target = if（target <2）
 then putStrNot a Prime.\\\
\\\

 else if elem（mod target 10）[0,2,4,5,6,8] 
 then putStrComposite \\\
\\\

 else if（elem target）[a ^ b | a  -  [3,5 ..（flrt target）]，b < -  [1 ..（foo target）]] 
 
然后putStrComposite \\\
\\\
 -  - } 
 else 
 putStrfiller
  

解决方案

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

我假设您处理的所有数字都至少足够小，以至于 是它们的一些浮点表示形式，例如全部是< 10 ³⁰⁰ 。但是，例如

  Prelude> （sqrt.fromInteger $ 10 ^ 60 :: Double）^ 2 
 1000000000000000039769249677312000395398304974095154031886336 
 Prelude> { -  and not  - } 10 ^ 60 { -  ==（10 ^ 30）^ 2 ==（sqrt $ 10 ^ 60）^ 2  - } 
 1000000000000000000000000000000000000000000000000000000000000 
  pre> 
 
 
关于绝对差异， way 关闭。尽管如此，它对数字本身来说确实是一个相当好的近似值，所以您可以将其用作算法的快速确定的起点以找到确切的结果。您可以使用整数 s来实现Newton / Raphson（在这种情况下为AKA Heron）： 
 
 
  flrt :: Integer  - >整数 -  flrt x≈√x，flrt x ^ 2≤x< flrt（x + 1）^ 2 
 flrt x = approx（round。（sqrt :: Double-&Double;）fromInteger $ x）
 where r 
 | ctrl <= x，（r + 1）^ 2> x = r 
 |否则= approx $ r  -  diff 
其中ctrl = r ^ 2 
 diff =（ctrl  -  x）//（2 * r） - ∂/∂xx²= 2x 
 
a // b = a`div`b + if（a> 0）==（b> 0）then 1 else 0  -  always from 0 
   
 
 $ b 
现在可以根据需要运行： 
 
 
  * IntegerSqrt> （flrt $ 10 ^ 60）^ 2 
 10000000000000000000000000000000000000000000000000000000000 
  
牛顿 - 拉夫逊修正在这里是必要的，以防止陷入无限递归。
 
I'm just learning haskell (on my own, for fun) and I've come up against a wall.

My Question:

How can I define a function 
flrt = (floor . sqrt)
When I try it in a file and compile, GCHi complains with the following:
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)
I don't understand why the resulting function isn't just Int -> Int.

I've just finished my second year of CS and done a basic PL course. I've heard of, but don't quite get types yet. I tried reading through a few haskell tutorials but it's all going above my head.

P.S. - I also don't understand what a monad is. (a lot of the other questions that my search turned up talked about these)

P.P.S. - My full source
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"

解决方案
As copumpkin remarked, it might actually be a bad idea to convert to floating point here, because this comes with loss of precision and therefore might, even with rounding, yield incorrect results for sufficiently large integer inputs.

I assume all numbers you're dealing with will at least be small enough that there is some floating-point representation for them, e.g. all are < 10300. But, for instance
Prelude> round(sqrt.fromInteger$10^60 :: Double) ^ 2
1000000000000000039769249677312000395398304974095154031886336
Prelude>  {-   and not   -}     10^60    {-  == (10^30)^2 == (sqrt$10^60) ^ 2  -}
1000000000000000000000000000000000000000000000000000000000000
Which is way off, in terms of absolute difference. Still it's certainly a rather good approximation relative to the numbers themselves, so you can use it as a quickly determined starting point for an algorithm to find the exact result. You can implement Newton/Raphson (in this case AKA Heron) with Integers:
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
This now works as desired:
*IntegerSqrt> (flrt $ 10^60) ^ 2
1000000000000000000000000000000000000000000000000000000000000
The division always away from 0 in the Newton-Raphson correction is here necessary to prevent getting stuck in an infinite recursion.

                        
这篇关于在haskell中组成floor和sqrt的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！