Solutions for Session 4

1.  

   • first(X, [X|_]).

   • last(X, [X]).
     last(X, [_|Z]):-
     	last(X, Z).
     

   • remove(El, [El|List], List).
     remove(El, [El1|Tail], [El1|Tail1]):-
             not(El=El1), % could also be solved with other constructions
     	remove(El, Tail, Tail1).
     

   • remove_all(_, [], []).
     remove_all(El, [El|Tail], Tail1):- 
     	remove_all(El, Tail, Tail1).
     remove_all(El, [El1|Tail], [El1|Tail1]):-
     	not(El = El1),
     	remove_all(El, Tail, Tail1).
     

   • smaller(_, [], []).
     smaller(N, [M|Tail], Tail1):-
     	 M =< N,
     	 smaller(N, Tail, Tail1).
     smaller(N, [M|Tail], [M|Tail1]):-
              M > N,
     	 smaller(N, Tail, Tail1).
     

   • switch_first_two([X, Y| Tail], [Y, X|Tail]).

   • switch_every_two([], []).
     switch_every_two([X], [X]).
     switch_every_two([X, Y|Tail], [Y, X|Tail1]):-
     	switch_every_two(Tail, Tail1).
     

2.  

   • switch_unsorted([], []).
     switch_unsorted([X], [X]).
     switch_unsorted([X, Y|List], [Y,X|List]):-
     	X > Y.
     switch_unsorted([X, Y|List], [X|Rlist]):-
     	X =< Y,
     	switch_unsorted([Y|List],Rlist).
     

   • ten_times(NumberList0, NumberList10):-
     	switch_unsorted(NumberList0, NumberList1),
     	switch_unsorted(NumberList1, NumberList2),
     	switch_unsorted(NumberList2, NumberList3),
     	switch_unsorted(NumberList3, NumberList4),
     	switch_unsorted(NumberList4, NumberList5),
     	switch_unsorted(NumberList5, NumberList6),
     	switch_unsorted(NumberList6, NumberList7),
     	switch_unsorted(NumberList7, NumberList8),
     	switch_unsorted(NumberList8, NumberList9),
     	switch_unsorted(NumberList9, NumberList10).
     

     Some queries:

     ?- ten_times([2,1,4,3],Result).
     
     Result = [1, 2, 3, 4] 
     
     Yes
     ?- ten_times([5,4,3,2,1],Result).
     
     Result = [1, 2, 3, 4, 5] 
     
     Yes
     ?- ten_times([6,5,4,3,2,1],Result).
     
     Result = [2, 3, 4, 5, 6, 1] 
     
     Yes
     

     The shorter solution:

     ten_times_2(List1,List2):-
     	switch_N_times(List1,List2,10).
     
     switch_N_times(L,L,0).
     switch_N_times(L1,L2,N):-
     	N>0,
     	switch_unsorted(L1,Temp),
     	Next is N-1,
     	switch_N_times(Temp,L2,Next).
     

   • is_sorted([]).
     is_sorted([_]).
     is_sorted([X, Y|List]):-
     	X =< Y,
     	is_sorted([Y|List]).
     

   • sort2(List,List):-
     	is_sorted(List).
     sort2(List,Result):-
     	not(is_sorted(List)),
     	switch_unsorted(List,Temp),
     	sort2(Temp,Result).
     

     Note that this predicate indeed sorts the given list!
     (the predicate is called 'sort2' because SWI already has a predicate 'sort' and we cannot re-define that ourselves)
3.  

   • flatten_list_of_lists([], []).
     flatten_list_of_lists([List|Lists], Result):-
     	flatten_list_of_lists(Lists, Result1),
     	conc(List, Result1, Result).
     
     conc([],X, X).
     conc([H|T], X, [H|T1]):-
     	conc(T, X, T1).
     

   • We use the predicate split_matrix/3 that splits a given matrix into its first column and the rest of the matrix: e.g. ?- split_matrix([[1,2,3],[4,5,6]],FirstCol,Rest). results in FirstCol=[1,4] and Rest=[[2,3],[5,6]].

     split_matrix([], [], []).
     split_matrix([[A|B]|C], [A|First], [B|WithoutFirst]):-
     	split_matrix(C, First, WithoutFirst).
     	
     transpose([[]|_], []).
     transpose(Matrix, [FirstColumn|TransposedRestMatrix]):-
             % FirstColumn will become the first row in the transposed matrix
     	split_matrix(Matrix, FirstColumn, RestMatrix),
     	transpose(RestMatrix, TransposedRestMatrix).
     

   • flatten([], []).
     flatten([X|Y], List):-
     	X = [_|_],
     	flatten(X,List1),
     	flatten(Y, List2),	
     	conc(List1,List2,List).
     flatten([X|Y], [X|List]):-
     	not(X = [_|_]),
     	flatten(Y, List).
     

4.  

   • empty_set([]).
     
     add_to_set(Element, [], [Element]).
     add_to_set(Element, [Element|Set], [Element|Set]).
     add_to_set(Element, [Element1|Set], [Element1|Set1]):-
             not(Element = Element1),
             add_to_set(Element, Set, Set1).
     
     member_of_set(Element, [Element|_]).
     member_of_set(Element, [_|Set]):-
             member_of_set(Element, Set).
     
     delete_from_set(_, [], []).
     delete_from_set(Element, [Element|Set], Set).
     delete_from_set(Element, [Other|Set], [Other|Set1]):-
             not(Other = Element),
             delete_from_set(Element, Set, Set1).
     

   • union_set([], Set, Set).
     union_set([Element|Set1], Set2, Union):-
             add_to_set(Element, Set2, Set3),
             union_set(Set1, Set3, Union).
     
     intersect_sets([], _, []).
     intersect_sets([Element|Set1], Set2, [Element|Intersection1]):-
             member_of_set(Element, Set2),
             intersect_sets(Set1, Set2, Intersection1).
     intersect_sets([Element|Set1], Set2, Intersection):-
             not(member_of_set(Element, Set2)),
             intersect_sets(Set1, Set2, Intersection).
     
     union_list_of_sets([], []).
     union_list_of_sets([Set1|Sets], Union):-
             union_list_of_sets(Sets, Union1),
             union_set(Set1, Union1, Union).
     
     difference_set([], _, []).
     difference_set([Element|Set1], Set2, Difference):-
             member_of_set(Element, Set2),
             difference_set(Set1, Set2, Difference).
     difference_set([Element|Set1], Set2, [Element | Difference1]):-
             not(member_of_set(Element, Set2)),
             difference_set(Set1, Set2, Difference1).