Considere a função p a seguir, em que L é uma lista.
B. Se L=x, um único elemento, então p(L)=" x ".
R. Se L=L^prime, x para alguma lista L^prime, então p(L)= " x, p(L^prime) ".
(a) Se L= john, paul, george, ringo, o que é p(L) ?
(b) O que a função p faz, em geral?
(c) Demonstre a sua afirmação da parte (b), usando indução.

Passo 1

O enunciado define uma função recursiva p que recebe uma lista L e devolve uma cadeia de caracteres construindo pares aninhados:
  • Caso base (B): se L = x (lista com um único elemento), então
p(L) = ";x;"
  • Regra recursiva ®: se L = L',x para alguma lista L' e elemento x, então
p(L) = "(,x,,p(L'),)"
O conteúdo envolvido é recursão em listas e, para a parte (c), prova por indução estrutural em listas.

Passo 2

(a) Seja L = [john,;paul,;>=or>=,;ringo].
Aplicando ® com L'=[john,paul,>=or>=] e x=ringo,
p(L) = "(,ringo,,p([john,paul,>=or>=]),)"
Sobre p([john,paul,>=or>=]) aplicamos ® de novo até chegar ao caso base:
p([john,paul,>=or>=]) = "(,>=or>=,,p([john,paul]),)" = "(,>=or>=,,(,paul,,p([john]),),)"
E p([john]) pelo caso base é " john ". Substituindo tudo,
p(L) = "(,ringo,,(,>=or>=,,(,paul,,john,),),)"

Passo 3

(b) Em geral, p recebe uma lista
L = [x1, x2, dots, xn]
e devolve uma representação de pares aninhados que é exatamente a lista invertida em forma de tuplas à direita, ou seja,
p(L) = (;xn,;(xn-1,;(dots,(x2,x1)dots));)
Em outras palavras, p faz um fold à direita que inverte a lista e agrupa os elementos em pares.

Passo 4

(c) Prova por indução no tamanho de L.
Base ( n=1). Se L=[x1], então pelo caso base
p(L)=";x1;",
que coincide com a afirmação de que
(x1)
é a lista invertida de um único elemento.
Passo indutivo. Suponha que para toda lista de tamanho n=k,
L'=[x1,dots,xk] Longrightarrow p(L')=(xk,(xk-1,dots,(x2,x1)dots))
Considere agora uma lista de tamanho k+1,
L=[x1,dots,xk,xk+1]
Pela regra ®,
p(L) = (,xk+1,,p([x1,dots,xk]),)
Pelo passo indutivo conhecemos p([x1,dots,xk]), logo
p(L) = (,xk+1,,(xk,(xk-1,dots,(x2,x1)dots)),),
que é exatamente a lista invertida em pares aninhados. Isso fecha a indução.

Resposta

(a) p([john,paul,>=or>=,ringo]) = "(,ringo,,(,>=or>=,,(,paul,,john,),),)".
(b) A função p inverte a lista e representa o resultado como pares aninhados à direita:
[x1,dots,xn];mapsto;(xn,,(xn-1,;( dots,(x2,x1)dots)))
(c) Demonstrado por indução no tamanho da lista.

Exercícios de Livros Relacionados