Práctica 5 (Paradigmas)

1. TODO: formatear. Practica 2014

%ej 3 natural(0). natural(suc(X)) :- natural(X).

menorOIgual(X,X) :- natural(X). menorOIgual(X, suc(Y)) :- menorOIgual(X, Y).

%ej4 %concatenar(?Lista1,?Lista2,?Lista3) concatenar([],L,L). concatenar([X | XS], L, [X | OTRA] ) :- concatenar(XS,L,OTRA).

%Ej5 %i. last(?L, ?U), donde U es el ultimo elemento de la lista L.

last([X], X). last([_|XS], S) :- last(XS, S).

%reverse(+L, -L1), donde L1 contiene los mismos elementos que L, pero en orden inverso. reverse([], []). reverse([X|XS], L) :- reverse(XS, M), append(M, [X], L).

%iii. maxlista(+L, -M) y mnlista(+L, -M), donde M es el m ́aximo/m ́ınimo de la lista L. maxlista([X], X). maxlista([X|XS], X) :- maxlista(XS, Z), X >= Z. maxlista([X|XS], Z) :- maxlista(XS, Z), X < Z.

minlista([X], X). minlista([X|XS], X) :- minlista(XS, Z), X =< Z. minlista([X|XS], Z) :- minlista(XS, Z), X > Z.

%iv. prefijo(?P, +L), donde P es prefijo de la lista L.

prefijo(P, L) :- append(P, _, L).

%v. sufijo(?S, +L), donde S es sufijo de la lista L. sufijo(S, L) :- append(_, S, L).

%vi. sublista(?S, +L), donde S es sublista de L. sublista(S, L) :- prefijo(P, L), sufijo(S, P).

%vii. pertenece(?X, +L), que es verdadero sii el elemento X se encuentra en la lista L pertenece(X, [X|_]). pertenece(X, [_|LS]) :- pertenece(X, LS).

%ej6 %Definir el predicado aplanar(+Xs, -Ys), que es verdadero sii Ys contiene los elementos de todos los niveles de %Xs, en el mismo orden de aparicion. Los elementos de Xs son enteros, ́atomos o nuevamente listas, de modo que %Xs puede tener una profundidad arbitraria. Por el contrario, Ys es una lista de un solo nivel de profundidad.

isList([_|_]). isList([]).

aplanar([], []). aplanar([X | XS], YS) :- isList(X), aplanar(X, Z), aplanar(XS, W), append(Z, W, YS). aplanar([X | XS], YS) :- \+isList(X), aplanar(XS, W), append([X], W, YS).

%ej7 %i. palindromo(+L, -L1), donde L1 es un pal ́ındromo construido a partir de L. %Ejemplo: palindromo([a,b,c], [a,b,c,c,b,a]).

%????EL palindromo de ejemplo o todos los palindromos formables con elementos de L? palindromo(L, P) :- reverse(L, R) ,append(L, R, P).

%doble(?L, ?L1), donde cada elemento de L aparece dos veces seguidas en L1. %Ejemplo: doble([a,b,c], [a,a,b,b,c,c]).

doble([],[]). doble(L, Y) :- nonvar(L), L = [X|XS], doble(XS, Z), append([X, X], Z, Y). doble(X,Y) :- var(X), Y = [Z,Z|Zs], doble(W,Zs), append([Z],W,X).

%iii. iesimo(?I, +L, -X), donde X es el I- ́esimo elemento de la lista L. %Ejemplo: iesimo(2, [10, 20, 30, 40], 20).

iesimo(1, [X|_], X). iesimo(I, [_|LS], X) :- nonvar(I), I > 1, N is I-1, iesimo(N, LS, X). iesimo(I, L, X) :- var(I), length(L, N), between(2,N, I), iesimo(I, L, X).

%ej8 desde(X,X). desde(X,Y) :- var(Y), N is X+1, desde(N,Y). desde(X,Y) :- nonvar(Y), Y > X.

%Ejercicio 9 %i. interseccion(+L1, +L2, -L3), tal que L3 es la interseccion sin repeticiones de las listas L1 y L2, respe- %tando en L3 el orden en que aparecen los elementos en L1.

%CONSULTAR REPETICION DE RESULTADOS interseccion([], _, []). interseccion([L|LS], L2, L3) :- member(L, L2), interseccion(LS, L2, T), member(L,T), T = L3. interseccion([L|LS], L2, L3) :- member(L, L2), interseccion(LS, L2, T), \+member(L,T), append([L], T, L3). interseccion([L | LS], L2, L3) :- \+member(L, L2), interseccion(LS, L2, L3).

%ii. split(N, L, L1, L2), donde L1 tiene los N primeros elementos de L, y L2 el resto. Si L tiene menos de N %elementos el predicado debe fallar. ¿Cuan reversible es este predicado? Es decir, ¿qu ́e par ́ametros pueden %estar indefinidos al momento de la invocaci ́on?

%(El between arranca de 1 porque si arranca con 0 entra 2 veces a la primer clausula) splitt(0, L, [], L). splitt(N, [L|LS], L1, L2) :- nonvar(N), N > 0, M is N-1, splitt(M, LS, Z1, Z2), append([L], Z1, L1), L2 = Z2. splitt(N, L, L1, L2) :- var(N), length(L, LEN), between(1, LEN, I), splitt(I, L, L1, L2).

%iii. borrar(+ListaOriginal, +X, -ListaSinXs), que elimina todas las ocurrencias de X de la lista

borrar([], _, []). borrar([L|LS], X, Z) :- L = X, borrar(LS, X, Z). borrar([L|LS], X, Z) :- L \= X, borrar(LS, X, W), append([L], W, Z).

%iv. sacarDuplicados(+L1, -L2), que saca todos los elementos duplicados de la lista L1. sacarDuplicados([], []). sacarDuplicados([L|LS], L2) :- borrar(LS, L, Z), sacarDuplicados(Z, W), append([L], W, L2).

%v. reparto(+L, +N, -LListas) que tenga exito si LListas es una lista de N listas (N ≥ 1) de cualquier %longitud - incluso vac ́ıas - tales que al concatenarlas se obtiene la lista L.

reparto(L, 1, [L]). reparto(L, N, LL) :- N > 1, M is N-1, length(L, LEN), between(0, LEN, I), splitt(I, L, L1, L2), reparto(L2, M, R), append([L1], R, LL).

%vi. repartoSinVacias(+L, -LListas) similar al anterior, pero ninguna de las listas de LListas puede ser %vac ́ıa, y la longitud de LListas puede variar.

repartoSinVacias([], []). repartoSinVacias([X], X). repartoSinVacias(L, LL) :- length(L, LEN), LEN > 1, between(1, LEN, I), splitt(I, L, L1, L2), repartoSinVacias(L2, R), append([L1], R, LL).

%Ej12 %nil, si es vacio. %bin(izq, v, der), donde v es el valor del nodo, izq es el sub arbol izquierdo y der es el sub arbol derecho.

vacio(nil).

raiz(bin(_, V, _), V).

maximo(X,Y,Y) :- X < Y. maximo(X,Y,X) :- X >= Y.

altura(nil, 0). altura(bin(I, _, D), H) :- altura(I, HI), altura(D, HD), maximo(HD,HI,X), H is 1+X.

cantidadDeNodos(nil, 0). cantidadDeNodos(bin(I, _, D), N) :- cantidadDeNodos(I, NI), cantidadDeNodos(D, DI), N is NI+DI+1.

%Ejercicio 13 %i. inorder(+AB,-Lista), que tenga ́exito si AB es un ́arbol binario y Lista la lista de sus nodos seg %un el recorrido inorder

inorder(nil, []). inorder(bin(I, V, D), L) :- inorder(I, LI), inorder(D, LD), append(LI, [V], LIV), append(LIV, LD, L).

%ii. arbolConInorder(+Lista,-AB), version inversa del predicado anterior.

arbolConInorder([], nil). arbolConInorder(L, A) :- length(L, LEN), N is LEN-1, between(0, N, H), splitt(H, L, RI, RD), arbolConInorder(RI, I), RD = [V|R], arbolConInorder(R, D), A = bin(I,V,D).

testACI(1) :- arbolConInorder([5,1,7,8],A), inorder(A, [5,1,7,8]).

%iii. aBB(+T), que sera verdadero si T es unarbol binario de busqueda.

aBB(bin(nil, _, nil)). aBB(bin(nil, V, D)) :- \+ D=nil, raiz(D, VD), VD > V, aBB(D). aBB(bin(I, V, nil)) :- \+ I=nil, raiz(I, VI), VI < V, aBB(I). aBB(bin(I,V,D)) :- \+ D=nil, \+ I=nil, raiz(I, VI), VI < V, aBB(I), raiz(D, VD), VD > V, aBB(D).

%iv. aBBInsertar(+X, +T1, -T2), donde T2 resulta de insertar X en orden en el arbol T1.

aBBInsertar(X, nil, bin(nil, X, nil)). aBBInsertar(X, bin(I,V,D), bin(I,V,D)) :- X = V. aBBInsertar(X, bin(I,V,D), A) :- X < V, aBBInsertar(X, I, R), A = bin(R, V, D). aBBInsertar(X, bin(I,V,D), A) :- X > V, aBBInsertar(X, D, R), A = bin(I, V, R).

%Ejercicio 14 %Definir el predicado coprimos(-X,-Y), que genere uno a uno todos los pares de n ́ %umeros naturales coprimos (esdecir, cuyo maximo comun divisor es 1), sin repetir resultados. %Usar la funci ́on gcd del motor aritmetico.

gcd(X, Y, G) :- X = Y, G = X. gcd(X, Y, G) :- X < Y, Y1 is Y - X, gcd(X, Y1, G). gcd(X, Y, G) :- X > Y, gcd(Y, X, G).

generarPares(X,Y) :- desde(0, D), between(0, D, X), Y is D-X.

coprimos(X,Y) :- generarPares(X,Y), \+ X = 0, \+ Y = 0, gcd(X,Y,1).

%Ej 15 cuadradoSemiLatino(+N, -XS).

%cuadradoSemiLatino(N, XS) :- desde(0, S), generarMatriz(XS, S, N), semiLatino(XS, N).

%generarMatriz(-XS, +S, +N) generarMatriz(XS, S, N) :- generarMatrizAux(XS, S, N, N).

generarMatrizAux([], _, _, 0). generarMatrizAux(XS, S, N, F) :- F>0, generarLista(S, N, L), Fm1 is F-1, generarMatrizAux(R, S, N, Fm1), append([L], R, XS).

%generarLista(+SUMA, +CANT, -L). generarLista(0,0, []). generarLista(N,M,L) :- M>0, between(0,N,X), NmX is N-X, Mm1 is M-1, generarLista(NmX, Mm1, A), append([X],A,L).

%Dada la representacion de arboles binarios del ejercicio 12, definir el predicado subABB(+AB,-Subarbol), que %tenga ́exito si Subarbol es un subarbol de AB (puede ser un hijo o un descendiente cualquiera), %que ademas es un arbol binario de busqueda.

%subArbol(+AB, ?SA) subArbol(bin(I,_,_), I). subArbol(bin(_,_,D), D). subArbol(bin(I,_,_), T) :- subArbol(I, T). subArbol(bin(_,_,D), T) :- subArbol(D, T).

subABB(AB, S) :- subArbol(AB, S), aBB(S).

%ej17 %i. esTriangulo(+T) que, dada una estructura de la forma tri(A,B,C), indique si es un tri ́angulo valido. %En un triangulo valido, cada lado es menor que la suma de los otros dos, y mayor que su diferencia (y %obviamente mayor que 0).

tri(_,_,_).

%esTriangulo(+T)

esTriangulo(tri(A,B,C)) :- esCompatible(A,B,C), esCompatible(B,A,C), esCompatible(C,A,B).

%verifica que A cumpla la condicion en relacion a B y C %esCompatible(?A,+B,+C) esCompatible(A,B,C) :- D is B+C-1, E is B-C+1, abs(D,F), abs(E,G), between(G,F,A).

%perimetro(?T,?P) perimetro(T, P) :- generarTrianguloPerimetro(T,P), calcularPerimetro(T,P).

calcularPerimetro(tri(A,B,C), P) :- P is A+B+C.

generarTrianguloPerimetro(T,P) :- desde(3, P), generarTernasMenoresAP(A,B,C,P), T = tri(A,B,C), esTriangulo(T).

generarTernasMenoresAP(A,B,C,P) :- Q is P-1, between(1, Q, B), between(1, Q, C), A is P-B-C.

%triangulo(-T), que genera todos los tri ́angulos v ́alidos, sin repetir resultados. triangulo(T) :- desde(3,P), perimetro(T,P).

%Ejercicio 18 %Definir el predicado diferenciaSimetrica(+Lista1, +Lista2, -Lista3), que tenga ́exito si Lista3 es la lista %de todos los elementos que, o bien estan en Lista1 pero no en Lista2, o bien est ́an en Lista2 pero no en %Lista1. Asumir que las listas no tienen elementos repetidos.

%X in L3 sii (X in L1, not X in L2; not X in L1, X in L2)

diferenciaSimetrica([], L2, L2). diferenciaSimetrica([X|XS], L2, L3) :- \+ member(X,L2), borrar(XS, X, Z), diferenciaSimetrica(Z,L2,L), append([X], L, L3). diferenciaSimetrica([X|XS], L2, L3) :- member(X,L2), borrar(XS, X, Z), borrar(L2,X,Y), diferenciaSimetrica(Z,Y,L3).

%22 %i. Implementar un predicado arbol(-A) que genere estructuras de arbol binario, dejando los valores de los nodos sin instan- %ciar. Deben devolverse todos los arboles posibles (es decir, para toda estructura posible, %el predicado debe devolverla luego de un numero finito de pedidos). No debe devolverse dos veces elmismo arbol

arbol(A) :- desde(0, H), dameArbol(H, A).

dameArbol(0, nil). dameArbol(H, bin(I, _, D)) :- H > 0, Hm1 is H-1, dame(P,Q,Hm1), dameArbol(P, I), dameArbol(Q, D).

%dame(?P,?Q,+V) dame(0,0,0). dame(P,Q,V) :- V > 0, P = V, between(0, V, Q). dame(P,Q,V) :- V > 0, Q = V, D is V-1, between(0, D, P).

%ii. Implementar un predicado nodosEn(?A, +L) que es verdaderocuando A es un arbol cuyos %nodos pertenecen al conjunto conjunto de atomos L (representado mediante una lista no vac ́ıa, sin orden %relevante y sin repetidos). Puede asumirse que el ́arbol se recibe instanciado en %su estructura, pero no necesariamente en sus nodos

nodosEn(A, L) :- var(A), arbol(A), instanciarNodos(A, L). nodosEn(A, L) :- nonvar(A), instanciarNodos(A, L).

instanciarNodos(nil, _). instanciarNodos(bin(I, V, D), L) :- member(E, L), V = E, instanciarNodos(I,L), instanciarNodos(D,L).

%iii. Implementar un predicado sinRepEn(-A, +L) que genere todos los arboles cuyos nodos %pertenezcan al alfabeto L y usando como m ́aximo una vez cada s ́ımbolo del mismo. %En este caso, no hay infinitos ́arboles posibles; es importante que el predicado no devuelva soluciones repeti- %das y que no se quede buscando indefinidamente una vez terminado el espacio de soluciones.

sinRepEn(A, L) :- var(A), arbolesPosibles(A, L), nodosEn(A,L), noTieneRepetidos(A). sinRepEn(A, L) :- nonvar(A), nodosEn(A,L), noTieneRepetidos(A).

arbolesPosibles(A,L) :- length(L, N), between(0, N, H), dameArbol(H, A).

noTieneRepetidos(A) :- inorder(A,L), sinRepe(L).

sinRepe([]). sinRepe([X|XS]) :- \+ member(X, XS), sinRepe(XS).

testSinRepeArbol(Simb, P, Q) :- findall(A, sinRepEn(A, Simb), L), interseccion(L,L,X), length(L, P), length(X, Q).