---
# System prepended metadata

title: TP Prolog - s03 - ISC IL 3a
tags: [prolog]

---

###### 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.
```