[m-dev.] efficiency of mercury lists ?

Ralph Becket rbeck at microsoft.com
Mon Jul 30 21:28:34 AEST 2001

> From: Holger Krug [mailto:hkrug at rationalizer.com]
> Sent: 28 July 2001 17:14
> I need a list-like data-type which is optimized for the following
> operations:
> a) concatenation
> b) forward scanning from the start of the list
> c) backwards scanning from the list tail
> Can anybody tell me which library data-type fits best into this
situation ?
> `list' seems to require O(n) for a) and c).

For lists you have
a) O(n) in length of prefix list,
b) O(n) time, O(1) space,
c) O(n) time, O(n) space (using a foldr style approach).

For arrays you have
a) O(n + m) in the size of both arrays,
b) O(n) time, O(1) space,
c) O(n) time, O(1) space.

> `array' seems inefficient if a) is needed quite often.

It depends upon your program's concatenation behaviour.
Each list cons cell occupies two words of memory, whereas
each array cell only occupies one.  If As is typically at
least as large as Bs in As ++ Bs then you will do at least
as well in efficiency terms as using lists.

If, on the other hand, this isn't the case, you may be able
to use amortization to make things efficient (see Ch. 5 of
Okasaki's book [ref. below]).

> Are their other possibilities ?

If you check out the rather excellent "Purely Functional Data
Structures" by Chris Okasaki you'll find an implementation of
binary random-access lists for which the cons, head, tail, 
lookup and update operations run in O(log n) worst case space.


mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au

More information about the developers mailing list