How would you declare the types of these functions in Haskell?

Question

So I'm learning about Haskell at the moment, and I came across this question:

The type of a function f is supposed to be a->[a]->a. The following definitions of f are incorrect because their types are all different from a->[a]->a:

i. f x xs = xs
ii. f x xs = x+1
iii. f x xs = x ++ xs
iv. f x (y:ys) = y

My answers as I see it are:

i) f :: a -> a -> a

This is because x or xs can be of any value and is not a list as it does not contain the ':' operator.

ii) f :: Int -> a -> Int

This is because the + operator is used on x, meaning x is of type Int.

iii) f :: Eq a => a -> a -> a

The ++ operators are used, therefore in order to concatenate they must be of the same type..?

iv) f :: a -> [a] -> a

f returns an element from the list.

The last one is definitely wrong, because it can't be of type a -> [a] -> a. Are there any others I did wrong, and why? I'm hoping I can fully understand types and how to find out the types of functions.

Answer 1

i. f x xs = xs

(...)

i) f :: a -> a -> a

Although this can be a type signature, you make it too restrictive. The function takes two parameters x and xs. Initially we can reason that x and xs can have different types, so we say that x :: a, and xs :: b. Since the function returns xs, the return type is b as well, so the type is:

f :: a -> b -> b
f x xs = xs

ii. f x xs = x+1

(...)

ii) f :: Int -> a -> Int

Again you make the function too restrictive. Let us again assume that x :: a and xs :: b have different types. We see that we return x + 1 (or in more canonical form (+) x 1. Since (+) has signature (+) :: Num c => c -> c -> c (we here use c since a is already used), and 1 has signature 1 :: Num d => d, we thus see that we call (+) with x and 1, as a result we know that a ~ c (a and c are the same type), and c ~ d, so as a result we obtain the signature:

f :: Num c => c -> b -> c
f x xs = x+1

iii. f x xs = x ++ xs

(...)

iii) f :: Eq a => a -> a -> a

This is wrong: we here see that f has two parameters, x :: a and xs :: b. We see that we return (++) x xs. Since (++) has signature (++) :: [c] -> [c] -> [c], we thus know that a ~ [c] and b ~ [c], so the type is:

f :: [c] -> [c] -> [c]
f x xs = x ++ xs

iv. f x (y:ys) = y

(...)

iv) f :: a -> [a] -> a

This is again too restrictive. Here we see again two parameters: x and (y:ys). We first generate a type a for x :: a, and (y:ys) :: b, since the pattern of the second parameter is (y:ys), this is a list constructor with as parameters (:) :: c -> [c] -> [c]. As a result we can derive that y :: c, and ys :: [c], furthermore the pattern (y:ys) has type [c]. Since the function returns y, we know that the return type is c, so:

f :: a -> [c] -> c
f x (y:ys) = y

Note: you can let Haskell derive the type of the function itself. In GHCi you can use the :t command to query the type of an expression. For example:

Prelude> f x (y:ys) = y
Prelude> :t f
f :: t1 -> [t] -> t

Answer 2

i) f :: a -> a -> a

f x xs = xs

This is because x or xs can be of any value and is not a list as it does not contain the ':' operator.

True, but it also does not have to be of the same type! So, it's actually f :: a -> b -> b.

ii) f :: Int -> a -> Int

f x xs = x+1

This is because the + operator is used on x, meaning x is of type Int.

Correct. (Actually, in Haskell we get Num b => b -> a -> b which generalized the Int to any numeric type, but it's not that important.)

iii) f :: Eq a => a -> a -> a

f x xs = x ++ xs

The ++ operators are used, therefore in order to concatenate they must be of the same type..?

True, but they must be lists. Also, Eq is only needed if you use == or something which compares values.

Here, f :: [a] -> [a] -> [a].

iv) f :: a -> [a] -> a

f x (y:ys) = y

f returns an element from the list.

The type of x does not have to be the same. We get f :: b -> [a] -> a.