2.2 Dados Hierárquicos e a Propriedade de Closure

Como vimos, os pares fornecem uma "cola" primitiva que podemos usar para construir objetos de dados compostos. A figura abaixo mostra uma maneira padrão de visualizar um par—neste caso, o par formado por pair(1, 2). Nesta representação, que é chamada de notação box-and-pointer, cada objeto composto é mostrado como um ponteiro para uma caixa. A caixa para um par tem duas partes, a parte esquerda contendo o head do par e a parte direita contendo o tail.

Já vimos que pair pode ser usado para combinar não apenas números, mas pares também. (Você fez uso desse fato, ou deveria ter feito, ao fazer os exercícios 2.2 e 2.3.) Como consequência, os pares fornecem um bloco de construção universal a partir do qual podemos construir todos os tipos de estruturas de dados. A figura abaixo mostra duas maneiras de usar pares para combinar os números 1, 2, 3 e 4.

A capacidade de criar pares cujos elementos são pares é a essência da importância da estrutura de lista como uma ferramenta representacional. Nos referimos a essa capacidade como a propriedade de closure de pair. Em geral, uma operação para combinar objetos de dados satisfaz a propriedade de closure se os resultados de combinar coisas com essa operação podem ser combinados usando a mesma operação. Closure é a chave para o poder em qualquer meio de combinação porque nos permite criar estruturas hierárquicas—estruturas compostas de partes, que são elas mesmas compostas de partes, e assim por diante.

Desde o início do capítulo 1, fizemos uso essencial de closure ao lidar com funções, porque todos, exceto os programas mais simples, dependem do fato de que os elementos de uma combinação podem ser eles mesmos combinações. Nesta seção, abordamos as consequências de closure para dados compostos. Descrevemos algumas técnicas convencionais para usar pares para representar sequências e árvores, e exibimos uma linguagem gráfica que ilustra closure de uma maneira vívida.