composing floor and sqrt in haskell

Question

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"

Banas

floor $ sqrt means floor sqrt - you're trying to apply floor to function sqrt. What you want is function composition. Try floor . sqrt. – Esker

@Vitus: You could've made it the answer! – Porty

ok, my bad; that does indeed work out. But I still have a problem when trying to compile it. – Banas

Keep in mind that you probably don't actually want floor . sqrt but want intSqrt :: Integer -> Integer (or Natural -> Natural, really) instead. sqrt goes through an imprecise Float or Double, and considering that primality testing often works with very large numbers, the loss of precision might eventually bite you. But then again, your algorithm isn't particularly well suited to large numbers, so you might be fine :) – Redemptioner

@copumpkin: Thanks! and well... the ultimate end is for it to work with very large numbers, but I was figuring I'd start with a naive implementation and then read up on some numerical analysis and go through it again. – Banas

Answer 1

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 < 10³⁰⁰. 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.

Australorp

+1 for the numerical analysis thrown in =) but could you also please explain flip const "AND NOT:" (10^60) -- == (10^30)^2 "== (sqrt$10^60) ^ 2" I don't get how that gives (sqrt$10^60) ^ 2 (that is what it gives right?) – Banas

No, it's not, I'm sorry. It's just a stupid way of inserting a comment before (10^60). Edited. – Australorp

Answer 2

The problem is that you're trying to use Integer as the input. Haskell is strongly typed, which means there are no implicit coercions or conversions of any kind. Look at signatures of functions you're trying to compose:

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

And at the signature of your function inferred by GHC:

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

So, to have a function that goes from Integer (which doesn't have a Floating instance) to Integer, you have to first convert your argument to Floating, which can be done by using fromIntegral:

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

Finnougrian