Considere a função
a seguir, em que
é uma lista.
B. Se
, um único elemento, então
.
R. Se
para alguma lista
, então
"
".
(a) Se
john, paul, george, ringo, o que é
?
(b) O que a função
faz, em geral?
(c) Demonstre a sua afirmação da parte (b), usando indução.
B. Se
R. Se
(a) Se
(b) O que a função
(c) Demonstre a sua afirmação da parte (b), usando indução.
Passo 1
O enunciado define uma função recursiva
que recebe uma lista
e devolve uma cadeia de caracteres construindo pares aninhados:
- Caso base (B): se
(lista com um único elemento), então
- Regra recursiva ®: se
para alguma lista e elemento , então
O conteúdo envolvido é recursão em listas e, para a parte (c), prova por indução estrutural em listas.
Passo 2
(a) Seja
.
Aplicando ® com e
,
Aplicando ® com
Sobre
aplicamos ® de novo até chegar ao caso base:
E
pelo caso base é
. Substituindo tudo,
Passo 3
(b) Em geral,
recebe uma lista
e devolve uma representação de pares aninhados que é exatamente a lista invertida em forma de tuplas à direita, ou seja,
Em outras palavras,
faz um fold à direita que inverte a lista e agrupa os elementos em pares.
Passo 4
(c) Prova por indução no tamanho de
.
Base (
). Se
, então pelo caso base
que coincide com a afirmação de que
é a lista invertida de um único elemento.
Passo indutivo. Suponha que para toda lista de tamanho
,
Considere agora uma lista de tamanho
,
Pela regra ®,
Pelo passo indutivo conhecemos
, logo
que é exatamente a lista invertida em pares aninhados. Isso fecha a indução.
Resposta
(a)
.
(b) A função inverte a lista e representa o resultado como pares aninhados à direita:
(b) A função
(c) Demonstrado por indução no tamanho da lista.