Prolog : Recursive Function Branching & "Returning"

Question

I was writing few recursive Prolog predicates and ran into a certain point that I don't quite understand at the moment.

For example, I wrote the predicate split/3 that divides a list of integers into a list of non-negative integers and a list of negative integers:

Version 1

split([], [], []).
split([ListHead|ListTail], [ListHead|PList], NList) :- 
   ListHead >= 0,
   split(ListTail, PList, NList).
split([ListHead|ListTail], PList, [ListHead|NList]) :- 
   ListHead < 0,
   split(ListTail, PList, NList).

But before arriving at that solution, I wrote the solution below and wondered for a while why it wasn't working:

Version 2

split([], [], []).
split([ListHead|ListTail], PList, NList) :- 
   ListHead >= 0,
   split(ListTail, [ListHead|PList], NList).
split([ListHead|ListTail], PList, NList) :- 
   ListHead < 0,
   split(ListTail, PList, [ListHead|NList]).

where:

• The first given argument is split into ListHead and ListTail.
• If the ListHead element (integer) is greater than or equal to 0, it's prepended to the list of non-negative integers, and used an argument for the recursive call with an unmanipulated Nlist.
• If the ListHead element (integer) is less than 0, it's prepended to the list of negative integers and used as an argument for the recursive call with an unmanipulated PList.

I'm not getting why version 2 doesn't work; it compiles without any warnings, but only ever returns false. The only difference with the above version is that the prepending of integer elements to Nlist or PList is done within the predicate definition (after the :- operator), and not in the parameters for the predicate call. For me, it makes sense to prepend the result as part of the argument for the next call...

I feel like I'm missing something about Prolog's way of "searching" recursively calls!

Could someone explain why version 1 works as intended whereas version 2 does not?

Answer 1

It does not work because you are loosing the elements when you go back in the backtracking.

In version 1, PList is instantiated with [] when the returns begins, you start to stack elements like this:

[ListHead|PList]    the same as   [ListHead| [] ] at first level.

At the end you have all the list.

In version 2, Plist remains uninstantiated and cutting condition never satisfy, because you have something like:

[[]|1,2,3,4,5,6]

and don't match with anything.

In version 2 you need to use accumulators (or auxiliary variables) at the end you need to copy the accumulators into real variables like this:

split([],A,B,A,B).
split([ListHead|ListTail], PList, NList, PListAcum, NListAcum) :- ListHead >= 0, 
    split(ListTail, PList, NList, [ListHead|PListAcum], NListAcum).
split([ListHead|ListTail], PList, NList, PListAcum, NListAcum) :- ListHead < 0, 
    split(ListTail, PList, NList,  PListAcum, [ListHead|NListAcum]).

You call that like this:

split([1,2,3,-1,-2,-3] , P, N, [], []);

Let me explain that, the accumulator are initialized and they accumulate your data. The first line only copy the accumulators into the real variables when the list is empty an then the accumulators lost its elements back y recursion (you'll understand if you look at the names of the variables on different backtracking levels) but the real variables remain unchanged through the backtracking.

You'll need an accumulator for each variable you want to return as a result, or do it like your first version.

You can search for information about accumulators.

Greets.

Answer 2

Pattern matching it's a key feature of Prolog, accounting for half of the power of the language, and plays together to backtracking, allowing to express control in a elegant, but unusual, way. Here is how you could 'correct' the second version

split([],[],[]).
split([ListHead|ListTail], PList, NList) :-
    ListHead >= 0, split(ListTail, Temp, NList), PList=[ListHead|Temp].
split([ListHead|ListTail], PList, NList) :-
    ListHead < 0, split(ListTail, PList, Temp), NList=[ListHead|Temp].

Of course the problem it's that the base case cannot be matched with your original version.

Answer 3

Re-writing your code with shorter variable names and rule head assignments moved into rule body, it might be easier to read.

We'll assume it is called with a given list, to produce its two halves, one of its non-negatives (we'll call them "positives", for short, but 0 is included), and another, of its negative elements.

Version 1 reads,

split([],[],[]).
split(X, Y, Z) :-        X = [A|B], Y = [A|POS], Z = NEG,
    A >= 0, split(B, POS, NEG).
split(X, Y, Z) :-        X = [A|B], Y = POS, Z = [A|NEG],
    A <  0, split(B, POS, NEG).

• an empty list splits into two empty lists;
• to split a list X with head A which is non-negative, we split its tail B into two lists, list of positives POS and list of negatives NEG, and (naturally) prepend A to B's positives to be returned as X's positives;
• to split a list X with head A which is negative, we split its tail B into two lists, list of positives POS and list of negatives NEG, and (naturally) prepend A to B's negatives, to be returned as X's negatives.

Version 2 reads,

split([],[],[]).
split(X, Y, Z) :-        X = [A|B], Y = POS, Z = NEG,
    A >= 0, split(B, [A|POS], NEG).
split(X, Y, Z) :-        X = [A|B], Y = POS, Z = NEG,
    A <  0, split(B, POS, [A|NEG]).

• an empty list splits into two empty lists;
• to split a list X with head A which is non-negative, we split its tail B into two lists, list of positives and list of negatives, and we demand that the head of B's positives be the same as A (which is most unlikely); and then we return only the tail of B's positives (i.e. POS) as X's positives (i.e. one element shorter...??);
• similarly with the negative head element.

I think you can see that this makes no sense.

There is no backtracking here, because all the rule's clauses are mutually exclusive (guaranteed to fail on backtracking).