[mercury-users] List instantiation question

[Ralph Becket]

doug.auclair at logicaltypes.com, Thursday,  2 March 2006:
> 
> For this particular case it wasn't (the partially instantiated list
> was a guarantee of the list length, declaratively, as well as
> providing the place-holders for the resulting values, making the
> entire block deterministic)

Could you use an array instead?

> , but I have worked on systems where
> efficiency /was/ an issue -- a serious one -- so if I may ask, what is
> the efficient equivalent to Prolog's:
> 
> add_elements([H0|T]) -->
>   { do_something_with(H0, H) },
>   [H],
>   add_elements(T).
> 
> (called thusly:  add_elements(SomeStuff, Answer, []))
> 
> The above example is 0(N), whereas the documented Mercury response of
> 'prepend to the head and then reverse the resulting list' is O(2N).

And, of course, O(2n) = O(n) :-)

Prolog programs pay a huge performance cost supporting variables that
support this kind of thing.  Mercury programs don't pay this cost at all
because Mercury variables do not support Prolog-style aliasing.  Mercury
will beat Prolog in almost any contest of this kind because Mercury's
constant factors are much smaller.

> This approach is what I settled on for the code I sent as the example:
> is there a better way than prepend-then-reverse?

Well... you could use an array buffer and double its length when needed
although that's still "O(2n)" in the worst case.  And, of course, using
arrays has consequences for determinism.

I did some experiments a couple of years ago and found that when n was
small (say 50 - 100) it was very hard to beat simple applicative list
programming for performance, no matter how clever I tried to be.

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