How can two similar functions have different polymorphic types in Haskell?

Question

Im pretty much new to Haskell, so if Im missing key concept, please point it out.

Lets say we have these two functions:

fact n
     | n == 0 = 1
     | n > 0  = n * (fact (n - 1))

The polymorphic type for fact is (Eq t, Num t) => t -> t Because n is used in the if condition and n must be of valid type to do the == check. Therefor t must be a Number and t can be of any type within class constraint Eq t

fib n
    | n == 1 = 1
    | n == 2 = 1
    | n > 2  = fib (n - 1) + fib (n - 2)

Then why is the polymorphic type of fib is (Eq a, Num a, Num t) => a -> t?

I don't understand, please help.

Answer 1

Haskell always aims to derive the most generic type signature.

Now for fact, we know that the type of the output, should be the same as the type of the input:

fact n | n == 0 = 1
       | n > 0  = n * (fact (n - 1))

This is due to the last line. We use n * (fact (n-1)). So we use a multiplication (*) :: a -> a -> a. Multiplication thus takes two members of the same type and returns a member of that type. Since we multiply with n, and n is input, the output is of the same type as the input. Since we use n == 0, we know that (==) :: Eq a => a -> a -> Bool so that means that that input type should have Eq a =>, and furthermore 0 :: Num a => a. So the resulting type is fact :: (Num a, Eq a) => a -> a.

Now for fib, we see:

fib n | n == 1 = 1
      | n == 2 = 1
      | n > 2  = fib (n - 1) + fib (n - 2)

Now we know that for n, the type constraints are again Eq a, Num a, since we use n == 1, and (==) :: Eq a => a -> a -> Bool and 1 :: Num a => a. But the input n is never directly used in the output. Indeed, the last line has fib (n-1) + fib (n-2), but here we use n-1 and n-2 as input of a new call. So that means we can safely asume that the input type and the output type act independently. The output type, still has a type constraint: Num t: this is since we return 1 for the first two cases, and 1 :: Num t => t, and we also return the addition of two outputs: fib (n-1) + fib (n-2), so again (+) :: Num t => t -> t -> t.

Answer 2

The difference is that in fact, you use the argument directly in an arithmetic expression which makes up the final result:

fact n | ...  = n * ...

IOW, if you write out the expanded arithmetic expression, n appears in it:

fact 3  ≡  n * (n-1) * (n-2) * 1

This fixes that the argument must have the same type as the result, because

(*) :: Num n => n -> n -> n

Not so in fib: here the actual result is only composed of literals and of sub-results. IOW, the expanded expression looks like

fib 3  ≡  (1 + 1) + 1

No n in here, so no unification between argument and result required.

Of course, in both cases you also used n to decide how this arithmetic expression looks, but for that you've just used equality comparisons with literals, whose type is not connected to the final result.

Note that you can also give fib a type-preservig signature: (Eq a, Num a, Num t) => a -> t is strictly more general than (Eq t, Num t) => t -> t. Conversely, you can make a fact that doesn't require input- and output to be the same type, by following it with a conversion function:

fact' :: (Eq a, Integral a, Num t) => a -> t
fact' = fromIntegral . fact

This doesn't make a lot of sense though, because Integer is pretty much the only type that can reliably be used in fact, but to achieve that in the above version you need to start out with Integer. Hence if anything, you should do the following:

fact'' :: (Eq t, Integral a, Num t) => a -> t
fact'' = fact . fromIntegral

This can then be used also as Int -> Integer, which is somewhat sensible.

I'd recommend to just keep the signature (Eq t, Num t) => t -> t though, and only add conversion operations where it's actually needed. Or really, what I'd recommend is to not use fact at all – this is a very expensive function that's hardly ever really useful in practice; most applications that naïvely end up with a factorial really just need something like binomial coefficients, and those can be implemented more efficiently without a factorial.