[Haskell-cafe] Monad for Set?

[Ronald Guida]

Hi,

I'm pondering, is it possible to define a Set monad analogous to the 
List monad?

My thinking is as follows:
 *  "fmap f x" would apply f to each element in a set x
 *  "return x" would create a singleton set {x}
 *  "join x", where x is a set of sets: x = {x1, x2, ... xn},
              would form their union (x1 U x2 U ... U xn)

The advantage of Set over List is that duplicate elements would be
removed automatically.

There is just one /slight/ problem: In order to implement set
operations, I need to be able to test elements for equality; that is,
I need to impose the restriction (Eq a) => Set a.  This is a problem
because return really needs to work for any type; I have no way to
guarantee (Eq a).

In my search for answers, I came across "restricted monads".  I don't
like the idea of restricting the types I can return, and here's why.
Suppose I had a way to impose (Eq a).  Then I start to wonder:

 * What happens when I use a monad transformer like "StateT s Set a"
   or "ContT r Set a", but the types s and r are not equatable?

 * What happens when I want to define the monad transformer SetT
   because I need to put the IO monad inside it?

In both cases, I feel I'm screwed if I really have to impose the
constraint (Eq a) => Set a.

This leads me think of a different solution: What if I could define a
Set monad that's smart enough to "know", for any type a, whether or
not (Eq a) holds, and degenerate to a blind list if the elements can't
be equated.  Ultimately, what I would need is a way to overload "join"
(or "bind") with two different implementations, one for types that
satisfy (Eq a), and another implementation for all other types.

In my searching so far, I found ways to overload a function when all
overloads share a common typeclass, and I have found ways to overload
a function for disjoint types, provided that every type to be overload
is an instance of some typeclass.  All of the methods I have found so
far are deficient in the sense that there is no way to provide a
default implementation for types that don't fit into any typeclass.  I
have not been able to find a way to overload a function such that one
implementation works for a special class of types, and another
implementation works for *all* other types.

Question: Is it possible to define join :: [[a]] -> [a], with
(1) a special implementation that requires (Eq a) and removes duplicate
    elements, and
(2) a general implementation to fall back on for *any* type that fails
    the constraint, and
(3) a way to make "f" fully generic, such that the correct
    implementation is chosen automatically from the type variable a?

If I had a way to do this, then I could define a Set monad that
performs set operations when it can (i.e. when the elements are
equatable), but which automatically degenerates to a simple List when
it has to (i.e. when there's no equality test).  I almost suspect that
I might need to use Haskell Templates (I currently know nothing about
Haskell Templates).

Even better, if this problem is solvable, then the next step would be to
overload again to use an efficient implementation when set elements are
comparable (Ord a). 

Any ideas?

-- Ron