Concatenation of Lists in Prolog

Question

Can someone help me find the error in these rules?

concat([], List, List).
concat([Head|[]], List, [Head|List]).
concat([Head|Tail], List, Concat) :- concat(Tail, List, C), concat(Head, C, Concat).

Trying to concatenate two lists fails:

| ?- concat([1,2], [4,7,0], What).

no

Answer 1

To fix your code, the way you intended it, you just need to transform Head into [Head] in your last call to concat/3 in your last clause. The problem was that you called your predicate with Head only as first argument, which is not a list.

Though, here are several notes :

• [Head|[]] is equivalent to [Head]
• your algorithm has a poor complexity, n! I believe.
• with no cut inserted after your second clause, you generate infinite choice points through the call of your third clause with a list of length 1 (that hence calls your second clause, that then is ran through your third clause, etc... infinite loop).

Here is SWI-pl's version, to hint you towards good prolog recursion :

append([], List, List).
append([Head|Tail], List, [Head|Rest]) :-
    append(Tail, List, Rest).

You can find other resources on recent posts here or in Learn Prolog Now! tutorial if you want to learn how to use recursion properly.

Answer 2

It can be done by using append.

concatenate(List1, List2, Result):-
   append(List1, List2, Result).

Hope this helps.

Answer 3

Here is the concatenation between two lists rule:

concat([],L2,L2). concat([Head|Tail],L2,[Head|L3]) :- concat(Tail,L2,L3).