[mercury-users] List instantiation question

doug.auclair at logicaltypes.com doug.auclair at logicaltypes.com
Thu Mar 2 17:24:44 AEDT 2006


Dear Ralph, thank you for your reply.  I suspected that a partially-instantiated
list structure wouldn't be supported.  

You wrote:

>Whenever someone tries to do something Prologesque like this it's
>usually an efficiency hack.  Mercury's optimisations are powerful enough
>that just doing things the simple way (i.e., using ground values
>throughout) will often generate just as efficient code as you'd expect
>from a Mercury that did support partial instantiation.

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),
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).  This approach is
what I settled on for the code I sent as the example: is there a better way than
prepend-then-reverse?

Sincerely,
Doug Auclair

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



More information about the users mailing list