2.2.1 Representando Sequências
Uma das estruturas de dados úteis que podemos construir com pares é uma sequência—uma coleção ordenada de objetos de dados. Existem, é claro, muitas maneiras de representar sequências em termos de pares. Uma representação particularmente direta é ilustrada abaixo, onde a sequência 1, 2, 3, 4 é representada como uma cadeia de pares:
O head de cada par é o item correspondente na cadeia, e o tail do par é o próximo par na cadeia. O tail do par final sinaliza o fim da sequência apontando para um valor distinto de qualquer par, que representamos na diagrama de box-and-pointer como um símbolo diagonal e em programas como o valor de null. A sequência inteira é construída por operações pair aninhadas:
Carregando playground de código...
Tal sequência de pares é chamada de lista, e JavaScript fornece uma função primitiva chamada list para ajudar a construir listas. A definição acima é equivalente a:
Carregando playground de código...
Podemos pensar em head como selecionando o primeiro item na lista, e tail como selecionando a sublista consistindo de todos, exceto o primeiro item.
Carregando playground de código...
Carregando playground de código...
Operações de Lista
O uso de pares para representar sequências de elementos como listas é acompanhado por técnicas convencionais de programação para manipular listas através de operações sucessivas de head e tail. Por exemplo, a função list_ref pega como argumentos uma lista e um número n e retorna o n-ésimo item da lista (convenção: o primeiro item é o item zero):
Carregando playground de código...
Frequentemente usamos head e tail de forma caminhando pela lista inteira. Por exemplo, a função length, que retorna o número de itens em uma lista, pode ser implementada recursivamente:
Carregando playground de código...
A função append recebe duas listas como argumentos e combina seus elementos para fazer uma nova lista:
Carregando playground de código...
Mapeamento sobre Listas
Uma operação extremamente útil é aplicar alguma transformação a cada elemento em uma lista e gerar a lista de resultados. Por exemplo, a seguinte função escala cada número em uma lista por um dado fator:
Carregando playground de código...
Podemos abstrair este padrão geral e capturá-lo como um padrão comum expresso como uma função de ordem superior, assim como na seção 1.3. A função de ordem superior aqui é chamada map:
Carregando playground de código...
A função map é uma abstração importante porque estabelece uma barreira de abstração de nível superior na programação de listas. Usar map nos ajuda a separar a transformação dos elementos da mecânica de percorrer a estrutura de dados.
Exercícios
Exercício 2.17: Defina uma função last_pair que retorna a lista que contém apenas o último elemento de uma dada lista (não vazia).
Exercício 2.18: Defina uma função reverse que recebe uma lista como argumento e retorna uma lista dos mesmos elementos em ordem inversa.
Exercício 2.19: No programa de contagem de moedas da seção 1.2.2, modifique o programa para que a lista de tipos de moedas seja uma lista. Defina as funções first_denomination, except_first_denomination e no_more.
Exercício 2.21: Complete as duas definições diferentes de square_list, uma usando recursão direta e outra usando map.
Exercício 2.22: Louis Reasoner tenta reescrever a primeira função square_list como um processo iterativo, mas ela produz a lista de resposta em ordem reversa. Explique por que.
Exercício 2.23: A função for_each é similar a map, mas não retorna uma lista de resultados. Em vez disso, ela apenas aplica a função a cada elemento por seus efeitos colaterais. Implemente for_each.
Carregando playground de código...
📝 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! ✨