Exercício do Exame de Recorrência de 1998: Problema

Sobre operações com Listas em Prolog, responda às alíneas seguintes:

a)

Nas aulas teórico-práticas, a quando da implementação do ficheiro math.pl, implementou-se o predicado inverte/2 da maneira que se segue:

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

         inverte([],[]).
         inverte([X|L],I) :-
           inverte(L,LI),
           concatena(LI,[X],I).

O predicado inverte devolve-nos, no segundo argumento, a lista invertida que é fornecida como primeiro parâmetro. Assim, por exemplo,

         ?- inverte([1,2,3],L).
            L = [3,2,1]

         ?- inverte([1,[2,3],4],L).
            L = [4,[2,3],1]

Pretende-se que implemente agora um predicado inverte_tudo que faz a inversão a todos os níveis (caso a lista contenha listas de entre os seus elementos, essas listas também são invertidas). Assim, para os exemplos atrás considerados, teríamos:

         ?- inverte_tudo([1,2,3],L).
            L = [3,2,1]

         ?- inverte_tudo([1,[2,3],4],L).
            L = [4,[3,2],1]

b)

Ainda em relação ao predicado concatena/3 da alínea anterior, mostre, usando a Árvore de Prova que o átomo

         concatena([a,b], [c], [a,b,c]).

é verdadeiro.

c)

Ainda em relação ao predicado inverte/2 da alínea anterior, mostre, usando a Árvore de Procura que a resposta do interpretador de Prolog à questão

         inverte([a,b,c], [c,a,b]).

é ``no''.

d)

Pretende-se que implemente agora um predicado denominado merge, que serve para fundir duas listas ordenadas produzindo uma terceira lista, também ela ordenada.
Exemplo:

         ?- merge([2,5,6,6,8],[1,3,5,9],L).
            L = [1,2,3,5,5,6,6,8,9]

Pressuponha a existência de um predicado antes(X,Y) que resulta verdadeiro quando X vem antes de Y. Para o exemplo apresentado, pode pensar nos termos da seguinte definição:

         antes(X,Y) :- X =< Y.