How to write a function signature for Num -> Fractional?

Learn
#1

I am writing a function for the harmonic number series. The recursive implementation is straight forward:

harmonic 1 = 1 / 1
harmonic n = harmonic (n-1) + (1 / n)

Problem for me is the type signature. I came up with:

harmonic :: (Num a, Fractional p) => a -> p

But the language server complains with “Could not deduce (Fractional a) arising from a use of ‘harmonic’”. It suggests instead

harmonic :: (Eq p, Fractional p) => p -> p

Why’s that? From my understanding the recursive definition has in the function arguments only Integers, so my beginner’s brain thinks (Num a) should work here…

1 Like
#2

Fractional already provides Num:

λ> :i Fractional
type Fractional :: * -> Constraint
class Num a => Fractional a where                   ← here
  (/) :: a -> a -> a
  recip :: a -> a
  fromRational :: Rational -> a

You then need Eq p for pattern matching reasons.

The error you pasted (Could not deduce Fractional…) only happens if you write a type signature like this:

harmonic :: (Eq a, Num a) => a -> a

So maybe you forgot to save your file before reloading ghci or similar!

#3

One thing you should also remember is that Haskell does absolutely no automatic casting, so the input type will be the same as the output type unless you write an explicit cast which is most commonly done using fromIntegral or realToFrac.

You could do that like this:

harmonic :: (Integral a, Fractional b) => a -> b
harmonic 1 = 1 / 1
harmonic n = harmonic (n - 1) + 1 / fromIntegral n

Note how we need the Integral a constraint instead of Num a to be able to do the casting.

Also, 1 / 1 is equal to 1 so you could just write that.

3 Likes
#4

Thanks for the explanation!

The aspect I was not aware of is:

So type inference for input types works (at least in this example) backwards from the output type to the input type. And the output type can be determined here by the / operator.

Makes more sense now. :slight_smile:

Would you say, it is recommend in this case to do the casting in order to narrow the input to Integers?

#5

Yeah, the type inference is really going backwards, but I don’t think it is all the way from the output back to the input. The real critical part of the inference is the division operator: (/) :: Fractional a => a -> a -> a. There you see that the input and output types to this operation must also be fractional. That information gets propagated backwards to the input and forwards to the output.

Your function is only useful on natural number inputs that are larger than 1, otherwise it will get stuck in an infinite loop because it will miss the harmonic 1 base case. So limiting the input to at least instances of type Integral helps prevent some bad inputs. And I think it also makes sense that you can call this function with non-fractional types like Int.

One disadvantage is that the fromIntegral conversion between for example Int and Double is not completely free, so it will probably be slightly slower.

Another alternative is to make the base case stronger:

harmonic n
  | n <= 1 = 1
  | otherwise = harmonic (n - 1) + 1 / n

But this probably gives useless results on non-integer inputs too.

Also, I want to note that you can generalize the function by having the base case at n = 0 instead of n = 1:

harmonic 0 = 0
harmonic n = harmonic (n - 1) + 1 / fromIntegral n

That makes it behave the same as an implementation using sum:

harmonic n = sum [1 / fromIntegral m | m <- [1..n]]

Note that if n = 0 then the list [1..n] is an empty list, so the result of the list comprehension is also an empty list and finally the sum of the empty list is 0.