[Haskell-cafe] Where is Data.Atom ?

[Duncan Coutts]

On Sun, 2006-07-02 at 23:08 +0400, Bulat Ziganshin wrote:
> Hello Brian,
> 
> Sunday, July 2, 2006, 10:58:29 PM, you wrote:
> 
> >       fromString :: String -> Atom
> >       toString :: Atom -> String
> 
> >       instance Eq Atom
> >       instance Ord Atom -- this is where things get difficult!
> 
> i think that ByteString is a very strong candidate to Atom. `memicmp`
> is very fast operation, unless you plan to use really large strings
> with the same beginnings

and also equal lengths.

The nice thing about the ByteString representation is that we can use
the length to short-cut inequality and use equality of the pointers to
short-cut equality:

eq :: ByteString -> ByteString -> Bool
eq a@(PS p s l) b@(PS p' s' l')
    | l /= l'            = False    -- short cut on length
    | p == p' && s == s' = True     -- short cut for the same string
    | otherwise          = compareBytes a b == EQ

So the worst case is long strings that compare equal but have different
memory blocks.

Duncan