Práctica de Prolog: Listas (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

% Ejercicio 4
% Definir los siguientes predicados:

% i. last(-L, -U), donde U es el ´ultimo elemento de la lista L. Definirlo en forma recursiva, y usando
% el predicado append definido de la siguiente manera:
% append([], X, X).
% append( [H | T], Y, [H | Z]) :- append(T, Y, Z).

last(L, U) :- append(_, [U], L).

% ii. reverse(+L, -L1), donde L1 contiene los mismos elementos que L, pero en orden inverso.
% Ejemplo: reverse([a,b,c], [c,b,a]).
% Realizar una definici´on usando append, y otra sin usarlo. Mostrar el ´arbol de prueba para el
% ejemplo dado.

% reverse([], []).
% reverse([H | T], [ReversedT | [H]]) :- reverse(T, ReversedT).
% reverse: como se hace reverse sin append?

reverse2([], []).
reverse2([H | T], R) :- reverse2(T, ReversedT), append(ReversedT, [H], R).

% iii. maxlista(+L, -M) y minlista(+L, -M), donde M es el m´aximo/m´inimo de la lista L.
maxlista([H], H).
maxlista([H | T], H) :- maxlista(T, M), H >= M.
maxlista([H | T], M) :- maxlista(T, M), H < M.

minlista([H], H).
minlista([H | T], H) :- minlista(T, M), H =< M.
minlista([H | T], M) :- minlista(T, M), H > M.

% iv. palindromo(+L, -L1), donde L1 es un pal´indromo construido a partir de L.
% Ejemplo: palindromo([a,b,c], [a,b,c,c,b,a]).
palindromo(L, P) :- reverse2(L, RevL), append(L, RevL, P).

% v. doble(-L, -L1), donde cada elemento de L aparece dos veces en L1.
% Ejemplo: doble([a,b,c], [a,a,b,b,c,c]).
doble([], []).
doble([H | T], [H | H | DT]) :- doble(T, DT).

% vi. prefijo(-P, +L), donde P es prefijo de la lista L.
prefijo(P, L) :- append(P, _, L).

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

% viii. sublista(-S, +L), donde S es sublista de L.
% Esta version es para sublistas "continuas" en L.
sublista([], _).
sublista(S, L) :- append(CasiL, _, L), append(_, S, CasiL), S \= [].

% Esta version es para sublistas "no continuas" en L.

sublistaB([], []).
sublistaB([H | SubsT], [H | T]) :- sublistaB(SubsT, T).
sublistaB(SubsT, [_ | T]) :- sublistaB(SubsT, T).

% ix. iesimo(-I, +L, -X), donde X es el I-´esimo elemento de la lista L.
% Ejemplo: iesimo(2, [10, 20, 30, 40], 20).
iesimo(I, L, X) :- append(ListI, [X | _], L), length(ListI, I).

% Definir los siguientes predicados:
% i. mezcla(L1, L2, L3), donde L3 es el resultado de mezclar uno a uno los elementos de las listas
% L1 y L2. Si una lista tiene longitud menor, entonces el resto de la lista m´as larga es pasado
% sin cambiar. Verificar la reversibilidad, es decir si es posible obtener L3 a partir de L1 y L2, y
% viceversa.
% Ejemplo: mezcla([a,b,c], [d,e], [a,d,b,e,c]).
mezcla(L1, [], L1).
mezcla([], L2, L2).
mezcla([H1 | T1], [H2 | T2], [H1, H2 | T12]) :- mezcla(T1, T2, T12).

% 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. ¿Cu´an reversible es este predicado? Es decir,
% ¿qu´e elementos pueden estar indefinidos al momento de la invocaci´on?
split(N, L, L1, L2) :- append(L1, L2, L), length(L1, N).

% iii. borrar(+ListaConXs, +X, -ListaSinXs), que elimina todas las ocurrencias de X de la lista
% ListaConXs.
borrar([], _, []).
borrar([H | XS], E, [H | YS]) :- E \= H, borrar(XS, E, YS).
borrar([E | XS], E, YS) :- borrar(XS, E, YS).

% iv. sacarDuplicados(+L1, -L2), que saca todos los elementos duplicados de la lista L1.
pertenece(E, L1) :- append(Principio, _, L1), append(_, [E], Principio).
sacarDuplicados([], []).
sacarDuplicados([H | T], [H | SinDups]) :- borrar(T, H, BorrarH), sacarDuplicados(BorrarH, SinDups).
sacarDuplicados([H | T], SinDups) :- pertenece(H, T), sacarDuplicados(T, SinDups).

%Ejecicio 7
%Definir el predicado aplanar(+Xs, -Ys), que es verdadero sii Ys contiene los elementos contenidos
%en alg´un nivel de Xs, en el mismo orden de aparici´on. 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.
%Ejemplos:
%?- aplanar([a, [3, b, []], [2]], [a, 3, b, 2]).
%?- aplanar([[1, [2, 3], [a]], [[[]]]], [1, 2, 3, a]).
aplanar([], []).
aplanar([H | T], App) :- is_list(H), aplanar(H, AppH), aplanar(T, AppT), append(AppH, AppT, App).
aplanar([H | T], App) :- not(is_list(H)), aplanar(T, AppT), append([H], AppT, App).

%Ejecicio 8
%Definir los siguientes predicados:
%i. ordenada(+L), que ser´a cierta si los elementos de L est´an ordenados en forma ascendente.
ordenada([]).
ordenada([_]).
ordenada([X, Y | XS]) :- X =< Y, ordenada([Y | XS]).

%ii. quicksort(+L, -L1), donde L1 es el resultado de ordenar L por el m´etodo de quicksort, que
%consiste en dividir a L en 2 sublistas con los menores y mayores al primer elemento, ordenar cada
%una de ellas y luego proceder a concatenarlas.
quicksort_partir([], _, [], []).
quicksort_partir([H | T], E, [H | Menores], Mayores) :- (H =< E), quicksort_partir(T, E, Menores, Mayores).
quicksort_partir([H | T], E, Menores, [H | Mayores]) :- H > E, quicksort_partir(T, E, Menores, Mayores).

quicksort([], []).
quicksort([H | T], S) :- quicksort_partir(T, H, Menores, Mayores), quicksort(Menores, MenOrd),
quicksort(Mayores, MayOrd), append(MenOrd, [H | MayOrd], S).

%iii. inssort(+L, -L1), donde L1 es el resultado de ordenar L por el m´etodo de inserci´on, que
%consiste en insertar cada elemento en el lugar adecuado del resto de la lista ya ordenada.
insertar_ordenado([], E, [E]).
insertar_ordenado([H | T], E, [E, H | T]) :- E =< H.
insertar_ordenado([H | T], E, [H | S]) :- E > H, insertar_ordenado(T, E, S).

inssort([], []).
inssort([H | T], S) :- inssort(T, SortT), insertar_ordenado(SortT, H, S).

% Ejercicio 9
% Definir un predicado rotar(+L, +N, -R), tal que R sea la lista L rotada N posiciones (la rotaci´on se
% debe hacer hacia la derecha si N>0 y hacia la izquierda si N<0).
% Ejemplos:
% rotar([1, a, 2, b, 3], 3, X) debe dar como respuesta X = [2, b, 3, 1, a]
% rotar([1, a, 2, b, 3], -3, X) debe dar como respuesta X = [b, 3, 1, a, 2]

modulus(N, Modulus, Result) :- Result is ((N mod Modulus) + Modulus) mod Modulus.

rotar(L, N, R) :- length(L, Length), modulus(N, Length, Rotate), append(Init, Tail, L),
length(Tail, Rotate), append(Tail, Init, R).

% Ejercicio 10
% Definir un predicado que reciba una lista de n´umeros naturales y devuelva otra lista de n´umeros
% naturales, en la que cada n´umero n de la primera lista aparezca repetido n veces en forma consecutiva,
% respetando su orden de aparici´on. Considerar que la lista original siempre est´a instanciada.
% Ejemplo: para la lista [2, 3, 1, 0, 2] la salida es [2, 2, 3, 3, 3, 1, 2, 2].
repetir_n(_, 0, []).
repetir_n(E, Times, [E | T]) :- Times > 0, TimesMenos1 is Times - 1, repetir_n(E, TimesMenos1, T).

repetir_numeros([], []).
repetir_numeros([H | T], Reps) :- repetir_n(H, H, Hs), repetir_numeros(T, Ts), append(Hs, Ts, Reps).

% Ejercicio 11
% Escribir en Prolog un predicado que devuelva la mediana de una lista (la mediana es el elemento que
% se halla en la posici´on del medio de dicha lista, tras ser ordenada). Utilizar los predicados definidos
% anteriormente. Considerar que la lista siempre est´a instanciada.
mediana(L, M) :- quicksort(L, S), length(L, Length), Mitad is Length // 2,
append(Primeros, [M | _], S), length(Primeros, Mitad).

% Ejercicio 12
% Escribir en Prolog los siguientes predicados:

% interseccion(+X, +Y, -Z), tal que Z es la intersecci´on sin repeticiones de las listas X e Y,
% % respetando en Z el orden en que aparecen los elementos en X.
interseccion_con_duplicados([], _, []).
interseccion_con_duplicados([H | T], Y, [H | IntTY]) :- pertenece(H, Y), interseccion_con_duplicados(T, Y, IntTY).
interseccion_con_duplicados([H | T], Y, IntTY) :- not(pertenece(H, Y)), interseccion_con_duplicados(T, Y, IntTY).

interseccion(X, Y, Z) :- interseccion_con_duplicados(X, Y, W), sacarDuplicados(W, Z).