[plt-scheme] Re: User data structures and equality

On 4/10/07, Noel Welsh <noelwelsh at yahoo.com> wrote:
> I must be missing something.  If D is finite you can assign a unique integer to each element in D, and that's your hash (or your vector index).  If you know the structure of D (and presumably you do, as you know equality) can also assign unique integers.  Consider a data type like:
>
> number-list := null | cons number list
>
> assign 0 = null, 1 = cons
>
> Then (cons 1 (cons 2 null))  = 11120
>      (cons 2 null) = 120
> etc.  These are unique.  If the elements of the list weren't numbers you'd have to do a bit more work, but can still generate unique numbers.
>
> Anyway, that's what comes to mind.  Hope it's useful.
>

Hello Noel,

Well, it is not that simple. I don't know the kind of structure I
have. The user gives me a list of structure instances and a procedure
which receives 2 instances and returns a boolean indicating their
equality. Now, I need to assign them an integer. That's easy, it can
be their position on the list. Then I transform the list into a
vector. Given a number I can easily fetch the instance but given an
instance, for me to return its number, I have to go through the vector
until I find it (using the equality procedure) and then I return the
index of the vector. That's the best I can do now. Unfortunately, I
cannot use your scheme since the structure given to me might be as
simple as a list or as complex as hash-tables, class instances, etc. I
have no idea.

If you can think of something, it would be great.

Cheers,

Paulo Matos

> N.
>
>
> ----- Original Message ----
> From: Paulo J. Matos <pocm at soton.ac.uk>
> To: PLT-list Mailing <plt-scheme at list.cs.brown.edu>
> Sent: Tuesday, April 10, 2007 9:26:12 PM
> Subject: [plt-scheme] Re: User data structures and equality
>
> On 4/10/07, Paulo J. Matos <pocm at soton.ac.uk> wrote:
> > Hello all,
> >
> > I want to define a bijective function f: D -> N, where D is a finite
> > collection of user data structures which have a known equality
> > procedure that given two elements of D know if they are equal or not.
> > Implementing this with alists is trivial, however, computing f and
> > f^-1 is done in linear time. The 'good' way would be hash-tables but I
> > can't since I have no hash-function for the data structures, only the
> > equality procedure [there is no obvious ordering between the user
> > structures since I don't really know what they are].
> >
>
> Agrh, I always forget something... Another way (better) would be to
> use a simple vector. Computing f^-1 is constant, f  is linear but I'm
> still hoping for a better solution.
>
> > Any suggestions?
> >
> > Cheers,
> > --
> > Paulo Jorge Matos - pocm at soton.ac.uk
> > http://www.personal.soton.ac.uk/pocm
> > PhD Student @ ECS
> > University of Southampton, UK
> >
>
>
>
>
>
>
> ____________________________________________________________________________________
> Don't pick lemons.
> See all the new 2007 cars at Yahoo! Autos.
> http://autos.yahoo.com/new_cars.html
>
>
>


-- 
Paulo Jorge Matos - pocm at soton.ac.uk
http://www.personal.soton.ac.uk/pocm
PhD Student @ ECS
University of Southampton, UK