Back to Lists

• Lists are a recursive data structures
• Since in a list, the composition is of a head and a tail, where the tail itself could be a list - hence the concept of recursion comes into the definition
• Hence : Most operations on lists are defined recursively
• These include definitions already considered : member to list manipulation operations like concatenating lists,deleting elements from lists etc.

Membership again :

member(X, [X | _]).
member(X, [ _| Tail]) :-
	member(X, Tail).

• X is a member of a list, if X is the head of the list
• X is a member of the tail
• Boundary condition is placed first - and satisfied when X is the first element (head) of the list
• The recursive call in the second clause searches for an element in the tail of the list that is shorter than the original list. The recursive call successively reduces the size of the list by comparing the head of the list with X, then removing the head, and using the remainder, and taking the first element of the remainder as the new head, comparing with X and so on. This process stops when we are left with tail being the empty list

Concatenating Lists (combining two lists together into one) :

conc( [], L, L).

conc( [X | L1], L2, [ X|L3 ]) :-
 conc(L1, L2, L3).

• L3 is obtained by concatenating L1 and L2 together.
• It works by first stating the base case : i.e. joining an empty list to any list is the list itself
• A list obtained by concatenating a list L2 with a list whose head is X and tail L1, is a list whose head is X and tail composed of concatenating L1 and L2.
• Hence, the new formed list, L3, will also have X as its head

Issuing the command :

conc( [1,2], [3,4], [1,2,3,4])

will return yes

Similarly, a query :

conc( [1,2], [3,4], L)

will return L = [1,2,3,4]