[Haskell-cafe] Efficient Sets for Small Enumerations

[Jean-Philippe Bernardy]

On 4/3/06, David F. Place <d at vidplace.com> wrote:
>
> On Apr 3, 2006, at 1:31 PM, Benjamin Franksen wrote:
>
> >  wondered about the Ord instance. Wouldn't it be faster to compare
> > (word-) representations?
>
>
> I thought about that some.   Since the set representation is based
> completely on the enumeration, it would be possible for the type
> being collected to have a different implementation of Ord.  For
> instance:
>
> newtype LowerCaseAlpha = LCA Char deriving (Eq, Show)
>
> instance Enum LowerCaseAlpha where
>      fromEnum (LCA x) = (fromEnum x) - (fromEnum 'a')
>      toEnum x = LCA $ toEnum $ x + (fromEnum 'a')
>
> instance Ord LowerCaseAlpha where
>      compare (LCA a) (LCA b)
>          | a == b = EQ
>          | a > b = LT
>          | a < b = GT
>
> Perverted, but possible.

I don't think there is a requirement for the Ord class to be equal to
"compare a b = compare (toAscList a) (toAscList b)". I'd say it's safe
to simply compare the bits representation.

Besides, I've integrated your module to the package I'm busy setting up.

http://darcs.haskell.org/packages/collections/Data/Set/Enum.hs

(I'm accepting patches -- most notably if someone wishes to complete
the haddock documentation)

FWIW, it passed the standard regression testsuite for Sets flawlessly.

I'm thinking of removing the UniverseSet class though. It seems to me
that Bounded serves the purpose just right.

Cheers,
JP.