On Sun, Jun 27, 2010 at 9:33 PM, Michael Ekstrand <michael@elehack.net>wrote:

> On 06/27/2010 10:15 PM, José Romildo Malaquias wrote:
> > Is there a symbol type in OCaml, with a constant time comparison
> > function? Something like symbols from Scheme and LISP or atoms from
> > Prolog. Useful in compiler construction.
>
> Not directly.  As I see it, you have two decent options:
>
> - Use/write a symbol table which "interns" symbols to integers.  The
> resulting integers can be compared.
> - Use/write a symbol table which interns symbols to unique string
> instances, so SymTbl.intern "foo" returns the existing string object if
> one already exists, and the string object passed in if it's never been
> seen before.  The resulting strings can be compared with == rather than
> = in constant time.
>
> Either of these options would be fairly similar to how symbols work
> under the hood in a Lisp implementation, I believe.
>
>

Use the Ocaml hash-consing library.

http://gallium.inria.fr/ml2006/accepted/5.html
http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.pdf

Best,
-Nick