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

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.
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