Prolog workshops
Workshop 1 - 5 are Haskell topics.
The code in workshop is guaranteed to be error-free.
Workshop 6
Some files required:
Please put them in same dir as workshop 6 source code
:- ensure_loaded(borders).
:- ensure_loaded(cities).
:- ensure_loaded(countries).
:- ensure_loaded(rivers).
/*
Q1 borders(X,australia).
Q2 borders(B, france), borders(B, spain).
Q3 borders(B, france), borders(B, spain), country(B,_,_,_,_,_,_,_).
*/
/* Q4
country/1
country(C) is True if C is a country
*/
country(A) :-
country(A,_,_,_,_,_,_,_).
/* Q5
larger/2
larger(C1, C2) holds when C1 is larger
country(Country,Region,Latitude,Longitude,
Area (sqmiles),
Population,
Capital,Currency)
*/
larger(C1, C2) :-
country(C1,_,_,_,A1,_,_,_),
country(C2,_,_,_,A2,_,_,_),
A1 > A2.
/*
river_country/2
river_country(River, Country) holds if:
- River is a river
- Country is a country
- River flows into or outof Country
country_region/2
country_region(Country, Region) holds if:
- Country is a country in Region
*/
river_country(River, Country) :-
river(River, L),
country(Country),
member(Country, L).
country_region(Country, Region) :-
country(Country, Region, _,_,_,_,_,_).
Workshop 7
/* Q1
list_of/2
list_of(Elt, List) holds if:
- every element if List equals to Elt
Works in any mode
*/
list_of(_,[]).
list_of(E, [E|T]) :-
list_of(E,T).
/* Q2
all_same/1
all_same(List) holds if:
- All elements are same
*/
all_same([]).
all_same([_]).
all_same([E|[E|T]]) :-
all_same([E|T]).
/* Q3
adjacent/3
adjacent(E1, E2, List) holds if:
E1 appear immediately before E2 in List
*/
adjacent(E1, E2, List) :-
append(_, [E1, E2|_], List).
/* Q4
same predicate as Q3, but implement it recursively
*/
adjacent_r(E1, E2, [E1,E2|_]).
adjacent_r(E1, E2, [_|T]) :-
adjacent_r(E1, E2, T).
/* Q5
before/3
before(E1,E2,List) holds if:
- E1 occurs before E2 in List
Solve this recursively.
If List starts with E1, then we need to make sure
E2 is in tail. If not, apply this to tail.
*/
before(E1, E2, [E1|T]) :-
member(E2,T).
before(E1, E2, [_|T]) :-
before(E1, E2, T).
/* Q6
tree/3
tree(L, N, R) represents a tree with label N and left
sub-tree L and right sub-tree R. Atom empty is Leaf.
intset_member/2
intset_member(N, Set) holds if:
- N is a member of Set
*Avoid unnecessary recursion by comparing N with label of Set
intset_insert/3
intset_insert(N, Set0, Set) where
Set has N as a member. There should be no duplicated elements
*/
intset_member(N, tree(_,N,_)).
intset_member(N, tree(L,N0,_)) :-
N < N0,
intset_member(N, L).
intset_member(N, tree(_, N0, R)) :-
N >= N0,
intset_member(N,R).
intset_insert(N, empty, tree(empty, N, empty)).
intset_insert(N, tree(L,N,R), tree(L,N,R)).
intset_insert(N, tree(L1,N1,R1), tree(L2,N1,R1)) :-
N < N1,
intset_insert(N, L1, L2).
intset_insert(N, tree(L1,N1,R1), tree(L1,N1,R2)) :-
N >= N1,
intset_insert(N, R1, R2).
Workshop 8
/* Q1
Convert the code to tail recursive version
sumList([], 0).
sumList([N|Ns], Sum) :-
sumList(Ns, Sum0),
Sum is Sum0 + N.
Solve this by introducing an accumulator A
When the list is empty, the sum is A
Otherwise, Add head to A and recursively call
predicate.
*/
sumListA([],A,A).
sumListA([N|Ns], Sum, A) :-
Sum0 is A + N,
sumListA(Ns, Sum, Sum0).
sumList(L, Sum) :-
sumListA(L, Sum, 0).
/* Q2
a binary tree defined as:
tree(empty).
tree(node(Left, _, Right)) :-
tree(Left),
tree(Right).
tree_list/2
tree_list(Tree, List) holds if:
- List is list of all elem of tree
- Left to Right order
*/
tree_list(empty, []).
tree_list(node(Left,Elt,Right), List) :-
tree_list(Left, List1),
tree_list(Right, List2),
append(List1, [Elt|List2], List).
/* Q3
Same as last question, but not use append
Make sure the cost is proportional to number of
nodes in tree.
Refer to tail recursion optimization
It can be solved like this:
We are basically adding the tree to accumulator to get
the result.
Left hand side:
adding left tree to accumulator A where A is calculated from
right hand side and the node of current tree
Right hand side:
The accumulator is current accumulator passed as argument
*/
tree_list_a(empty, A, A).
tree_list_a(node(Left, V, Right), List, A) :-
tree_list_a(Left, List, List1),
List1 = [V|List2],
tree_list_a(Right, List2, A).
/* Q4
list_tree_b/2
list_tree_b(List, Tree) holds if:
- List is a list of elements in Tree
- Tree is balanced
Work in the mode where List is proper list
*/
/*
The below solution is not efficient because
it tries to find the appropriate list combination
one by one
list_tree_b([],empty).
list_tree_b(List, node(Left, V, Right)) :-
append(List_L, List_R_V, List),
List_R_V = [V| List_R],
length(List_L, Len_L),
length(List_R, Len_R),
Len_L - Len_R =< 1,
list_tree_b(List_L, Left),
list_tree_b(List_R, Right).
A better solution is to specify the length at
the beginning
*/
list_tree_b_([], empty).
list_tree_b_([E|List], node(Left,Elt,Right)) :-
length(List, Len),
Len2 is Len // 2,
length(Front, Len2),
append(Front, [Elt|Back], [E|List]),
list_tree_b_(Front, Left),
list_tree_b_(Back, Right).
Workshop 9
/* Q1
same_elements/2
same_element(L1, L2) holds if:
- Elems in L1 are in L2
- Vice versa
Only work in mode where both lists are ground
*/
members([],_).
members([H|T], L) :-
member(H, L),
members(T,L).
same_elements(L1, L2) :-
members(L1, L2),
members(L2, L1).
/* Q2
same as previous one, make it Nlog(N)
in time complexity
Note that prolog sort removes duplicates
*/
same_elements_log(L1, L2) :-
sort(L1, Sorted),
sort(L2, Sorted).
/* Q3
times/4
times(W,X,Y,Z). holds if:
- All arguments are integers
- W*X + Y = Z
- 0 <= Y < |W|
Works when W and at least on of X and Z are bound to integer
Deterministic when 3 of 4 args are ground
*/
/* Q4
Solve water container problem
two containers: 5L and 3L. The goal is to get
4L water in 5L container.
fill/1
fill(To) where To is the capacity of container to fill
empty/1
empty(From) where From is capacity of container to empty
pour/2
pour(From, To)
container/1
Solve this by first define all the possible next operations and their effects
Bring non-deteministic movement by using Prolog Variables
It eventually reach the goal, and all the actions after that are don't cares
*/
next(fill(3), [_,B], [3, B]).
next(fill(5), [A,_], [A, 5]).
next(empty(3), [_,B], [0,B]).
next(empty(5), [A,_], [A,0]).
next(pour(3,5), [A,B], [C,D]) :-
(
A + B > 5 ->
C is A - (5-B),
D is 5;
C is 0,
D is B + A
).
next(pour(5,3), [A,B], [C,D]) :-
(
A + B > 3 ->
C is 3,
D is B - (3-A);
C is B + A,
D is 0
).
container([_,4], _, _):-
print("success").
container(State, History, [Action|Actions]) :-
next(Action, State, State_),
\+ member(State_, History),
container(State_, [State_|History], Actions).
container(Action) :-
container([0,0], [], Action).