Haskell - Couldn't match expected type ‘b’ with actual type ‘a’

Question

Just started learning Haskell and Im trying to implement a max function to find the max of a list recursively

max' :: (Num b) => [a] -> b
max' [] = 0
max' (x:xs)
    | x > max' xs = x
    | otherwise = max' xs

but am getting the error when trying to compile

Couldn't match expected type ‘b’ with actual type ‘a’ ‘a’ is a rigid type variable bound by the type signature for: max' :: forall b a. (Num b, Num a) => [a] -> b at implementingFunctions.hs:5:1-34 ‘b’ is a rigid type variable bound by the type signature for: max' :: forall b a. (Num b, Num a) => [a] -> b at implementingFunctions.hs:5:1-34

Can anyone help me understand whats wrong ?

Answer 1

max' takes as input (based on the signature) an [a]: a list of as. But you return a b. That means that you have written that - regardless of the type of the elements in the list - we can pick whatever type b as output we want, as long as it is a Num b. But that does not makes sense. If we enter a list of strings, we can of course calculate the "largest string" (lexicographically), but we can not return that as a Num.

Another problem is that you use the (>) :: Ord a => a -> a -> Bool function (as a guard). But you do not specify in the function signature that the type of the input elements must be an instance of the Ord typeclass. So you can not compare the elements.

The minimal fix is to restrict the input type to be b as well:

max' :: (Ord b, Num b) => [b] -> b
max' [] = 0
max' (x:xs)
    | x > max' xs = x
    | otherwise = max' xs

That being said, it does not make much sense to return an 0 in case we provide an empty list. That would result in the weird fact that max [] is actually greater than max [-1]: usually we expect the maximum of a superset to be greater than or equal to the maximum of the set.

So the max' function can probably be best seen as a non-total function: a function for which not every input results in output. In this case the empty list does not.

We can rewrite it to error with:

max' :: Ord b => [b] -> b
max' [] = error "Empty list"
max' [x] = x
max' (x:xs@(_:_))
    | x > max' xs = x
    | otherwise = max' xs

So now there are three patterns: (1) the empty list, (2) the singlton list, and (3) the list with at least two elements.

Writing errors however is not always a good way to handle non-total functions, since one can not see in the type signature that a function is non-total. Another wa to do it is use Maybe b as return type. This will be a Nothing in case there is no maximum, or a Just x in case there is one:

max' :: Ord b => [b] -> Maybe b
max' [] = Nothing
max' [x] = Just x
max' (x:xs@(_:_))
    | y <- max' xs = max x y
    | otherwise = Nothing

Or shorter:

max' :: Ord b => [b] -> Maybe b
max' [] = Nothing
max' [x] = Just x
max' (x:xs@(_:_)) = fmap (max x) (max' xs)

For example:

Prelude> max' []
Nothing
Prelude> max' [1,4,2,5]
Just 5
Prelude> max' [-3]
Just (-3)