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