[mercury-users] Destructive list operations

Ralph Becket rafe at csse.unimelb.edu.au
Tue Jan 6 13:55:22 AEDT 2009

Michael Day, Tuesday,  6 January 2009:
> >Regarding your performance concerns, have you considered moving to an
> >array or tree based representation or otherwise abstracting away from
> >lists?  If your structures really are unique, then some kind of
> >extensible array data type might be more appropriate to your needs.
> An array is not convenient, as we want to insert things into the middle 
> of it, potentially replacing one item with several items. A tree could 
> work for that, we haven't tried this option yet.

Sure, I'm not suggesting a simple array.  Something like a list of array
segments or a B-tree of array segments should work.

> We have implemented our own list type entirely in C with a last pointer 
> at the beginning for constant time appends, and that works, but results 
> in overhead converting to and from standard lists if it is not used 
> everywhere in the code.

Yes, you will inevitably have this issue.  If you can abstract away
from the list type, that would be good.  Destructively updating lists
is likely to lead to some very hard to find bugs, IMHO.

-- Ralph
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au

More information about the users mailing list