Session 4: Lists, the sequel

Exercise 1: basic list-predicates

Define predicates for:

Retrieving the first element of a list: first(Element, List)
Retrieving the last element of a list: last(Element, List)
Removing in a list one element equal to T: remove(T, List, NewList)
Removing in a list ALL elements equal to T: remove_all(T, List, NewList)
Removing in a list of numbers all elements smaller than or equal to N: smaller(N, NumberList, NewNumberList)
Switching the first two elements of a list: switch_first_two(List, NewList). For example a call to switch_first_two([a,b,c,d,e,f], L) should return L = [b,a,c,d,e,f]
Switching every pair of elements in a list: switch_every_two(List, NewList). For example a call to switch_every_two([a,b,c,d,e,f,g], L) should return L = [b,a,d,c,f,e,g]

Exercise 2: sorting a list

In this exercise we will gradually write a program for sorting a list.

Write a predicate that switches the first pair of numbers in a list for which the first number is larger that the second:
switch_unsorted(NumberList, NewNumberList). For example, ?- switch_unsorted([1,2,4,7,6,9,8], L). returns L = [1,2,4,6,7,9,8]. If there is no unsorted pair then no numbers should be switched.
Write a predicate that applies ten times the predicate switch_unsorted/2. The result of the first call is used as input for the second call etc...:
```
ten_times(NumberList0, NumberList10):-
        switch_unsorted(NumberList0, NumberList1),
        switch_unsorted(NumberList1, NumberList2), 
        ...
        switch_unsorted(NumberList9, NumberList10).
```
Try the following calls to ten_times/2 on your PC:
```
?- ten_times([2,1,4,3],Result).
?- ten_times([5,4,3,2,1],Result).
?- ten_times([6,5,4,3,2,1],Result).
```
Try to find a shorter definition than the above predicate ten_times/2 (or: make it easy to iterate it 100 times instead of 10 times).
Write a predicate that succeeds only when the argument is a sorted list: is_sorted(NumberList).
Write a predicate sort/2 that applies the predicate switch_unsorted/2 on a list until that list is sorted.

Exercise 3: nested lists

Given a list of lists, example [[a,b,c], [d,e,f]], write a predicate that flattens the list: make one list with all the elements. For the example this should return [a,b,c,d,e,f]. (Hint: this can be solved using conc/3 (in SWI this is already implemented as append/3)).
Suppose you have a list with lists that represents a matrix:
```
[[a11,a12,a13],
 [a21,a22,a23],
 [a31,a32,a33]]
```
Then write a predicate that computes the transposed matrix:
```
[[a11,a21,a31],
 [a12,a22,a32],
 [a13,a22,a33]]
```
Notice that your code should work for any square matrix, not only for a 3 by 3 matrix.
Now suppose you have a list which could recursively contain lists: example [a,[a,d,[2,3], w, [2], []], [er]]. Write a predicate that returns a list with all elements: flatten(RecList, List). For the example the returned list should be [a,a,d,2,3,w,2,er].

Exercise 4: sets
Lists are often used as a representation for sets. In this exercise we want to make a data abstraction for a set, using a list as internal representation. Remark that in a list an element could occur more than once, in a normal set this is not the case.

Define the following predicates for a set:

empty_set(Set)
% returns an empty set, or check if the set is empty
% when the argument is instantiated.

add_to_set(Element, Set, NewSet) % add an element to a set

member_of_set(Element, Set) % true if the element is a member

delete_from_set(Element, Set, NewSet)
% delete the element from the set if it occurs, otherwise
% the new set is unchanged

Test the code above with some queries and little programs. Example:

test_set(Set):-
        empty_set(Empty_set),
        add_to_set(a, Empty_set, Set1),
        add_to_set(b, Set1, Set2),
        delete_from_set(a, Set2, Set).

Now define the following predicates:

union_set(Set1, Set2, Union)

intersect_sets(Set1, Set2, Intersection)

union_list_of_sets(Sets, Union) 
% The first argument contains a list of sets 
%  of which the union has to be computed.

difference_set(Set1, Set2, Difference)
% Difference contains all elements from Set1 not a member of Set2.