Understanding type-related Haskell errors when using sqrt

Question

I've been reading Learn You a Haskell for a few days (chaps 1-6) and there are several things, even in the land of newbies, which are not clear to me.

For instance, I've been trying to implement a script to solve this classic problem of finding the largest prime factor of an integer.

I'm pretty sure my approach,

• check if the number is a square and return its square root if so,
• otherwise search for divisors downward from its square root, scanning only odd numbers,

is probably not the right one, is plainly wrong, as pointed out in the answer and the comments (I hope I would have realized this myself, if I had been able to write a compilable code), but at least it's being a chance to practice Haskell's syntax and not only.

The only commented line is the one with which I'm having issue. What is "strange" to me, is that the errors are about the two lines just after that, whereas everything works fine if I change the lamda to something which does not use both x and e (except that the result is wrong, clearly).

largestprime x
  | isSquare = srx
  | otherwise = head $ filter (\e -> x `mod` e == 0) lst --Lambda
    where intsqrt = floor . sqrt
          isSquare = sqrt x == fromInteger(intsqrt x)
          srx = intsqrt x
          lst = [i,i-2..]
            where i = if odd srx then srx else srx - 1

My understanding is that something is wrong with the types that are deduced for e and x, however the error is not very helpful, given my current level:

Main.hs:59:21: error:
    • No instance for (RealFrac Integer) arising from a use of ‘floor’
    • In the first argument of ‘(.)’, namely ‘floor’
      In the expression: floor . sqrt
      In an equation for ‘intsqrt’: intsqrt = floor . sqrt
   |
59 |     where intsqrt = floor . sqrt
   |                     ^^^^^

Main.hs:59:29: error:
    • No instance for (Floating Integer) arising from a use of ‘sqrt’
    • In the second argument of ‘(.)’, namely ‘sqrt’
      In the expression: floor . sqrt
      In an equation for ‘intsqrt’: intsqrt = floor . sqrt
   |
59 |     where intsqrt = floor . sqrt
   |                             ^^^^

Main.hs:60:22: error:
    • No instance for (Floating Integer) arising from a use of ‘sqrt’
    • In the first argument of ‘(==)’, namely ‘sqrt x’
      In the expression: sqrt x == fromInteger (intsqrt x)
      In an equation for ‘isSquare’:
          isSquare = sqrt x == fromInteger (intsqrt x)
   |
60 |           isSquare = sqrt x == fromInteger(intsqrt x)
   |                      ^^^^^^
Failed, no modules loaded.

Concerning e, it is an element of lst, which is a list whose elements are of the same type as srx, which is the type in output from floor, which based on :t floor seems to be Integral. So maybe I just have to define the type of largestprime appropriately?

I've seen some questions exist already on the topic, like this one or this one. However I'm a bit confused at the moment.

Besides receiving help so that I can solve the problem, it'd be also nice to receive some advices on how to read those errors, which at the moment are close to arabic for me.

Answer 1

Having defined your function, check its type right away:

> :t largestprime
largestprime :: (RealFrac c, Integral c, Floating c) => c -> c

Here's the problem right there: its type demands an input value's type to be an Integral and also a Floating and RealFrac type at the same time.

Why? Because the same x is used as input to mod and sqrt (and, inside intsqrt, to floor):

> :t mod
mod   ::  Integral a              => a -> a -> a

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

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

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

Why did it compile? Because theoretically you could define - in some other module - a type which is an instance of all the typeclasses in the constraint, and use this function with it.

The errors No instance for (RealFrac Integer) and No instance for (Floating Integer) just mean that you haven't done so (your Integral has defaulted to Integer).

Answer 2

There are a few places where you seem to be a little confused in whether you are using an Integral type or a RealFrac one. A good technique to make sure you don't confuse yourself is to use type annotations.

To start off, what is the input and output of the function you are creating, largestprime? IMO, it should be integral types on both ends, since it doesn't make sense to talk about prime factors if you have non-integers.

largestprime :: Integral a => a -> a

So, then we want to find the square root of the input. Unfortunately, sqrt doesn't belong to Integral, but to Floating (just run :i sqrt in GHCi). What we can do instead is use the fromIntegral function, which has the following type signature:

fromIntegral :: (Integral a, Num b) => a -> b

So in order to find the square root of our integer, we have to use sqrt . fromIntegral. To check if the number is a square, we can do

isSquare = let y = fromIntegral x in sqrt y == fromIntegral (floor $ sqrt y)

or

isSquare = let y = fromIntegral x in ceiling (sqrt y) == floor (sqrt y)

So far, we've got the "is a perfect square" case figured out and working. Next up is the rest.

The list of candidates for us to check for divisibility is [i, i-2 ..] for i being as you've defined. So, following your code, we first filter for those that divide x:

filter (\n -> x `mod` n == 0) [i, i-2, ..]

We want the first number that matches our criteria (that is, wasn't filtered). So, just as you did, we take the head:

head $ filter (\n -> x `mod` n == 0) [i, i-2, ..]

The whole function is:

largestprime :: Integral a => a -> a
largestprime x  | isSquare  = root
                | otherwise = head $ filter (\n -> x `mod` n == 0) [i, i-2 ..]
    where   isSquare = let y = fromIntegral x in ceiling (sqrt y) == floor (sqrt y)
            root     = floor $ sqrt $ fromIntegral x
            i        = if odd root then root else root - 1

And now we've got a function that compiles successfully. I didn't really cover this in this answer, but a tip to solving GHC errors is to go from the bottom — always fix the last error first. In your case, you would've seen right off that sqrt x complains that x isn't a Floating type.

I just think it's also worth quickly mentioning that your algorithm does not do what you think it does. Sure, it will return one of its factors, but it's not necessarily prime (largestprime 36 gives 6, which isn't prime).