# Working with lists in Prolog

Please work in SWISH or locally, using `swipl` command.

## 1. List notation

A list is an ordered collection of items. An element can be any Prolog structure (term).

We denote the list:

```[a,b,c]
[2,4,6, ala, has, a, cat]
[]```

Each list consists of:

• head , which is always the 1st list element, and
• tail , which is always a list

The head and tail are separated by the operator ` | ` (vertical bar), e.g .:

```? - [X | Y] = [a, b, c, d].

X = a
Y = [b, c, d];```

The decomposition and structuring of lists is mainly carried out by the unification mechanism. For example:

```? - [X, Y | Z] = [a, b, c, d].

X = a
Y = b
Z = [c, d];

? - [X, Y, a] = [Z, b, Z].

X = a
Y = b
Z = a;```

Exercise

```? - X = [a, b, c].
? - [X | Y] = [a, b, c].
? - [[a, b], c] = [X, Y].
? - [a(b), c(X)] = [Z, c(a)].
? - [X | Y] = [a].```

Selecting an Item:

`third([A, B, C | Rest], C).`

Define a predicate that compares 2 selected list items, e.g. 3 and 4.

Example of use:

```? - compare([a, b, c, d]).
false
? - compare([a, b, c, c]).
true```

Define a predicate that replaces 2 selected list items, e.g. 3 and 4.

```? - replace ([a, b, c, d], X).
X = [a, b, d, c]
true```

## 2. List membership

```belongs(X, [X | _]).
belongs(X, [_ | Ytail]) :- belongs(X, Ytail).```

Exercise

Add the predicate `belongs` to your program.

Check and think about the operation of the following:

```? - belongs(c, [a, b, c, d]).
? - belongs(x, [a, b, c, d]).
? - belongs(X, [a, b, c, d]).
? - belongs(x, a).
? - belongs(X, a).```

## 3. Counting items

```list_length([], 0).
list_length([_ | Tail], Length):-
list_length(Tail, X),
Length is X + 1.```

Exercise

Add the predicate `list_length` to the file.

Check and think about the operation of the following:

`  ? - list_length ([a, b, c], X).`

## 4. Recursive list analysis

(source: LearnPrologNow))

```a2b([], []).
a2b([a | Ta], [b | Tb]): -
a2b(Ta, Tb).```

Exercise

Add the predicate ` a2b ` to the file.

Check and think about the operation of the following:

```  ? - a2b([a, a, a], [b, b, b]).
? - a2b([a, a, a, a], [b, b, b]).
? - a2b([a, s, d], [b, s, d]).

? - a2b([a, a, a, a], X).
? - a2b(X, [b, b]).
? - a2b(X, Y).```

Note: this predicate does “something interesting” only for lists starting with 'a' and 'b'!

## 5. Merging lists

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

Exercise

Add the predicate `list_merge` to the file.

Check and think about the operation of the following:

```? - list_merge([a, b], [c, d], X).
? - list_merge([a, b], X, [c, d]).
? - list_merge([a, b], X, [a, b, c, d]).

? - list_merge(A, B, [a, b, c, d, e]).

? - list_merge([1,2,3], [a, b, c], X).
? - list_merge([1,2,3], [a (e), b (f), c (d, g)], X).

? - list_merge(Before, [5 | After], [1,2,3,4,5,6,7,8,9]).
? - list_merge(_, [A, 5, B, _], [1,2,3,4,5,6,7,8,9]).
? - list_merge(A, [x, x, x | _], [a, b, x, x, c, x, x, x, d, e]).```

Note: add and test the predicate:

`belongs(X, L) :- list_merge(_, [X | _], L).`

Define a predicate that checks if the Item is the last element of the List:

`last(Item, List).`

With and without the use of “list_merge”.

`list_add(X, L, [X | L]).`

In practice, an additional predicate would not be needed here.

Exercise

Add the predicate ` list_add ` to the file.

Check and think about the operation of the following:

```? - list_add(a, [c, d], X).
? - list_add([a, b], [c, d], X).```

## 7. Deleting items

```list_remove(X, [X | Remainder], Remainder).
list_remove(X, [Y | Tail], [Y | Rest]) :-
list_remove(X, Tail, Rest).```

Exercise

Add the predicate `list_remove` to the file.

Check and think about the operation of the following:

```? - list_remove(a, [a, b, a, c, a, a], X).
? - list_remove(a, [a, b, c, d], X).
? - list_remove(c, [a, b, c, d], X).
? - list_remove(c, X, [a, b, c, d]).

? - list_remove(1, X, [a, b, c, d]).```

Note: add and test the predicate:

`list_insert(X, L, Large) :- list_remove(X, Large, L).`

Note: add and test the predicate:

`belongs2 (X, L) :- list_remove(X, L, _).`

## 8. Lists containment

```list_contains(S, L) :-
list_merge(_, L2, L),
list_merge(S, _, L2).```

Exercise

Add the predicate `list_contains` to the file.

Check and think about the operation of the following:

```? - list_contains(a, [a, b, c]).
? - list_contains([a], [a, b, c]).
? - list_contains(X, [a, b, c]).
? - list_contains([X], [a, b, c]).
? - list_contains([X, Y], [a, b, c]).
? - list_contains([X, Y, Z], [a, b, c]).```

## 9. List permutations

```permutation([],[]).
permutation([X | L], P) :-
permutation(L, L1),
list_insert(X, L1, P).

permutation2([], []).
permutation2(L, [X | P]) :-
list_remove(X, L, L1),
permutation2(L1, P).```

Exercise

Add the predicate ` permutation ` to the file.

Check and think about the operation of the following:

```? - permutation([a, b, c], X).
? - permutation2([a, b, c], X).```

## 10. Reversing Lists

```list_reverse([], []).
list_reverse([H | T], L): -
list_reverse(T, R), list_merge(R, [H], L).```

Exercise

Add the predicate `list_reverse ` to the file.

Check and think about the operation of the following:

```? - list_reverse([a, b, c, d], X).
? - list_reverse([a, b, c, d], [d, c, b, a]).```

## 11. Lists and strings

A string in Prolog may be represented by:

• an atom - difficult to process,
• a list of ASCI codes of characters,
• a list of one-letter atoms.

List representation increases the string processing possibilities.

Useful predicate:

```write_string([H | T]) :-
put(H), write_string(T).
write_string([]).```

Another situation: An example of using the built-in predicates ` name ` and ` append ` to transform strings. Predicate ` plural (Noun, Pl) ` - converts an English regular noun from singular to plural.

```plural(Noun, PL) :-
name(Noun, L),
name(s, T),
append(L, T, NL),
name(PL, NL).```

Exercise

Check and think about the operation of the following:

```? - write('ala').
? - write('ala has a cat').
? - write("ala").
? - write("ala has a cat").
? - X = 'a', put(X).
? - X = 'ala', put(X).
? - X = "a", put(X).
? - put(65), put(66), put(67).```

Add the predicates ` write_string ` and ` plural ` to the file.

Check and think about the operation of the following:

```? - write_string("ala has a cat").
? - permutation ("abc", X), write_string(X), nl, fail.
? - list_insert("", "abcdefgh", Z), write_string(Z), nl, fail.```
`? - plural(day, PL).`

## If you want to know more...

1. More lists problems in Polish, but you can get the idea…