Linguagens e Ambientes de Programação (2016/2017)



Teórica 04 (16/mar/2017)

Tipos soma (uniões). Os tipos somas árvore binária e árvore n-ária.
Padrões. Padrões disjuntos. Emparelhamento de padrões.

Tipos soma (uniões)

Muitas linguagens de programação incluem uma construção específica para a definição de tipos cujos valores podem assumir diferentes variantes, disjuntas entre si. Essa construção designa-se genericamente por tipo soma.

Por exemplo, numa linguagem com suporte para tipos soma é possível definir um tipo de dados cshape, para representar formas geométricas coloridas cujos valores podem assumir as três seguintes variantes: Line, Circle e Rect.

Um tipo soma permite conciliar o geral com o particular. Por um lado os elementos das variantes Line, Circle e Rect são formas geométricas coloridas com algumas propriedades comuns: no mínimo todas têm um cor! Por outro lado são variantes, cada uma delas com dados específicos associados: um círculo tem um centro e um raio, uma linha tem dois pontos extremos, etc.

Os tipos soma do Pascal chamam-se registos com variante.
Os tipos soma do C são as uniões.
Os tipos soma do Java, Smalltalk e C++ são as classes abstratas (imagine uma classe abstrata cshape com três subclasses concretas Line, Circle e Rect). [Em rigor, as classes abstratas são um bocadinho diferentes dos tipos soma: os tipos soma são entidades fechadas enquanto que as classes abstratas são extensíveis.]

Como é em OCaml?

Tipos soma em OCaml

Para exemplificar, o tipo soma cshape atrás referido pode ser definido em OCaml da seguinte forma, usando os tipos auxiliares color e point: Repare que o nome dos tipos definidos pelo utilizador começa sempre por letra minúscula e o nome de cada variante começa sempre por letra maiúscula. Chamam-se etiquetas, aos nomes das variantes.

Continuando a usar o mesmo exemplo, vejamos agora quais são os mecanismos essenciais para escrever e manipular valores de tipos soma.

Literais: Eis dois literais de tipo cshape. Repare como o nome de cada variante é usado para marcar os respetivos literais.

Construção: Por exemplo, a seguinte função cria círculos centrados no ponto zero: Processamento: Eis uma função que calcula a área duma forma colorida. Os elementos de qualquer tipo soma são processados usando emparelhamento de padrões. Eis uma função que determina o raio duma forma. Só está definida para círculos.

Alguns tipos soma predefinidos em OCaml

  1. O tipo 'a list é um tipo soma. Internamente a sua definição assemelha-se a:

  2. O tipo bool também é um tipo soma, internamente é definido da seguinte forma: O OCaml abre uma exceção neste caso, e permite que o nome das variantes comece por letra minúscula.

  3. O tipo 'a option é um tipo soma que permite representar o conceito de ausência de valor, em situações que tal possa ser útil. Internamente, é definido assim:

Os três papéis das etiquetas dum tipo soma

As etiquetas dum tipo soma tem três papéis:

Árvores binárias

Em programação, as árvores binárias permitem exprimir informação hierarquizada e permitem organizar dados por forma a aumentar a velocidade de acesso a eles.

O tipo soma árvore binária não está predefinido em OCaml, mas é fácil de definir usando um tipo soma:

Literais: Eis uma constante do tipo int tree: Construção: Por exemplo, a seguinte função cria folhas da árvore: Processamento: Eis uma função que determina o número total de nós duma árvore binária:

Eis um exemplo de avaliação duma expressão envolvendo uma chamada da função "size":

Vocabulário relativo a árvores

Método indutivo aplicado a árvores binárias

No caso das árvores binárias, o método indutivo consiste na seguinte técnica:

Exemplo de utilização do método indutivo

Problema: Programar uma função "size" que determine o número total de nós duma árvore binária:

Resolução: A função "size" aplica-se a uma árvore, a qual será, naturalmente, processada usando emparelhamento de padrões. Aplicando o método indutivo ao caso geral "G=Node(x,l,r)", vamos começar por assumir que já temos o problema resolvido para os casos "L=size l" e "R=size r". Obtemos assim o seguinte PONTO DE PARTIDA PARA COMEÇAR A RACIOCINAR:

O problema que temos para resolver é o seguinte: Como é que se obtém o valor de "G=size (Node(x,l,r))" a partir dos valores "L=size l" e "R=size r"? Mas este problema é simples. De facto, basta adicionar uma unidade a L+R para se obter G!

Preenchendo o que falta no esquema anterior, surge a solução final:

Mais duas funções sobre árvores binárias

Altura duma árvore:

Árvore ao espelho:



Árvores n-árias

Numa árvore n-ária, cada nó pode ter um número qualquer (ilimitado) de filhos.

O tipo soma árvore n-ária pode definir-se assim em OCaml:

Repare que enquanto numa folha duma árvore binária se usam dois Nil para indicar que não há filhos, numa folha duma árvore n-ária usa-se uma lista vazia para indicar a mesma coisa.

Literais: Eis uma constante de tipo "int ntree":

Construção: Por exemplo, a seguinte função cria folhas:

Processamento: A função size determina o número de nós duma árvore n-ária. Note que se usa uma função auxiliar que processa uma lista de árvores.

Esquema geral da utilização do método indutivo no tratamento de árvores n-árias:

Árvore ao espelho:

Invariante: A representação das árvores n-árias é ambígua pois a mesma árvore pode ser apresentada de várias formas. Isto acontece porque ocorrências de NNil numa lista de filhos não acrescentam nada de útil. Por exemplo, as seguintes árvores n-árias são equivalentes e representam sempre a mesma folha:

Para evitar esta ambiguidade, vamos introduzir o seguinte invariante:

Para ajudar a cumprir o invariante, introduzimos a função auxiliar ncons. A função acrescenta uma árvore n-ária à cabeça duma lista de árvores n-árias apenas se a árvore não for vazia:

Um exemplo que usa ncons: Eliminar duma árvore t, todas as subárvores com um dado valor v na raiz:



Padrões

Um padrão é uma expressão especial que representa um conjunto de valores. A sintaxe dum padrão fornece geralmente uma boa intuição sobre a estrutura dos valores em causa.

A utilização de padrões torna as funções mais fáceis de escrever e de entender. Os padrões são, portanto, bons amigos do/a programador/a. As linguagens funcionais antigas (e.g. Lisp) não usavam padrões, mas as linguagens funcionais modernas (e.g. OCaml, Haskell) não os dispensam.

Exemplos de padrões:

Numa expressão match podem ocorrer padrões em número variável. Durante a avaliação, esses padrões são explorados sequencialmente, de cima para baixo.

Por exemplo, o que faz a seguinte função?

E o que faz esta outra função?

Onde podem ocorrer os padrões?

Na sintaxe do OCaml, está previsto que os padrões ocorrem nos seguintes contextos:

Atenção ao contexto!

Padrões disjuntos

Dois padrões dizem-se disjuntos se os conjuntos que eles representam são disjuntos. Numa expressão match, a ordem dos casos só é irrelevante se os padrões forem disjuntos entre si.

Exemplos:

Emparelhamento

Como resultado do emparelhamento dum valor com um padrão, há duas consequências possíveis:
  1. Falhanço;
  2. Sucesso, e os nomes que ocorrem no padrão ficam ligados a valores.

Restrições

A seguinte função aplica-se a uma lista de pares ordenados, e conta o número de pares com as duas componentes iguais:

A seguinte função aplica-se a uma lista de pares ordenados, e conta o número de pares em que a segunda componente é igual a um valor dado:



#140