In terms of a strictly pure implementation of a functional Set, it would be

odd to have a "find" function - you'll also get some interesting undefined

behaviour with these sets if you try to operations like union and

intersection but I guess you're already happy with that! 

It seems to me rather natural to have it: otherwise, what's the point of
being able to provide your own compare, beside just checking for
membership of the class?

type t = F of t | G of t * t | A | B
I want to index values of type t according to their first constructor.
So in my set structure, there will be at most one term starting with
each constructor, and:
find (F(A)) (add (F(B)) empty) will return F(B)

With a Set.find, it's easy:

let compare x y = match x,y with
| (F,F | G,G | A,A | B,B) -> 0
| _ -> Pervasives.compare x y

module S = Set.Make ...

With the Map solution, i'm obliged to define:

type cstr = F' | G' | A' | B'
let cstr_of x = F _ -> F' | G _ -> G' etc.

and then make a Map : cstr |--> t, which duplicates the occurrence of
the constructor (F' in the key, F in the element). Besides, I'm
responsible for making sure that the pair e.g. (G', F(A)) is not added.