Appending lists in Prolog with functor

Question

I am trying to use Prolog's append and length predicates for the first time in order to split a list, and I believe it requires a recursive solution. I am new to Prolog, and would like some help with this starter problem! :)

Here is the expected code output:

?- splits([1,2,3],S).
S = [1]/[2, 3] ;
S = [1, 2]/[3] ;
false.

It takes a list and splits it, but it does so by creating a structure with the functor /, this is what confuses me so far... I know that I need to use append for this, but how would one do so?

Here is my code so far:

splits([H | T], S) :-
    length(T, len), len > 0,

It will run until the tail of the list is empty, and then stop, but I can't quite figure out how to add in the append function or make it recursive... Could someone give me a tip? :)

Answer 1

I would say that you are almost at a working implementation with your remark that append/3 can be used for splitting lists. This is indeed what append/3 in the instantiation (-,-,+) does.

The only added requirement that seems to occur in your question is to exclude cases in which either of the splits is empty. This can be achieved by checking for inequivalence between terms using \==/2.

This results in the following code:

splits(List, X/Y):-
  append(X, Y, List),
  X \== [],
  Y \== [].

PS: Notice that your use of len in your code snippet is wrong, since len is not a Prolog variable but an atom. Handing an atom to the second argument of length/2 produces a type error, and an arithmetic error in len > 0 (provided that len is not defined as a function). (Both observations relate to SWI-Prolog.)

Hope this helps!

Answer 2

Here is a recursive approach:

splits([A,B|T], [A]/[B|T]).
splits([A|T], [A|R]/S) :-
    splits(T, R/S).

The first clause provides the base case of splitting a list with at least 2 elements ([A,B|T]) into [A]/[B|T] (it just splits out the first element).

The second clause says that [A|R]/S is the split of [A|T] if R/S is the split of T. So it will "generate" the other solutions recursing down to the base case. If the first list has only two elements, the base case will be successful, and backtrack to the recursive case will fail on the first try (which is what you want - no more solutions to that case) because the recursive case only succeeds when the first list has 3 or more elements (A plus the two enforced on T in the recursive query).

| ?- splits([1], S).

no
| ?- splits([1,2], S).

S = [1]/[2] ? ;

no
| ?- splits([1,2,3], S).

S = [1]/[2,3] ? ;

S = [1,2]/[3] ? ;

no

...