Path: utzoo!mnetor!uunet!munnari!mulga!jws
From: jws@mulga.oz (Jeff Schultz)
Newsgroups: comp.lang.prolog
Subject: Re: Simple decomposition and PROLOG (random musings - part II)
Message-ID: <2570@mulga.oz>
Date: 3 Mar 88 02:53:23 GMT
References: <7290@agate.BERKELEY.EDU>
Reply-To: jws@mulga.UUCP (Jeff Schultz)
Organization: Comp Sci, Melbourne Uni, Australia
Lines: 30
Keywords: Destructive, Problem decomposition, LISP vs PROLOG Philosophy

Two brief points about

>          reverse1([],[]).    /* Base case */
>          /* recursive case, append first element to last of reversed */
>          reverse1([H|T],L) :- reverse(T,Z), append(Z,[H],L). /* list */

>          reverse2(L1,l2) :- revzap(L1,[],L2).    /* create "holder" list */
>          /* Remove element off one list, add it to reversed list */
>          /* since it starts empty, it will "fill up" in reverse order */
>          revzap([X|L],L2,L3) :- revzap(L,[X|L2],L3).
>          revzap([],L,L).     /* When first element list is empty, then */
>                              /* copy "holder" list to return reverse */

Just replacing append with nconc or whatever isn't going to change the
time complexity of reverse1, though languages that have already paid
for the ability to do destructive modifications should run faster with
it.  Of course, the space complexity will change.

But, if you want backtrackable destructive modification, you need a
rather more complicated trail which will take up twice the space and
time.  You may not gain anything unless destructive modification is a
significant part of your program.

I'd be surprised to find a LISP programmer writing something similar
to either reverse1 or reverse2 -- with or without replacd.  A do loop
producing code essentially equivalent to reverse2 seems more likely.
Now, there is nothing except syntax preventing this from being done
for Prolog, provided that it expands to Prolog code in some
intelligible way, but there doesn't seem that much to save besides
the dummy function name.