Haskell-(Type declaration) what is "a"?

Question

This is perhaps a very basic question, but, nevertheless, it does not seem to have been covered on SO.

I recently took up Haskell and up until now type declarations consisted of mostly the following:

Int
Bool
Float
etc, etc

Now I am getting into lists and I am seeing type declarations that use a, such as in the following function that iterates through an associative list:

contains :: Int -> [(Int,a)] -> [a]
contains x list = [values | (key,values)<-list, x==key]

Can someone provide an explanation as to what this a is, and how it works? From observation it seems to represent every type. Does this mean I can input any list of any type as parameter?

Tatiana

Answer 1

Yes, you're right, it represents "any type" - the restriction being that all as in a given type signature must resolve to the same type. So you can input a list of any type, but when you use contains to look up a value in the list, the value you look up must be the same type as the elements of the list - which makes sense of course.

Mindi

Just as importantly, a is not special: any lower-case identifier means that. It's a type variable, and it's possible for multiple different type variables to exist in the same signature. For example, const :: a -> b -> a takes in two arguments, each of any type at all, and returns a value with the same type as its first input. – Weasel

I see, its very generic-like. So, I guess, in most cases, a would generally represent elements that my function doesn't really use, or change, too much. – Tatiana

@Bolboa: Yes, it is closely related to the concept of "generics" in other languages. And yes, if the type is completely generic, there is little you can do directly to the value itself. Haskell does have a way of giving more information about the type (for example, "can be compared for equality", "can be printed", "can be treated like a number"), which allows you to do more processing on the values; if you're interested in this then look up "classes" in the documentation or a tutorial. – Mindi

@Bolboa Indeed, for instance a function f :: [a] -> [a] can not produce in its output anything which was not present in its input, since it is "generic". For instance f [1,2] can not produce [2,3]. Similarly, your contains function can not output anything new, and you can see that just from the type, without even looking at the code. – Alexandrine

What @Alexandrine describes is called 'the parametricity property', if you're looking for a keyword to Google. – Kobarid

Answer 2

In Haskell, uppercase types are concrete types (Int, Bool) or type constructors (Maybe, Either) while lowercase types are type variables. A function is implicitly generic in all the type variables it uses, so this:

contains :: Int -> [(Int, a)] -> [a]

Is shorthand for this*:

contains :: forall a. Int -> [(Int, a)] -> [a]

In C++, forall is spelled template:

template<typename a>
list<a> contains(int, list<pair<int, a>>);

In Java and C#, it’s spelled with angle brackets:

list<a> contains<a>(int, list<pair<int, a>>);

Of course, in these languages, generic type variables are often called T, U, V, while in Haskell they’re often called a, b, c. It’s just a difference of convention.

* This syntax is enabled by the -XExplicitForAll flag in GHC, as well as other extensions.

Censorship

Much more useful: -XScopedTypeVariables. Also, C++ templates seem to be inherently rather different from either Haskell/ML/... type variables or even Java Generics. – Mailbox