###### tags: `prolog`
# TP Prolog - s03 - ISC IL 3a
## Baudin Valentin et Braillard Simon
## Exercice 1
### Partition
```prolog=
partition(_P, [], [], []).
partition(P, [L|Ls], Ss, [L|Gs]) :-
L > P,
partition(P, Ls, Ss, Gs).
partition(P, [L|Ls], [L|Ss], Gs) :-
L =< P,
partition(P, Ls, Ss, Gs).
```
#### Output
```
| ?- > partition(3, [1, 2, 3, 4, 5], Ss, Gs) .
Gs = [4,5]
Ss = [1,2,3] ?
```
### QuickSort
```prolog=
quickSort([], []).
quickSort([P|Ls], Ss) :-
partition(P, Ls, As, Bs),
quickSort(As, AsSorted),
quickSort(Bs, BsSorted),
append(AsSorted, [P|BsSorted], Ss).
```
#### Output
```
qsorttest .
Input list: [4,5,3,6,8,2]
Sorted result: [2,3,4,5,6,8]
```
## Exercice 2
### Iterative List
```prolog!
% itrList : Iterative List ADT, with current arc
% Operations :
% new(-X), goToNext, insertAfter(+X),
% isFirst, goToPrev, consultAfter(?X),
% isLast, removeAfter(?Removed)
% Representation :
% e(ListTowardsFirst, ListTowardsEnd)
itrList_new(e([], [])).
itrList_apply(e(Xs,[Y|Ys]), goToNext, e([Y|Xs],Ys)) .
itrList_apply(e([X|Xs],Ys), goToPrev, e(Xs, [X|Ys])) .
itrList_apply(e(Xs, Ys), insertAfter(A), e(Xs, [A|Ys])) .
itrList_apply(e(Xs, [Y|Ys]), removeAfter(Y), e(Xs, Ys)) .
itrList_apply(e(Xs, [Y|Ys]), consultAfter(Y), e(Xs, [Y|Ys])) .
itrList_apply(e([], Ys), isFirst, e([], Ys)) .
itrList_apply(e(Xs, []), isLast, e(Xs, [])) .
```
#### Output
```
| ?- > itrList_test .
trying(itrList_apply(e([],[]),insertAfter(a),_319))
done(itrList_apply(e([],[]),insertAfter(a),e([],[a])))
trying(itrList_apply(e([],[a]),insertAfter(b),_340))
done(itrList_apply(e([],[a]),insertAfter(b),e([],[b,a])))
trying(itrList_apply(e([],[b,a]),goToNext,_361))
done(itrList_apply(e([],[b,a]),goToNext,e([b],[a])))
trying(itrList_apply(e([b],[a]),consultAfter(a),_382))
done(itrList_apply(e([b],[a]),consultAfter(a),e([b],[a])))
trying(itrList_apply(e([b],[a]),removeAfter(a),_403))
done(itrList_apply(e([b],[a]),removeAfter(a),e([b],[])))
trying(itrList_apply(e([b],[]),isLast,_422))
done(itrList_apply(e([b],[]),isLast,e([b],[])))
trying(itrList_apply(e([b],[]),insertAfter(d),_441))
done(itrList_apply(e([b],[]),insertAfter(d),e([b],[d])))
trying(itrList_apply(e([b],[d]),goToPrev,_462))
done(itrList_apply(e([b],[d]),goToPrev,e([],[b,d])))
trying(itrList_apply(e([],[b,d]),consultAfter(_294),_483))
done(itrList_apply(e([],[b,d]),consultAfter(b),e([],[b,d])))
Test passed successfully.
```
## Exercice 3
### BST
```prolog!
% bst : Map (dictionary) ADT (with numbers as keys)
% Operations :
% new(-X), put(+Key, +Value),
% remove(+Key), get(+Key, -Value),
% Representation : with binary search tree
% nil, or n(Key, Value, LeftBST, RightBST)
bst_new(nil).
bst_apply(n(K,_,L,R), put(K,Val), n(K,Val,L,R)).
bst_apply(nil, put(K,Val), n(K,Val,nil,nil)).
bst_apply(n(K1,V,L,R), put(K,Val), n(K1,V,L1,R)) :- K < K1,
bst_apply(L, put(K,Val), L1).
bst_apply(n(K1,V,L,R), put(K,Val), n(K1,V,L,R1)) :- K > K1,
bst_apply(R, put(K,Val), R1).
% --- bst_apply(???, remove(K), ???)...
% 5 rules :
% - empty tree
% - reached node without right child
% - reached node with right child (needs left rotation)
% - current node is smaller
% - current node is greater
bst_apply(nil, remove(_K), nil) .
bst_apply(n(_K, _V, L, nil), remove(_K), L) .
bst_apply(n(K, V, L, n(K1,V1,L1,R1)), remove(K), n(K1, V1, N, R1)) :-
bst_apply(n(K,V,L,L1), remove(K), N).
bst_apply(n(K1,V1,L1,R1), remove(K), n(K1,V1,L2,R1)) :-
K < K1,
bst_apply(L1, remove(K), L2).
bst_apply(n(K1,V1,L1,R1), remove(K), n(K1,V1,L1,R2)) :-
K > K1,
bst_apply(R1, remove(K), R2).
% --- bst_apply(???, get(K,Val), ???)...
% Correct current node
bst_apply(n(K,V,L,R), get(K,V), n(K,V,L,R)) .
% Current node is too big
bst_apply(n(K1,V1,L,R), get(K,V), n(K1,V1,L,R)) :-
K < K1,
bst_apply(L, get(K,V), L) .
% Current node is too small
bst_apply(n(K1,V1,L,R), get(K,V), n(K1,V1,L,R)) :-
K > K1,
bst_apply(R, get(K,V), R) .
```
#### Output
```!
| ?- > bst_test .
trying(bst_apply(nil,put(10,1),_339))
done(bst_apply(nil,put(10,1),n(10,1,nil,nil)))
trying(bst_apply(n(10,1,nil,nil),put(20,2),_360))
done(bst_apply(n(10,1,nil,nil),put(20,2),n(10,1,nil,n(20,2,nil,nil))))
trying(bst_apply(n(10,1,nil,n(20,2,nil,nil)),put(15,9),_389))
done(bst_apply(n(10,1,nil,n(20,2,nil,nil)),put(15,9),n(10,1,nil,n(20,2,n(15,9,nil,nil),nil))))
trying(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),nil)),get(10,_291),_426))
done(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),nil)),get(10,1),n(10,1,nil,n(20,2,n(15,9,nil,nil),nil))))
trying(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),nil)),put(30,3),_447))
done(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),nil)),put(30,3),n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,nil,nil)))))
trying(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,nil,nil))),put(25,8),_484))
done(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,nil,nil))),put(25,8),n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,n(25,8,nil,nil),nil)))))
trying(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,n(25,8,nil,nil),nil))),remove(40),_529))
done(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,n(25,8,nil,nil),nil))),remove(40),n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,n(25,8,nil,nil),nil)))))
trying(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,n(25,8,nil,nil),nil))),remove(20),_566))
done(bst_apply(n(10,1,nil,n(20,2,n(15,9,nil,nil),n(30,3,n(25,8,nil,nil),nil))),remove(20),n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil))))
trying(bst_apply(n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil)),get(30,_304),_613))
done(bst_apply(n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil)),get(30,3),n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil))))
trying(bst_apply(n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil)),get(15,_307),_637))
done(bst_apply(n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil)),get(15,9),n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil))))
trying(bst_apply(n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil)),get(25,_310),_667))
done(bst_apply(n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil)),get(25,8),n(10,1,nil,n(30,3,n(25,8,n(15,9,nil,nil),nil),nil))))
Test passed successfully.
```
{"metaMigratedAt":"2023-06-17T10:53:15.481Z","metaMigratedFrom":"Content","title":"TP Prolog - s03 - ISC IL 3a","breaks":true,"contributors":"[{\"id\":\"8c5c3788-11df-452f-9374-6e1552e561a2\",\"add\":5572,\"del\":3},{\"id\":\"eb2933d9-44da-4ddd-b209-34f78dde26fa\",\"add\":712,\"del\":0}]"}