###### tags: `prolog`

# TP Prolog - s08 - ISC IL 3a
## Baudin Valentin et Braillard Simon

## Exercice 1

| ?- inverse([a,b,c|DXs]-DXs, ...).
         Où est le problème ?

Le problème est que quand on passe par le cas de base la première fois, `XDs` et `Ys`sont unifiés, et ce n'est pas ce qu'on veut. Par conséquent, ça retourne directement `yes`. C'est pourquoi on doit utiliser `unify_with_occurs_check` afin d'éviter l'unification de `XDs` et `Ys`.

## Exercice 2

% --- inverseDL1(+XDs, ?YDs) : YDs is the D-List inverse of D-List XDs
inverseDL1(Xs-XDs, Ys-YDs) :-
    unify_with_occurs_check(Xs, XDs),
    unify_with_occurs_check(Ys, YDs).
inverseDL1([X|Xs]-DXs, Ys-DYs) :-
    inverseDL1(Xs-DXs, Ys-DDYs),
    DDYs=[X|DYs].

### Solution

| ?- > inverseDL1([a,b,c|Xs]-Xs, Ys-[]) .


Ys = [c,b,a] ? > 


(1 ms) yes

| ?- > inverseDL1(Xs-Xs, Ys-[]) .


Ys = [] ? > 


yes

## Exercice 3

% myList: a list where you can remove from one extremity, and add at both
%    OPERATIONS: new(-X), consultFirst(?Elt), removeFirst(?Elt) 
%                         addFirst(+Elt), addLast(+Elt)
%              maybe: consultLast(?Elt)
%    REPRESENTATION: based on a D-List
%    COMPLEXITY:     CPU O(1), RAM O(n) 

myList_new(Xs-Xs).

myList_apply(Xs-[A|XDs],      addLast(A), Xs-XDs).
myList_apply(Xs-XDs,     addFirst(A), [A|Xs]-XDs).
myList_apply(Xs-XDs,  removeFirst(A), Ys-XDs) :-
    nonvar(Xs),
    Xs = [A|Ys].
myList_apply(Xs-XDs, consultFirst(A), Xs-XDs):-
    nonvar(Xs),
    Xs = [A|_].

### Solution

| ?- > myList_test.
trying(myList_apply(_281-_281,addLast(a),_341))
done(myList_apply([a|_350]-[a|_350],addLast(a),[a|_350]-_350))
trying(myList_apply([a|_350]-_350,addLast(b),_362))
done(myList_apply([a,b|_371]-[b|_371],addLast(b),[a,b|_371]-_371))
trying(myList_apply([a,b|_371]-_371,addLast(c),_383))
done(myList_apply([a,b,c|_392]-[c|_392],addLast(c),[a,b,c|_392]-_392))
trying(myList_apply([a,b,c|_392]-_392,consultFirst(a),_404))
done(myList_apply([a,b,c|_392]-_392,consultFirst(a),[a,b,c|_392]-_392))
trying(myList_apply([a,b,c|_392]-_392,addFirst(d),_423))
done(myList_apply([a,b,c|_392]-_392,addFirst(d),[d,a,b,c|_392]-_392))
trying(myList_apply([d,a,b,c|_392]-_392,consultFirst(d),_444))
done(myList_apply([d,a,b,c|_392]-_392,consultFirst(d),[d,a,b,c|_392]-_392))
trying(myList_apply([d,a,b,c|_392]-_392,removeFirst(d),_463))
done(myList_apply([d,a,b,c|_392]-_392,removeFirst(d),[a,b,c|_392]-_392))
trying(myList_apply([a,b,c|_392]-_392,consultFirst(a),_482))
done(myList_apply([a,b,c|_392]-_392,consultFirst(a),[a,b,c|_392]-_392))
trying(myList_apply([a,b,c|_392]-_392,removeFirst(a),_501))
done(myList_apply([a,b,c|_392]-_392,removeFirst(a),[b,c|_392]-_392))
trying(myList_apply([b,c|_392]-_392,removeFirst(b),_520))
done(myList_apply([b,c|_392]-_392,removeFirst(b),[c|_392]-_392))
trying(myList_apply([c|_392]-_392,addLast(e),_539))
done(myList_apply([c,e|_548]-[e|_548],addLast(e),[c,e|_548]-_548))
trying(myList_apply([c,e|_548]-_548,removeFirst(c),_560))
done(myList_apply([c,e|_548]-_548,removeFirst(c),[e|_548]-_548))
trying(myList_apply([e|_548]-_548,removeFirst(e),_579))
done(myList_apply([e|_548]-_548,removeFirst(e),_548-_548))

true ? > 


(1 ms) yes

## Exercice 4
Une collection de D-Listes peut se représenter de plusieurs façons différentes :
a) une liste de couples
b) un couple de listes ("2 listes parallèles")
c) un couple de D-Listes

### Que fait le prédicat concatDL si on le lance avec comme paramètres deux collections de D-Listes de la forme `b` ?

f_test(Result) :-
    X = [ [a,b|R], [c,d,e|S], [f,g|T] ] - [R,S,T],
    Y = [ [h,i|U], [j,k|V], [l,m,n|W] ] - [U,V,W],
    concatDL(X, Y, Result).

| ?- > f_test(Result) .


Result = [[a,b,h,i|A],[c,d,e,j,k|B],[f,g,l,m,n|C]]-[A,B,C]

yes

Les listes de la collection sont entrecroisées. Cela arrive grâce à ces unifications :

Pour `[a,b|R]`, `(R :[h,i|U])`
Pour `[c,d,e|S]`, `(S :[j,k|V])`
Pour `[f,g|T]`, `(T :[l,m,n|W])`

### Que fait le prédicat suivant si on le lance sur une une collection de D-Listes de la forme `c` ?

%--- g(+CDL, ?Result)
g(([X|As]-[Y])-(Bs-_), X-Y) :- concatDL(_-As, Bs-_, X-Y).

g_test(Result) :-
    La = [ [a,b|A], [c,d,e|B],
    [f,g|C] | Lad ] - Lad,
    DLa = [A,B,C | DLad] - DLad,
    CDLa = La - DLa,
    g(CDLa, Result).

| ?- > g_test(Result).


Result = [a,b,c,d,e,f,g|A]-A

yes
| ?- 

Le prédicat permet de concaténer les listes de la première partie du couple.