G'day all.
Quoting Brian Hulley <[EMAIL PROTECTED]>:
> So perhaps my original spec is impossible to implement, though it is an open
> question whether some very clever encoding (with corresponding
> implementation of <) could be found which would lead to a better average
> performance (whatever that means).
For what it's worth:
- It's not such a dumb idea to separate equality testing from
less-than testing. A (Unique,ByteString) pair makes the former
fast and the latter pretty fast when it's needed.
- Arithmetic coding preserves lexicographic ordering. If you have
a good statistical model for what sort of strings might be used
as atoms, it may be possible to construct a representation of atoms
which fit in machine 32- or 64-bit word most of the time. (This is
similar to the way that GHC represents Integers; use a machine word
when it fits.)
- Hash table implementations rely on using a cheap test first
(comparing hash codes), going to a full comparison only if the
cheap test doesn't rule out what you're looking for.
> As an aside, if the monad was removed then the result of atom "a" < atom "b"
> (atom :: String -> Atom) could not be determined by analysis of the program.
> It would depend on the evaluation order chosen by the compiler, but in a
> sense this doesn't matter because whatever the result is, it would be the
> same at any future time during the same run of the program so the use of
> Atoms as keys would still be safe. But is this still "functional"?
Questions of this nature produce much disagreement. Once upon a time,
program arguments and environment variables were passed to a Haskell
program using a similar mechanism. I think we got rid of this because
it's not "functional" if you consider programs that fork.
Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
