Why does Haskell want this function's argument to have the type classes (RealFrac x, Integral x) when it only needs to be Integral x?

Question

I'm trying to write some code that does a complete factorization of an integer by trial division. This code seems like it ought to work:

findAFact :: Integral x => x -> x
findAFact x = searchInts [2, 3..] x where
    searchInts (int:ints) div
        | div `mod` int == 0 = int
        | otherwise          = searchInts ints div

completeFacts :: Integral x => x -> [x]
completeFacts x = tryForFact [] x where
    tryForFact fs x = if x == 1
                      then fs
                      else let fact = findAFact x
                           in tryForFact (fact:fs) (floor ((fromIntegral x) / fact))

but if I try to compile this I get the following error:

Could not deduce (RealFrac x) arising from a use of 'tryForFact'
from the context (Integral x)
  bound by the type signature for
             completeFacts :: Integral x => x -> [x]
  at 5.hs:26:18-39
Possible fix:
  add (RealFrac x) to the context of
    the type signature for completeFacts :: Integral x => x -> [x]
In the expression: tryForFact [] x
In an equation for 'completeFacts':
    completeFacts x
      = tryForFact [] x
      where
          tryForFact fs x
            = if x == 1 then
                  fs
              else
                  let ... in tryForFact (fact : fs) (floor ((fromIntegral x) / fact))

If I remove the type signature from completeFacts and try loading it into GHCI, the interpreter loads the file and supplies the type signature (RealFrac x, Integral x ) => x -> [x] for completeFacts, but then complains when I try to use completeFacts that there's no way to show it because its type is ambiguous in the context of show. That makes sense to me because it seems like there would be a clear way to display x as a RealFrac or an Integral, but not both.

This seems to be the offending code:

...
in tryForFact (fact:fs) (floor ((fromIntegral x) / fact))

I'm confused because I'd imagine passing x through fromIntegral and then passing the result of the division into floor would give me an Integral back. I don't see why Haskell still thinks x also needs to have the type class RealFrac. Why does Haskell insist on this, and how can I rewrite completeFacts so that x can just be an Integral?

Thanks!

Answer 1

It's because you didn't convert fact to a RealFrac before doing division:

in tryForFact (fact:fs) (floor (fromIntegral x / fromIntegral fact))

You've said that fact = findAFact x, which has type Integral x => x, but you're using it in a division with /, so it thinks it needs to satisfy both Integral and RealFrac.

What would actually be better is to just use div instead (I've also cleaned up the code a little bit so that it's easier to read and you aren't shadowing an existing binding for x):

completeFacts :: Integral x => x -> [x]
completeFacts x = tryForFact [] x
    where
        tryForFact fs 1 = fs
        tryForFact fs y = let fact = findAFact y
                          in tryForFact (fact:fs) (y `div` fact)