Problems getting a list of number dividers in Haskell

Question

This is not a duplicate question . Read below ...

I declare the following function:

divisors x = [(a, x/a) | a <- [2..(sqrt x)], x `mod` a == 0] 

What I want to get is divisors from x : a list of tuples that will contain (n, k) , like n * k = x

Example:

 > divisors x [(1,10), (2, 5)] 

Why does the above code not work?

This gives me an error:

 *Main> divisors 10 <interactive>:1:0: Ambiguous type variable `t' in the constraints: `Floating t' arising from a use of `divisors' at <interactive>:1:0-10 `Integral t' arising from a use of `divisors' at <interactive>:1:0-10 Probable fix: add a type signature that fixes these type variable(s) 

I tried manually setting the function signature without success ...

Answer 1

The sqrt task returns a Floating a , and you really want to get integers when looking for divisors. You can turn Floating a into Integral a using ceiling , floor or round . I will use ceiling , as I'm not sure if using floor or average will not skip the divider.

The sqrt function also accepts only a floating-point number, so you have to convert the integer to a floating-point number before you give it (this can be done using fromIntegral ).

In addition, you use / , which also works with floating numbers. Using a div better because it works with integers (rounding if necessary).

 divisors x = [(a, x `div` a) | a <- [2..(ceiling $ sqrt $ fromIntegral x)], x `mod` a == 0] 

At the same time, divisors 10 will give [(2,5)] (your code stops the case (1,10) ) - I assume this was intentional). Unfortunately, you will get duplicates, for example divisors 12 will return [(2,6),(3,4),(4,3)] , but it should not be too difficult to fix if this is a problem.

Answer 2

You can see the problem if you specify the type:

  divisors :: (Integral t, Floating t) => t -> [(t, t)] 

and then check what Integral and Floating :

  Prelude> :info Floating class Fractional a => Floating a where instance Floating Float -- Defined in GHC.Float instance Floating Double -- Defined in GHC.Float 

and

  Prelude> :info Integral class (Real a, Enum a) => Integral a where instance Integral Integer -- Defined in GHC.Real instance Integral Int -- Defined in GHC.Real 

therefore, it cannot be either Int, Integer, Float, or Double. You have problems...

Fortunately, we can convert between types, so while sqrt requires a floating point, and mod requires an integral (btw, rem faster), we can either, for example, do away with floating point division

  divisors :: Integer -> [(Integer, Integer)] divisors x = [(a, x `div` a) | a <- [2..ceiling (sqrt (fromIntegral x))], x `rem` a == 0] > divisors 100 [(2,0),(4,0),(5,0),(10,0)] 

However, you need to think a lot about what you really want to do when converting integer types to floating points, via sqrt ...

Answer 3

In Haskell, integer division and fractional division are different operations and have different names. The slash operator, / , is used for fractional division. Integer division is performed using div or quot (the difference between them is related to the behavior in the presence of negative numbers).

Try replacing x/a with

 x `quot` a 

instead.

A compiler error tells you exactly this: you treat the type sometimes as an integer (using mod ), and sometimes as a fractional number (using / ), and it is not sure how to choose a type that acts like both.

You will have a similar problem with sqrt if it is sorted. Again, you need to be consistent as to whether your types are integers or (in this case) floating point. In order to find possible dividers, it should be enough that the distance to the largest integer is less than a floating point, so consider using floor (sqrt (fromIntegral x))) . fromIntegral converts x (which must be an integral type) to another type - in this case, the default is Double . Then floor converts the Double result to an integral type.

Answer 4

Instead of using the square root to anchor the search, you can enable range comprehension over an infinite list and use takeWhile to stop the search when the remainder is greater than the divisor:

 divisors x = takeWhile (uncurry (<=)) [(a, x `div` a) | a <- [1..], x `mod` a == 0] > divisors 100 [(1,100),(2,50),(4,25),(5,20),(10,10)] 

Note: your original example shows (1,10) as one of the divisors of 10 , so I started to understand with 1 instead of 2 .

Hmm, this does a search outside the square root until it reaches the next factor above.

How about this:

 divisors x = [(a, x `div` a) | a <- takeWhile ((<= x) . (^2)) [1..], x `mod` a == 0]