0
votes

I am learning prolog, what I am doing is writing a predicate to join two list. For example, if I query:

joinL([22,33,44],[1,2,3],L)

It will show L = [22,33,44,1,2,3].

To do it, I have tried to write predicate as followings:

joinL([],L2,L2).
joinL([H|T],L2,L):-joinL(T,L2,L),L = [H|L].

But when I query

joinL([22,33,44],[1,2,3],L)

It does not show desired result as i have just described above. Actually, it returns false.

What I want to ask is: "How did my code become wrong?", I do NOT ask "How to write predicate that join two list in prolog?" cause I can google it easily, and when compare with my code, I curiously want to know why i am wrong with my code. Can any one help me! Thank you all for reading and answering my question!

1
If we want to approach your question with an open mind: your code is not wrong, it is simply not doing what you want it to do. In a similar vein of thought, if there exists code that does exactly what you need, it is usually "clever" to read that code and understand it. You can of course approach a programming language empirically, and study it experimentally, but I don't think that something as simple as a programming language deserves an experimental approach. - User9213
In a few words, you are re-discovering append/3. - User9213
@User9213 Thank you, Thank to your comments! I must practice more to understand this language, it's is strange with me. - TaQuangTu
I'd recommend the open access, free version of the book that you can find on this website here (look for the PDF download link). If you read it and solve the exercises you will get a good head-start in Prolog programming. - User9213
This intro is gentler: Learn Prolog Now!. I remember "The Art of Prolog" fondly but it was tough. - David Tonhofer

1 Answers

2
votes

The problem is that you are using the = in the same way as one would use assignment:

L = [H|L]

In a state-changing language this means that whatever is stored in L (which is supposed to be a list) becomes a new list, made by tacking H to the front: [H|L]

In Prolog this states that what we know about L is that it is equal to [H|L]- equal to itself with H tacked to the front. This is not possible for any L though (actually, it is, if L is an infinite list containing only H but the proof engine of Prolog is not good enough to deal with that). Prolog's proof search fails at that hurdle and will return "false" - there are no solutions to the logic program you have entered.

(More after a coffee)

Here is how to think about this:

Ok, so I would like to state some logic facts about the problem of "list concatenation" so that, based on those logic facts, and given two completely-specified lists L1, L2, Prolog's proof search can determine enough about what the concatenated list LJ should look like to actually output it completely!

We decide to specify a predicate joinL(list1,list2,joinedlist) to express this.

First, we cover a special edge case:

joinL([],L2,LJ) :- LJ = L2.

So, it is stated that the 'joinL' relationship between the empty list '[]' and the joined list 'LJ' is such that 'LJ' is necessarily equal to 'L2'.

The logical reading is:

(LJ = L2) → joinL([],L2,LJ)

The operational reading is:

In order to prove joinL([],L2,LJ) you must prove LJ = L2 (which can either be verified if LJ and L2 are already known or can be added to the solution's known constraints if not.

There is also the reading of the SLD resolution, where you add the negation of joinL([],L2,LJ) to your set of logic facts, then try to prove ⊥ (the contradiction also know as the empty statement) using resolution, but I have not found that view to be particularly helpful.

Anyway, let's state more things about the edge cases:

joinL([],L2,LJ) :- LJ = L2.
joinL(L1,[],LJ) :- LJ = L1.
joinL([],[],LJ) :- LJ = [].

This will already enable the Prolog proof engine to determine LJ completely whenever any of the L1 and L2 is the empty list.

One commonly abbreviates to:

joinL([],L,L).
joinL(L,[],L).
joinL([],[],[]).

(The above abbreviation would not be possible in Picat for example)

And the third statement can be dropped because the other two "subsume it" - they cover that case more generally. Thus:

joinL([],L,L).
joinL(L,[],L).

Now for the case of non-empty lists. A fat part of logic programming is about inductive (or recursive) definitions of predicates (see this), so let's go:

joinL([H|T],L2,LJ) :- LJ = [H|LX], joinL(T,L2,LX).

Again, this is just a specification, where we say that the concatenation of a nonempty list [H|T] and any list L2 is a list LJ such that LJ is composed of H and a list LX and LX is the concatenation of T and L2.

This is useful to the Prolog proof engine because it gives more information about LJ (in fact, it specifies what the first element of LJ is) and reduces the problem to finding out more using the same predicate but a problem that is a little nearer to the base case with the empty list: joinL(T,L2,LX). If the proof goes down that route it will eventually hit joinL([],L2,LX), find out that L2 = LX and be able to successfully return from its descent.

joinL([H|T],L2,LJ) :- LJ = [H|LX], joinL(T,L2,LX).

is commonly abbreviated to

joinL([H|T],L2,[H|LX]) :- joinL(T,L2,LX).

Looks like we have covered everything with:

joinL([],L,L).
joinL(L,[],L).
joinL([H|T],L2,[H|LX]) :- joinL(T,L2,LX).

We can even drop the second statement, as it is covered by the recursive descent with L2 always equal to '[]'. It gives us a shorter program which burns cycles needlessly when L2 is '[]':

joinL([],L,L).
joinL([H|T],L2,[H|LX]) :- joinL(T,L2,LX).

Let's test this. One should use unit tests but I can't be bothered now and will just run these in SWISH. Let's see what Prolog can find out about X:

joinL([],[],X).       % X = []
joinL([1,2],[],X).    % X = [1,2] 
joinL([],[1,2],X).    % X = [1,2]
joinL([3,4],[1,2],X). % X = [3,4,1,2]
joinL([1,2],[3,4],X). % X = [1,2,3,4]

One can constrain the result completely, transforming Prolog into a checker:

joinL([3,4],[1,2],[3,4,1,2]). % true
joinL([3,4],[1,2],[1,1,1,1]). % false

Sometimes the predicate works backwards too, but often more careful design is needed. Not here:

joinL([3,4],L2,[3,4,1,2]). % L2 = [1, 2]

For this one, Prolog suggests a second solution might exist but there is none of course:

joinL(L1,[3,4],[1,2,3,4]). % L1 = [1, 2] 

Find me something impossible:

joinL(L1,[3,4],[1,2,100,100]). % false