[mercury-users] Assoc-List: keys ground & values unique

[Ralph Becket]

Hi Stefan,

Kral Stefan, Thursday, 22 September 2005:
> 
> I need to do a variant of assoc_list that can hold something unique 
> as the value. Of course, I tried anything promising (to me), but
> it didn't quite work out.

Before going further with this it's probably worth pointing out that
uniqueness is awkward to work with (few library predicates currently
preserve uniqueness) and, somewhat embarrassingly, is not yet fully
supported (e.g., ui modes).

So my first question is why do you want uniqueness?  Are you sure it's
absolutely necessary?  If you can do without it, life will be much
easier.

> So, assuming a data-type like
> 	:- type gmpkv ---> index_content(int, gmpint).
> and a predicate like 
> 	:- pred assoclist_fetch(int, gmpint, list(gmpkv), list(gmpkv)).
> which does a lookup of the 1st arg in the 3rd, returning the 2nd and
> the 4th (upon success). The returned assoclist does not contain the
> key-value "pair" anymore. (I wanted to use "real" pairs at first. But 
> as two args are integers, that did not appear to be such a good idea...)
> 
> What should the mode declaration look like?
> 
> My first guess was
> 	:- mode assoclist_fetch(in, uo, di, uo) is semidet.
> the second one
> 	:- mode assoclist_fetch(in, uo, di(list(unique)),
> 					free >> unique(list(unique))) 
> 							is semidet.
> then I tried all kinds of variations that describe the instantiatedness
> tree in more (and more) details, yet I did not hit the right one yet.

The second mode is effectively identical to the first.

If you want an association list with shared keys but unique
values you need something like this:

:- inst shared_unique_pair ---> (ground - unique).
:- inst shared_unique_alist
	--->	[]
	;	[shared_unique_pair | shared_unique_alist].
:- mode assoclist_fetch(in, uo, in(shared_unique_alist),
	out(shared_unique_alist)) is semidet.

To be frank, uniqueness is something that requires great care.  We would
love someone to do a Ph.D. on fixing up this and other parts of the mode
system (there is plenty of interesting research left in mode systems...)

> It the problem solely on my side or it is also on the current status 
> of the implementation of unique modes within the Mercury compiler?

A bit of both :-)

> (My next step will be using unsafe_promise_unique at appropriate 
> places, hoping this will not kick correctness out of the window.)

This is probably the second easiest option.  The best thing to do would
be to identify, if at all possible, a way to solve your problem that
doesn't depend upon uniqueness at all.

-- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------