Seminary #3

Append 3 lists
append3(L1, L2, L3, R):-
V1 append(L1, L2, R12),
append(R12, L3, R).

append3(L1, L2, L3, R):-

append(L2, L3, R23),
V2
append(L1, R23, R).

append3([H|T], L2, L3, [H|R]):-

append3(T, L2, L3, R).
append3([], [H|T], L3, [H|R]):-
V3 append3([], T, L3, R).
append3([], [], L, L).
 append([], L, L). %mandatory first
append([H|T], L, [H|R]):-
append(T,L,R).
Append 3 lists
append3(L1, L2, L3, R):-
V1 append(L1, L2, R12),
append(R12, L3, R).

append3(L1, L2, L3, R):-

append(L2, L3, R23),
V2
append(L1, R23, R).

append3([H|T], L2, L3, [H|R]):-

append3(T, L2, L3, R).
append3([], [H|T], L3, [H|R]):-
V3 append3([], T, L3, R).
append3([], [], L, L).
Append 3 lists - analysis
|L1|=n1 , |L2|=n2 , |L3|=n3

V1: O(n1) + O(n1+n2)

L1 (1) L2 L3

(2)

V2: O(n2) + O(n1)

L1 (2) L2 (1) L3

V3: O(n1) din clauza 1 + O(n2) din clauza 2 + O(1) → O(n1+n2)

L1 (1) L2 (2) L3
 append([],L,L). append3(L1, L2, L3, R):-
append([H|T],L,[H|R]):- V1 append(L1, L2, R12),
append(T,L,R). append(R12, L3, R).
Append 3 lists - Q? append3(L1, L2, L3, R):-
V2 append(L2, L3, R23),
append(L1, R23, R).
● What are the results and in what
append3([H|T], L2, L3, [H|R]):-
order do they appear in a append3(T, L2, L3, R).
nondeterministic call? append3([], [H|T], L3, [H|R]):-
V3 append3([], T, L3, R).
append3([], [], L, L).
?- append3(X, Y, Z, [1,2]).
V1 V2 V3
X Y Z X Y Z X Y Z
[] [] [1,2] [] [] [1,2] [1,2] [] []
[] [1] [2] [1] [] [2] [1] [2] []
[] [1,2] [] [1,2] [] [] [1] [] [2]
[1] [] [2] [] [1] [2] [] [1,2] []
[1] [2] [] [1] [2] [] [] [1] [2]
[1,2] [] [] [] [1,2] [] [] [] [1,2]

It depends on the order of append/3. If the first clause moves the second list, in the
result it will appear first.
Sublist
● ?- sublist([b,c,d], [a,b,c,d,e]). ✓
● ?- sublist([b,c,d], [a,b,x,c,y,d]). ✗
● ?- sublist([b,c,d], [a,b,x,c,y,b,c,d]). ✓
Sublist
Solution 1:
sublist(S, L):- sublist(S,S,L).

sublist([H|TS], S, [H|TL]):- sublist(TS, S, TL).

sublist([_|TS], S, [_|TL]):- sublist(S,S,TL).
sublist([],_,_).

Solution 2:
sublist([H|TS], [H|TL]):-prefix(TS, TL),!.
sublist(S, [_|TL]):-sublist(S, TL).

% prefix/2 predicate is auxiliary to check whether we have continuity in the sublist

prefix([H|T], [H|R]):-prefix(T,R).
prefix([], _).
Sublist
● Q: Is there another option to find a solution for finding the prefix, based on
non-determinism? Which is it?
Sublist
● Q: Is there another option to find a solution for finding the prefix, based on
non-determinism? Which is it?
○ A: We replace prefix/2 with append/3.
Sublist
Solution 3:
% Q: Is there another option to find a solution for finding the prefix, based on
non-determinism? Which is it?
% A: We replace prefix/2 with append/3.

sublist(S, L):- append(S, _, L).

sublist(S, [_|TL]):-sublist(S, TL).
Sublist
Solution 3:
% Q: Is there another option to find a solution for finding the prefix, based on
non-determinism? Which is it?
% A: We replace prefix/2 with append/3.

sublist(S, L):- append(S, _, L).

sublist(S, [_|TL]):-sublist(S, TL).

If S cannot be a sublist, then we reinitialize. The append/3 predicate verifies if the

decomposition of L, actually starts with S.
Sublist
● Q: What would a solution based on a non-deterministic append look like?
Sublist
● Q: What would a solution based on a non-deterministic append look like?
○ A: The non-deterministic approach based on append/3, would insert the entire list
in the second argument (based on the first clause []) in the beginning, and then it
would keep moving the first element into the first list.
Sublist
● Q: What would a solution based on a non-deterministic append look like?
○ A: The non-deterministic approach based on append/3, would insert the entire list
in the second argument (based on the first clause []) in the beginning, and then it
would keep moving the first element into the first list.

X Y
append([], L, L). [] [1,2,3,4]
append([H|T], L, [H|R]):- [1] [2,3,4]
append(T, L, R). [1,2] [3,4]
[1,2,3] [4]
?- append(X,Y,[1,2,3,4]). [1,2,3,4] []
Sublist
Solution 4:
% Q: What would a solution based on a non-deterministic append look like?
% A:

sublist(S, L):-
append(X, _, L),
append(_, S, X).
Sublist
Solution 4:
% Q: What would a solution based on a non-deterministic append look like?
% A:

sublist(S, L):-
append(X, _, L),
append(_, S, X).

Idea: From all possible decompositions of L, generate the one which has in the first
argument a list which itself decomposed contains our sublist S.
X Y
append([], L, L). [] [1,2,3,4]
append([H|T], L, [H|R]):- [1] [2,3,4]
append(T, L, R). [1,2] [3,4]
[1,2,3] [4]
?- append(X,Y,[1,2,3,4]). [1,2,3,4] []
Sublist
Solution 5:

sublist(S, L):- append3(_, S, _, L).

Idea: From all possible decompositions of L, generate the one which contains the sublist as
the second argument.

The first argument starts with the first element until the second argument (or []). The last
argument contains the last x elements (or []). The second argument is the only one that can
take a group of consecutive elements that can be in the middle of the list.
Minimum FW
min([H|T],M,R):- H<M, !, min(T,H,R).
min([H|T],M,R):- min(T,M,R).
min([], R, R).

min([H|T], R):- min(T, H, R). %wrapper

Complexity: O(n) → traverses a single time

Stable: Yes.
Minimum BW
min([H|T], H):- min(T, X), H<X, !.
min([_|T], X):- min(T, X).
min([H], H).

Complexity: O(n2) for a decreasing array. This happens because when entering
recursion it goes through the first clause every time. When returning from
recursion H<X fails and it must go to the second clause and continue from there
with recursion.
Stabilitate: NO. The first minimum will not be found because it builds the result
from the end; thus, it will take the duplicate.
Minimum BW
min([H|T], H):- min(T, X), H<X, !.
min([_|T], X):- min(T, X).
min([H], H).

Complexity: O(n2) for a decreasing array. This happens because when entering
recursion it goes through the first clause every time. When returning from
recursion H<X fails and it must go to the second clause and continue from there
with recursion.
Stabilitate: NO. The first minimum will not be found because it builds the result
from the end; thus, it will take the duplicate.

Idea: We do not actually need two recursive clauses. Clauses 1 and 3 can be
combined into a single one.
Minimum BW
min([H|T], X):- min(T, X), H>X, !.
min([H|_], H).
 min([H|T], H):- min(T, X), H<X, !.
min([_|T], X):- min(T, X).
min([H], H).
Trace original minimum BW version ?- min([3,2,4], R).

[3,2,4], R1
[2,4], R2
[4] R3 => R3=4 %actually here it fails at [] and backtracks to clause3 for result

Return from recursion

[2,4] R2 → 2<4 ✓ => R2=2
[3,2,4] R1 → 3<2 ✗ => repeat clause 2
[3,2,4] R1
[2,4] R1
[4] R4 => R4=4 %actually here it fails at [] and backtracks to clause3 for result
[2,4] 2<4 ✓ => R1=2
[3,2,4], 2 ✓
Permutations
n! = n * (n-1)!
Recursive call
Clause head n ways to
extract the
first element
Permutations
n! = n * (n-1)!
Recursive call
Clause head n ways to
extract the
first element

● Q: How can we extract all the elements of a list one by one (think
non-deterministic)?
Permutations
n! = n * (n-1)!
Recursive call
Clause head n ways to
extract the
first element

● Q: How can we extract all the elements of a list one by one (think
non-deterministic)?
○ A: member / append
Permutations
n! = n * (n-1)!
Recursive call
Clause head n ways to
extract the
first element

● Q: How can we find the list without the extracted element?

Permutations
n! = n * (n-1)!
Recursive call
Clause head n ways to
extract the
first element

● Q: How can we find the list without the extracted element?

○ A: delete / append
Permutations
perm(L, [X|Y]):-
member(X, L),
delete(L, X, L1),
perm(L1, Y).
Permutations
perm(L, [X|Y]):-
member(X, L),
delete(L, X, L1),
perm(L1, Y).

member(X,L) + delete(L,X,L1) <--> append(A,[X|B], L), append(A,B,L1)

Permutations
perm(L, [X|Y]):-
member(X, L),
delete(L, X, L1),
perm(L1, Y).

member(X,L) + delete(L,X,L1) <--> append(A,[X|B], L), append(A,B,L1)

Idea: We decompose the list L, to extract an element X and then recompose it without the
element X.
Homework
1. Determine if an element is a singleton (appears a single time in the list)
2. With a single traversal switch adjacent elements which are not in increasing
order (will be used in bubble sort).