From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 4B28BBBAF for ; Mon, 28 Jun 2010 15:37:56 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlQBANJCKEzRVaC2mGdsb2JhbACfJwgVAQEBAQEICQwHESKwDIIJhQQuiFMBAQMFhR8Eg2Y X-IronPort-AV: E=Sophos;i="4.53,497,1272837600"; d="scan'208";a="65486497" Received: from mail-gy0-f182.google.com ([209.85.160.182]) by mail4-smtp-sop.national.inria.fr with ESMTP; 28 Jun 2010 15:37:38 +0200 Received: by gyf3 with SMTP id 3so699808gyf.27 for ; Mon, 28 Jun 2010 06:37:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type; bh=84TXlBoiakp7CtzQ6uUjyRATT6FgLuJ/5c6x+G/Vnow=; b=nu/1+xle333ajA8ENbEsNybusZaPJ3Tyg1oOL10Aubh9X1Shgp8jEXc7num3CVnWxy zkwRs0ns+YwJE5JaYVlYpez3qGJRmd+4FRhnXZwKjd0MV4OnJTDJoQwYKQQxI0CKNrnk gfgMrpcWLbNH99nqctmeaLKZxQdiH5RTHzvzk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=sKGy2qH86PSkR2DusLblx3gY3jmX+gF+3cdVBYZzzX18vuaXRRqndi+WvecwF9JXhG F215cCi941IYYcGLgGqrgFc4mELSqhk0GDGMNbXxcZ6Mqdy2YPef09qQZiY7VqjMrO1t c07yhXqyI2dV7rg0WAXq8lVNR8RkBj4OfvGAA= MIME-Version: 1.0 Received: by 10.229.89.204 with SMTP id f12mr2670852qcm.247.1277732257134; Mon, 28 Jun 2010 06:37:37 -0700 (PDT) Received: by 10.229.215.70 with HTTP; Mon, 28 Jun 2010 06:37:37 -0700 (PDT) In-Reply-To: References: <20100628021543.GA14360@malaquias.DHCP-GERAL> Date: Mon, 28 Jun 2010 08:37:37 -0500 Message-ID: Subject: Re: [Caml-list] Re: Symbol type From: Nicholas Kidd To: Michael Ekstrand Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=0016364eea884df851048a17390c X-Spam: no; 0.00; romildo:01 malaquias:01 ocaml:01 compiler:01 integers:01 integers:01 intern:01 foo:01 ocaml:01 hash-consing:01 lri:01 filliatr:01 publis:01 hash-consing:01 romildo:01 --0016364eea884df851048a17390c Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Sun, Jun 27, 2010 at 9:33 PM, Michael Ekstrand wrot= e: > On 06/27/2010 10:15 PM, Jos=E9 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 =3D=3D rather th= an > =3D 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 --0016364eea884df851048a17390c Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
On Sun, Jun 27, 2010 at 9:33 PM, Michael Ek= strand <michael= @elehack.net> wrote:
On 06/27/2010 10:15 PM, Jos=E9 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. =A0As I see it, you have two decent options:

- Use/write a symbol table which "interns" symbols to integers. = =A0The
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 obj= ect if
one already exists, and the string object passed in if it's never been<= br> seen before. =A0The resulting strings can be compared with =3D=3D rather th= an
=3D 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.


Best,
-Nick=A0
--0016364eea884df851048a17390c--