Thanks. I am quite convinced actually (no sarchasm involved).
I'm sorry I didn't follow the discussion. From the last few mails, it seems that the difference between fully polymorphic functions like map, id, filter etc. on one hand and overloaded functions on the other hand is not clear:
the goal of type class is to allow overloading of function, so for example id x = x is not subject to overloading => no use to put it in a type class.
Because it doesn't do anything?
<examples by Dave showing that id is useful>
There are fairly simple rules to decide whether or not a function should be in a type class. Notes: 1. The type of x is NOT needed/used <=> there is NO pattern match on x 2. The type of x is needed/used <=> there is AT LEAST ONE pattern match on x 3. Recursive checks are necessary sometimes. This will become clear in the filter example A. In a type class Rule: Put a function f in a type class if and only if For some argument x: (x ranges over more than one type) and (the function needs the type of x in order to do its work) B. Not in a type class Rule: Do NOT put a function f in a type class if (and only if) For each argument x of f: (f doesn't use the type of x) or (x doesn't range over multiple types (ie has a single type)) If someone has a better definition, I would be glad to hear it. I will explain the rules using a few examples. id :: a -> a id x = x There is just one argument to check: x Property: there is no pattern match on x We conclude that rule B applies The check that rule A doesn't apply is left as an exercise to the reader. filter :: (a -> Bool) -> [a] -> [a] filter p [] = [] filter p (x:xs) | p x = x : filter p xs | otherwise = filter p xs there are two arguments: the function p and the list p is just passed around and it can take any type satisfying (a -> Bool) like (Int -> Bool), (Char -> Bool) etc. Now note 3 (above) comes up. The list is a difficult case. Does it range over multiple types or doesn't it? filter takes as second argument a list, and only a list. No other structure is allowed. Therefore, it doesn't take a range of types there. It takes a single type. But because it is unpacked using pattern matching, we have to check the properties of its components x and xs. The type of x is not used. The list xs is pattern-matched (implicit in "filter p xs") but again, the list itself is only a single structure. The function map is left as an exercise to the reader. Quite regularly we have to work with datatypes other than lists. For example binary trees with elements in the nodes: data BinTree a = Node a (BinTree a) (BinTree a) | Leaf To convert a (BinTree a) to a (BinTree b) by applying a function f :: a -> b on each element, we need a function very similar to map. Unfortunately, map only accepts lists, so we have to write our own function. Of course the technical behaviour is quite different, but for the programmer the behaviour is very similar. For this situation we have fmap :: (a -> b) -> f a -> f b For the type f (of kind * -> *) we can take [] (note that "x :: [] a" is the same as "x :: [a]") or BinTree or some other collection type. However, not an arbitrary type, since the technical implementation of fmap for [] differs from the one for BinTree. Therefore, we have no uniform implementation working for an arbitrary type f. Note the requirement in A (the function needs the type of x in order to do its work) In this case, we need the type of f to choose the right implementation. Thus, we have to put in in a class: class Functor f where fmap :: (a -> b) -> f a -> f b For Maybe (a collection type with only two choices: no elements or one element) we can write: instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just x) = Just (f x) For lists we have (the usual map) instance Functor [] where fmap f [] = [] fmap f (x:xs) = f x : fmap f xs For BinTree we have instance Functor BinTree where fmap f Leaf = Leaf fmap f (Node x t1 t2) = Node (f x) (fmap f t1) (fmap f t2) If we try "fmap (+3) 5", the compiler will tell us that 5 is and Int, and fmap needs Maybe a, [a] or BinTree a. In the three implementations, you see that the second argument of fmap ranges over three different types, while it needs the type of that argument to perform the map. I hope this clears up a few difficulties. Rijk-Jan