[mercury-users] append for list skeletons

[Ralph Becket]

> From: Robert Colvin [mailto:robert at svrc.uq.edu.au]
> Sent: 31 July 2001 10:18
> 
> Hi, I just wanted to check that I understand the manual - it says that
it is
> not possible to implement append(in_listskel, in_listskel,
out_listskel),
> ie where the lists are lists of uninstantiated variables.

Using infix ++ for append we have

[]       ++ Ys = Zs :-
	Zs = Ys.

[X | Xs] ++ Ys = [Z | Zs] :-
	Z  = X,      % *1*
	Zs = Xs ++ Ys.

The line marked *1* is where the problem arises with lists of 
uninstantiated variables: it is an attempt to unify two variables
with inst free, which is the same as saying we want Z to be an alias
of X.  If this were supported, then if I wrote As + Bs = Cs where
As, Bs and Cs are lists of free (uninstantiated) variables, then if
at some later point in my program I unify a variable in Cs with
something, then that unification should be mirrored in the 
corresponding aliased variable in As or Bs.

Mercury does not support free variable aliasing because it is
so costly in terms of performance (this is one of the reasons why 
Mercury is so much faster than Prolog).

[In fact, the line Zs = Ys in the first clause is a more complicated
example of free variable aliasing.]

> Therefore the
> naive/inefficient implementation of reverse
> 
> rev([], []).
> rev([H|T], R) :-
>     append(RT, [H], R), rev(T, RT).
> 
> will not be implementable for list skeletons?

That's correct.

Mercury requires quite a different programming style to Prolog, more
in line with languages like ML.  Many of the cunning tricks you have
to use in Prolog with partially instantiated structure (e.g. the 
sort of difference structures you are describing here) are just 
efficiency hacks; there are few places, in my opinion, where their 
use doesn't make code less legible.

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