insert element in a list and return the same list updated

Question

Hi i'm trying to insert an element in a list but it is very important from my program that the result is stored in the original list and not in a new one.
Any code that i have written or found on the internet only succeeds if you create a new list in which the end result is kept.
So my question is can anyone tell me how to define a function: insert(X,L) where X is an element and L is a list?

Answer 1

No, Prolog just doesn't work that way. There is no such thing as "modifying" a value. A variable can be unified with a specific value, but if it was already [1,3], it won't ever be [1,2,3] later.

Answer 2

As aschepler says, you cannot add or make any change to a proper list, i.e. a list in which every element is already bound. The only "modifying" we can do is unifying one expression with another.

However there is a concept of a partial list to which additional elements can be "added" at the end. This is typically known as a difference list, although that nomenclature may not be immediately understandable.

Suppose we start, not with an empty list, but with a free variable X. One might however think of subtracting X from X and getting "nothing". That is, an empty difference list is represented by X - X. The minus "-" here is a purely formal operator; no evaluation of the difference is intended. It's just a convenient syntax as you see from how difference lists can be used to accomplish what you (probably) want to do.

We can add an element to a difference list as follows:

insertDL(M,X-Y,X-Z) :- Y = [M|Z].  

Here M is the new element we want to add, X-Y is the "old" difference list, and X-Z is the "new" difference (to which M has been added, by unifying the previously free variable Y with the partial list [M|Z], so that Z becomes the "open" tail of partial list X).

When we are finally done inserting things into our difference list, we can turn X into a proper list by setting the "free tail" at that point to the empty list [ ]. In this sense X is the "same" variable as when we first began, just unified by incremental steps from free variable to proper list.

This is a very powerful technique in Prolog programming, and it takes some practice to feel comfortable using it. Some links to further discussion on the Web:

[From Prolog lists to difference lists]
http://www.irisa.fr/prive/ridoux/ICLP91/node8.html

[Implementing difference lists in Prolog]
http://www.cl.cam.ac.uk/~jpw48/difflists.pdf

[Lecture Notes: Difference Lists]
http://www.cs.cmu.edu/~fp/courses/lp/lectures/11-diff.pdf