[Haskell-cafe] Efficient Sets for Small Enumerations

[David F. Place]

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.

--------------------------------
David F. Place
mailto:d at vidplace.com