List Exercise
Lists Recap, append and Exercise
Fariba Sadri
Recap on List Unification
% children_of(Mother, Father, [Child1,..,Childk])
children_of(elizabeth, philip,[charles, ann, edward, andrew]).
children_of(diana, charles, [harry, william]).
children_of(jane, bob, [june]).
children_of(mary, peter, []).
children_of(mo, joe, [charles, james]).
Example Queries:
?-children_of(M, F, [ ]).
?-children_of(M, F, [C]).
?-children_of(M, F, [C|Cs]).
?-children_of(M, F, [C1, C2|Cs]).
?-children_of(M, F, [C1, C2, C3, C4]).
?-children_of(M, F, Children), length(Children, 4).
children_of(elizabeth, philip,[charles, ann, edward, andrew]).
children_of(diana, charles, [harry, william]).
children_of(jane, bob, [june]).
children_of(mary, peter, []).
children_of(mo, joe, [james, charles]).
More Example Queries:
?-children_of(M, bob, Cs).
?-children_of(M, F, [charles|Rest]).
?-children_of(M, F, [ann|Rest]).
?-children_of(M, F, X), member(charles, X).
?-children_of(M, F, X), member(charles, X),
\+ member(ann, X).
Appending Lists: append/3
built-in predicate
append(L1, L2, L) :
L is the result of appending list L1 to
the front of list L2.
e.g. append([a,b],[c,d,e],[a,b,c,d,e])
append([], [1,2], [1,2])
Definition of append
append([ ], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
Use of append/3
?-append([1], [2, 3], [1, 2, 3]).
yes
?-append([1], [2, 3], X).
X = [1,2,3]
?-append(X, [2, 3], [1, 2, 3]).
X = [1]
?-append([1], X, [1, 2, 3]).
X = [2, 3]
?-append(X, Y, [1, 2, 3]) .
(find all splittings of a given list)
X = [ ], Y = [1, 2, 3] ;
X = [1] , Y = [2, 3] ;
X = [1, 2], Y = [3] ;
X = [1, 2, 3], Y = [ ] ;
No
?- append(F, [3|R], [1,2,3,4,5]).
(split at an element)
F=[1,2], R=[4,5]
Exercise
Define
last(E, L) where E is the last element of list L.
Do:
• one version with append, and
• one version without append.
Exercise
Let L be a list of tuples of the form
(Hospital_name, Type) giving the name of a hospital
and its type (nhs or private). Assume all nhs hospitals
come before the private ones in L.
Write a program for
hosp_list(L, NHS, Priv)
that takes such a list L, and produces a list NHS of the
NHS hospital tuples and a list Priv of the private
ones.
10
E.g. Given
L= [(st_thomas, nhs), (st_george, nhs),
(guy, nhs), (bupa, private), (harley, private)]
NHS will be
[(st_thomas, nhs), (st_george, nhs), (guy, nhs)]
and Priv will be
[(bupa, private), (harley, private)]
Do two versions:
1. Using append
2. Using aggregation
Edit the program So:
NHS will be a list of NHS hospitals, e.g.
[st_thomas, st_george, guy]
and Priv will be a list of private hospitals, e.g.
[bupa, harley].
List Processing Styles
E.g. The Bubble Sort Algorithm
[1, 2, 4, 6, 3, 5]
[1, 2, 4, 6, 3, 5]
[1, 2, 4, 3, 6, 5]
[1, 2, 4, 3, 6, 5]
[1, 2, 3, 4, 6, 5]
[1, 2, 3, 4, 6, 5]
[1, 2, 3, 4, 5, 6]
Bubble
bubble(L, L) :- sorted(L).
bubble(L, SL) :-
append(L1, [X, Y|Rest], L),
X>Y,
append(L1, [Y, X|Rest], NewL),
bubble(NewL, SL).
sorted(L) :-
\+ (append(L1, [X, Y|Rest], L), X>Y).
Bubble with a cut
bubble(L, SL) :-
append(L1, [X, Y|Rest], L),
X>Y,
!,
append(L1, [Y, X|Rest], NewL),
bubble(NewL, SL).
bubble(L, L).
Direct recursion or using an accumulator:
Example – Reverse a List
rev([],[]).
rev([H|T],R) :-
rev(T,RT),
append(RT,[H],R).
reverse [1, 2, 3]
reverse [2, 3] add 1 at the end
reverse [3] add 2 at the end, add 1 at the end
reverse [] add 3 at the end, add 2 at the end,
add 1 at the end
[]
[3]
[3, 2]
[3, 2, 1]
Reverse with Accumulator
rev2(L, Inv) :- h_rev(L, [], Inv).
h_rev([], Acc, Acc).
h_rev([H|T], Acc, Inv) :- h_rev(T, [H|Acc], Inv).
Reverse with Accumulator
reverse [1, 2, 3]
List Accumulator Result
[1,2, 3] []
[2, 3] [1]
[3] [2,1]
[] [3,2,1] [3,2,1]
Direct recursion or
using an accumulator
E.g. Summing the elements of a list
[4, 6, 8] —–> 18
With Direct Recursion
sumList([],0).
sumList([N|L],S) :- sumList(L,SumL), S is N+SumL.
[4, 6, 8]
4 [6, 8]
4 6 [8]
4 6 8 []
4 6 8 0
4 6 8
4 14
18
With an accumulator
summing(L, S) :- sum_acc(L, 0, S).
sum_acc([], S, S).
Can also be written as:
sum_acc([], SumSoFar, S) :- S= SumSoFar.
sum_acc([E|Rest], SumSoFar, S) :-
NewSum is SumSoFar+E,
sum_acc(Rest, NewSum, S).
list sum so far final sum
[4, 6, 8] 0
[6, 8] 4
[8] 10
[] 18 18