Function to Calculate `log` of Integer

Question

I wrote the following function.

f :: Integer -> Integer
f x = if (odd x) then 0 else (floor . logBase 2) x

But the following compile-time error occurs:

F.hs:2:31: 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 . logBase 2 In the expression: (floor . logBase 2) x

F.hs:2:39: No instance for (Floating Integer) arising from a use of logBase' Possible fix: add an instance declaration for (Floating Integer) In the second argument of(.)', namely `logBase 2' In the expression: floor . logBase 2 In the expression: (floor . logBase 2) x Failed, modules loaded: none.

How can I properly write the above function?

Answer 1

This will be a tad long, as I would like to not just give you code that works, but explain the issue in depth so you can understand GHC's type errors better.

As already answered briefly (and as the type error tries its best to tell you, although it is certainly not clear enough), in order to use logBase x y, the two parameters x and y must both be instances of the "floating point" typeclasses.

In particular, logBase is a method of the Floating typeclass (from the Prelude's documentation):

class Fractional a => Floating a where Source
    logBase :: a -> a -> a 

We also find, also from the Prelude:

class (Real a, Fractional a) => RealFrac a where Source
    floor :: Integral b => a -> b

That is, in order to use the function (floor . logBase), we need two parameters which are Fractional (since logBase requires this), and Real (since floor requires both). The merger of these two is defined as RealFrac, and that's exactly what GHC is complaining you failed to provide it (in your function's type declaration).

Why is it complaining? From the Prelude we find the following instance declarations for RealFrac. Note that "RealFrac Integer" is missing:

RealFrac Double  
RealFrac Float   
RealFrac CDouble     
RealFrac CFloat  
Integral a => RealFrac (Ratio a)     
HasResolution a => RealFrac (Fixed a)   

The way Haskell works, is that if you give it an integer literal (consecutive digits without a decimal point), it will assume that it belongs to the Integral typeclass (and will try to figure out whether to make it an Integer or Int implicitly), but it will never implicitly promote an integer literal to one of the Fractional classes (including RealFrac). Since there is no "RealFrac Integer" line, this means that you can't expect Haskell to compile your code.

You are telling Haskell that you will give it Integral instances by your explicit type declaration (this is one of the reasons why these are generally a good idea -- Haskell would have quietly accepted your function declaration otherwise, only to throw compilation errors in the client functions that use it):

f :: Integer -> Integer

The solution is to promote your integers by using the following function (which converts Integrals into any compatible Number types):

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

Floor performs the conversion in the opposite direction (from Fractional to Integral), as shown by its type.

In conclusion you need to simply say

f :: Integer -> Integer
f x = if (odd x) then 0 else (floor . logBase 2.0 . fromIntegral) x

Note the fromIntegral call to make the type of the parameter compatible with what the compiler expects, as well as the use of 2.0 (a Fractional literal) for the base.

Answer 2

Beware that logBase requires conversion to a Floating type, which may lead to erroneous results.

f :: Integer -> Integer
f x = if (odd x) then 0 else (floor . logBase 2.0 . fromIntegral) x

λ> f (2^99999)
    179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

This happens because (2^99999 :: Double) = Infinity, and the floor Infinity apparently evaluates to... something surprising.

The integer-logarithms package provides an integerLog2 function which works better:

λ> import Math.NumberTheory.Logarithms

λ> integerLog2 (2^99999)
    99999
it :: Int

The function in integer-logarithms is just a thin wrapper around integer-gmp, so you could also use that directly:

λ> :set -XMagicHash

λ> import GHC.Exts

λ> import GHC.Integer.Logarithms

λ> I# (integerLog2# (2^99999))
    99999
it :: Int

Note that these functions return a value even if the result is not a power of two:

λ> integerLog2 1023
    9