2.2.2 Estruturas Hierárquicas
A representação de sequências em termos de listas generaliza-se naturalmente para representar sequências cujos elementos podem ser eles mesmos sequências. Por exemplo, podemos considerar o objeto construído por:
Carregando playground de código...
como uma lista de três itens, o primeiro dos quais é ele mesmo uma lista. De fato, esta é a essência das estruturas hierárquicas—estruturas feitas de partes, que são elas mesmas feitas de partes, e assim por diante.
Outra maneira de pensar sobre sequências cujos elementos são sequências é como árvores. Os elementos da sequência são os ramos da árvore, e elementos que são eles mesmos sequências são subárvores.
Contando Folhas
A recursão é uma ferramenta natural para lidar com estruturas de árvore, já que podemos frequentemente reduzir operações em árvores a operações em seus ramos. Como um exemplo, considere a operação de contar as folhas de uma árvore:
Carregando playground de código...
Mapeamento sobre Árvores
Assim como map é uma abstração poderosa para lidar com sequências, tree_map é uma abstração poderosa para lidar com árvores:
Carregando playground de código...
Podemos abstrair isso usando map junto com recursão:
Carregando playground de código...
Exercícios
Exercício 2.24: Suponha que avaliamos a expressão list(1, list(2, list(3, 4))). Desenhe a representação box-and-pointer e a interpretação como árvore.
Exercício 2.25: Dê combinações de head e tail que selecionam 7 de cada uma das seguintes listas: list(1, 3, list(5, 7), 9), list(list(7)), e list(1, list(2, list(3, list(4, list(5, list(6, 7)))))).
Exercício 2.26: Suponha que definimos x e y como listas. Qual é o resultado de pair(x, y), list(x, y) e append(x, y)?
Exercício 2.27: Modifique sua função reverse do exercício 2.18 para produzir uma função deep_reverse que inverte todos os níveis de uma estrutura de árvore aninhada.
Exercício 2.28: Escreva uma função fringe que recebe uma árvore como argumento e retorna uma lista cujos elementos são todas as folhas da árvore organizadas da esquerda para a direita.
Exercício 2.29: Implemente um sistema de mobile binário (estrutura de equilíbrio) usando listas. Defina construtores e seletores, e funções para calcular peso total e verificar se o mobile está equilibrado.
Exercício 2.30: Defina uma função square_tree análoga à função square_list da seção anterior.
Exercício 2.31: Abstraia sua resposta ao exercício 2.30 para produzir uma função tree_map com a propriedade de que square_tree poderia ser definida como: function square_tree(tree) { return tree_map(square, tree); }.
Exercício 2.32: Complete a definição da função que gera o conjunto de subconjuntos de um conjunto.
📝 Encontrou algo errado nesta página?
Sua ajuda é muito importante para melhorar a qualidade da tradução!
🐛 Encontrou um erro?
Se você encontrou:
- Erro de tradução (palavra incorreta, termo técnico errado)
- Erro de ortografia ou gramática
- Link quebrado
- Código de exemplo que não funciona
- Problema de formatação
❓ Tem uma dúvida?
Se você tem:
- Dúvida sobre o conteúdo desta seção
- Pergunta sobre um conceito do SICP
- Dificuldade em entender algum exemplo
- Questão sobre a tradução de algum termo
💡 Tem uma sugestão de melhoria?
Se você quer sugerir:
- Melhoria na explicação
- Exemplo adicional
- Recurso visual (diagrama, ilustração)
- Qualquer outra ideia
🌍 Quer discutir a tradução?
Se você quer debater:
- Escolha de tradução de algum termo
- Consistência de terminologia
- Nuances do português
Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨