Prática (8) Prolog declarativo – recursividade em listas, aritmética,
computação simbólica, validação de dados
Exercícios de definição recursiva de predicados que processam listas
Usando um interpretador Prolog, define e experimenta os seguintes predicados:
a) inteiros/2, tal que inteiros(Lista, Inteiros) significa que Inteiros é a lista dos
elementos de Lista que são números inteiros. O predicado deve certificar-se
que Lista é uma lista, e que Inteiros é uma variável ou uma lista.
b) media/2, tal que media(Lista, Media) significa que Média é a média dos
valores da lista Lista. O predicado deve certificar-se que Lista seja uma lista e
que cada um dos seus elementos seja um valor numérico; e que Media seja
uma variável ou um número.
c) expansao/2 tal que expansão(L, E) significa que E é a expansão de L. Cada
elemento de L tem a forma de um par (N, X) em que N tem de ser um inteiro
não negativo. Na lista expandida, o par (N, X) da lista original é substituído
por N elementos X.
Exemplo
?- expansao([(3, a), (1, b), (6, c)], L).
L = [a, a, a, b, c, c, c, c, c, c]
d) Escreve o predicado max/2, tal que max(Lista, Max) significa que Max é o
maior elemento da lista Lista.
e) [Menos importante] Escreve uma nova versão do predicado para determinar o
maior elemento de uma lista. Agora, os elementos da lista são estruturas com a
forma t(X, Y, Z) (em que X, Y e Z são os argumentos numéricos da estrutura).
A selecção do maior elemento da lista é feita com base na comparação do
argumento nº N dos elementos da lista. Assim sendo, o predicado a criar tem
os seguintes argumentos: Lista de estruturas, número do argumento que serve
de termo de comparação, e maior elemento, o qual deve ser determinado pelo
predicado max/3.
Exemplos
?- max([t(1, 2, 3), t(3, 2, 1), t(1, 3, 2)], 2, Max).
Max = t(1, 3, 2)
?- max([t(1, 2, 3), t(3, 2, 1), t(1, 3, 2)], 1, Max).
Max = t(3, 2, 1)
?- max([t(1, 2, 3), t(3, 2, 1), t(1, 3, 2)], 3, Max).
Max = t(1, 2, 3)
O predicado arg/3 do Prolog permite aceder ao argumento nº N de uma
estrutura: arg(N, Estrutura, Arg)
f) Escreve o predicado insertion_sort/2, tal que insertion_sort(L1, L2) significa
que L2 é o resultado de ordenar a lista L1, por ordem crescente. O algoritmo
usado deve ser o insertion sort: para ordenar uma lista, basta inserir
ordenadamente o seu primeiro elemento no resultado de ordenar o resto da
lista. O resultado de ordenar uma lista vazia é uma lista vazia.
?- insertion_sort([3, 7, 1], L).
L = [1, 3, 7]