Haskell sqrt type error

Question

OK, so I'm attempting to write a Haskell function which efficiently detects all the factors of a given Int. Based off of the solution given in this question, I've got the following:

-- returns a list of the factors of n
factors         ::  Int -> [Int]
factors n       =   sort . nub $ fs where
                        fs  =   foldr (++) [] [[m,n `div` m] | m <- [1..lim+1], n `mod` m == 0]
                        lim =   sqrt . fromIntegral $ n

Sadly, GHCi informs me that there is No instance for (Floating Int) in the line containing lim = etc. etc.

I've read this answer, and the proposed solution works when typed into GHCi directly - it allows me to call sqrt on an Int. However, when what appears to be exactly the same code is placed in my function, it ceases to work.

I'm relatively new to Haskell, so I'd greatly appreciate the help!

Answer 1

When you check the type of sqrt

Prelude> :t sqrt 
sqrt :: Floating a => a -> a

It requires a floating number. It doesn't work in ghci. You might have tried calling it on a number and ghci would have inferred the type as Float.

Prelude> let a = 1 :: Int

Prelude> sqrt a

<interactive>:5:1:
    No instance for (Floating Int) arising from a use of `sqrt'
    Possible fix: add an instance declaration for (Floating Int)
    In the expression: sqrt a
    In an equation for `it': it = sqrt a

Now coming back to your code. The problem is in the expression [1 .. lim + 1]. Arithmetic sequences can only be applied on values of type Enum a => a. Since lim is of type Floating a => a, you need to convert it back to Integral a => a by either taking the ceiling or floor. Just for information, Integral class instance constraints the type to have an Enum instance too.

Answer 2

You do need fromIntegral to cast (n :: Int) to Double. Then you need the Double you get from sqrt to be converted back to Int. You will need to round, and since you use (lim+1) I can see you need to round down, using floor:

isqrt :: Int -> Int
isqrt i = let d :: Double
              d = fromIntegral i
          in floor (sqrt d)

Now you can use this instead of sqrt in your code.