[Haskell] Re: Data.Set whishes

[Wolfgang Jeltsch]

Am Montag, 16. Februar 2004 10:05 schrieb Ketil Malde:
> Wolfgang Jeltsch <wolfgang at jeltsch.net> writes:
> >     * subsetOf :: Ord element => Set element -> Set element -> Bool
>
> (Isn't "isSubsetOf" a better name?)

So is "isElementOf".  I just said "subsetOf" to be consistent with 
"elementOf".  Well, the naming in the Data.* modules should generally undergo 
some changes.

> Would
>
>         x `isSubsetOf` y = x `union` y == y
>
> do, or did you want something more efficient?

It's unefficient if, e.g., the x sets are always very small but so are union, 
intersect etc.  I think, at first a complexity of O(|x| + |y|) would be 
acceptable so that your definition would be fine.  Maybe, the implementation 
of union, intersect etc. should be changed so that the complexity is more 
like O(min(|x|,|y|)).

> -kzm

Wolfgang