In the Code below I'm not sure what the first three lines do? I understand that the fourth line recursively takes the head off of List 1 and List2, but why are the rules above that needed?
interweave([],[],[]).
interweave([X],[],[X]).
interweave([],[Y],[Y]).
interweave([X|List1],[Y|List2],[X,Y|Result]) :-
interweave(List1,List2,Result).
As others have pointed out, when you have a recursive predicate clause such as:
interweave([X|List1], [Y|List2], [X,Y|Result]) :-
interweave(List1, List2, Result).
You need a termination case. Otherwise, where does the logic end? In this case, as long as both of the first two arguments are lists of at least one element (or can validly be instantiated as such), and the third argument is a list of at least two elements (or can be instantiated as such), then recursion will occur.
When you pass lists in for the first two arguments and expect a result in the third, then eventually you'll hit one of the following cases which will fail the above predicate clause:
1. interweave([], List2, Result), where List2 has at least one element
2. interweave(List1, [], Result), where List1 has at least one element
3. interweave([], [], Result)
All three of these cases will fail the above predicate clause because [X|T] cannot be unified with []. It necessarily is a list of at least one element. Thus, without the base cases, the entire predicate fails if any of the arguments are fully instantiated, or will recurse infinitely if none of them are.
Therefore, you need at least one base case which will succeed. But what should the base cases be? It depends upon what behavior you desire for the predicate. In the case of the original implementation, the base cases give you the following behaviors:
1) interweave([], [], []). enables success when both of the original input lists are the same length.
2) interweave([X], [], [X]). enables success when the first list has exactly one more element than the second list.
3) interweave([], [Y], [Y]). enables success when the second list has exactly one more element than the first list.
@CapelliC pointed out the effects in his answer. So in the current implementation you show, with the three base cases, the following would succeed:
interweave([1,2,3], [a,b,c], R). % R = [1,a,2,b,3,c]
interweave([1,2,3], [a,b], R). % R = [1,a,2,b,3]
interweave([1,2], [a,b,c], R). % R = [1,a,2,b,c]
However, the following would fail:
interweave([1,2,3], [a], R).
interweave([1], [a,b,c], R).
etc
You can change this behavior in several ways. For example, if you want to require that the two input lists are identical in length, then leave out base cases #2 and #3. If you want lists of any length to "weave" together and just append the extra elements, then you can change the base cases to:
interweave([], L, L).
interweave(L, [], L).
These say that an empty list woven with another list, L, is the list L. And since [] is a list, then you get interweave([], [], []) succeeding without having to state it explicitly. It will, however, succeed twice for interweave([], [], []). and, as a result, yield some duplicate results in some cases. To avoid this, you can define these base cases as:
interweave([], L, L).
interweave(L, [], L) :- L = [_|_]. % Only true for non-empty list L