Guião para a Quinta Aula Prática de IPL

Delfim F. Marado Torres

7 de Abril de 1999

Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.

1  Objectivos da aula

Manipulação de listas:

• Definição (recursiva) de lista (introduzida na aula teórica);
• Representação de listas em Prolog (introduzida na aula teórica);
• Consolidação do conceito de lista, à custa da resolução de vários exercícios: adiciona/3, tira/3, concatena/3, adiciona_fim/3, inverte/2. Faz-se notar a versatilidade dos predicados implementados, os quais podem ser usados com fins não pensados à priori (uso de várias configurações possíveis para inputs e outputs).

2  Alguns exercícios a resolver na aula

         concatena([],L,L).
         concatena([X|R],L,[X|C]) :-
           concatena(R,L,C).

         adiciona(X,L,[X|L]).

         tira(_,[],[]).
         tira(X,[X|R],R).
         tira(X,[Y|R],[Y|R1]) :-
           tira(X,R,R1).

         adiciona_fim(X,L,NL) :-
           concatena(L,[X],NL).

3  Mais Exercícios

Implemente os predicados tira_todos/3, pertence/2, ultimo/2, sublista/2, permutacao/2 e ordena/2 (fazer uma versão para ordenar uma lista de números por ordem crescente, e uma outra para ordenar por ordem decrescente).

         tira_todos(_,[],[]).
         tira_todos(X,[X|R],NR) :-
           tira_todos(X,R,NR).
         tira_todos(X,[Y|R],[Y|R1]) :-
           tira_todos(X,R,R1).

         pertence(X,[X|_]).
         pertence(X,[_|R]) :-
           pertence(X,R).

         ultimo([U],U).
         ultimo([_|R],U) :-
           ultimo(R,U).

         sublista(S,L) :-
           concatena(_,S,L1),
           concatena(L1,_,L).

         permutacao([],[]).
         permutacao(L,[X|P]) :-
           tira(X,L,L1),
           permutacao(L1,P).

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% Predicados de ordena,c~ao.
         %% Recebem sempre dois argumentos. Retornam
         %% ''yes'' se o primeiro e'
         %% ''menor'' que o segundo
         %% e ''no'' caso contra'ario.
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         antes_c(X,Y) :-  % serve para ordenar uma lista de nu'meros
           X =< Y.        % por ordem crescente

         antes_d(X,Y) :-  % serve para ordenar uma lista de nu'meros
           X >= Y.        % por ordem decrescente

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         ordenada(_,[]).
         ordenada(_,[_]).
         ordenada(P,[X,Y|R]) :-
           ordenada(P,[Y|R]),
           C =..[P,X,Y],
           call(C).

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% ORDENA usando um algoritmo do tipo Bubble Sort
         %%    bubble_sort/3
         %%    ordena_c/2
         %%    ordena_d/2
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         bubble(_,[X],[X]).
         bubble(P,[X,Y|R],[X|O]) :-
           C =.. [P,X,Y],
           call(C),
           bubble(P,[Y|R],O).
         bubble(P,[X,Y|R],[Y|O]) :-
           bubble(P,[X|R],O).

         bubble_sort(P,L,L) :-
           ordenada(P,L).
         bubble_sort(P,L,LO) :-
           bubble(P,L,L1),
           bubble_sort(P,L1,LO).

         ordena_c(L,LO) :-
           bubble_sort(antes_c,L,LO).
         ordena_d(L,LO) :-
           bubble_sort(antes_d,L,LO).