functions not in type classes

[Rijk-Jan van Haaften]

>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