Novos operadores de tipos
Tipos que são por natureza paramétricos como as listas e as
matrizes, podem também ser definidos em ML.
O tipo lista (list) está predefinido por questões de eficiência, mas
se assim não fosse poderia ser definido pelo mecanismo de
definição de tipos do ML.
Uma extensão natural da definição datatype inclui a definição de
operadores de tipos. Para tal basta encarar a palavra datatype
como uma definição funcional (parametrizada) em vez de como
uma definição de valor (constante).
Em vez de definirmos um só tipo iremos definir um operador que
dado um tipo dá como resultado um novo tipo.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
94
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Novos operadores de tipos
Por exemplo, suponhamos que se pretende generalizar o seguinte
tipo básico, que define uma matriz de inteiros:
datatype int_matriz = Matriz of (int list list)
Pretende-se definir matrizes cujos elementos sejam de outro tipo
qualquer, mas sem ter que definir cada um dos tipos
separadamente, ou seja, usando uma construtora polimórfica.
Através da parametrização da definição acima,
introduzir um operador de tipos em vez de um tipo fixo:
podemos
datatype  matriz = Matriz of ( list list)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
95
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Novos operadores de tipos
Agora, para qualquer tipo T, teremos também o tipo T matriz e a
construtora é polimórfica sendo o seu tipo:
Matriz: ( list list)   matriz
Por exemplo poderemos ter:
Matriz [[1, 2], [3, 4], [5, 6]] : int matriz
Matriz [[Matriz [[true, false], [false, false]]]] : (bool matriz) matriz
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
96
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Novos operadores de tipos
Com esta facilidade para definir operadores de tipos, não será
necessário tratar as listas como um tipo especial pré-definido.
Podemos simplesmente definir:
datatype  list = :: of ( x  list)
|[]
que introduz as construtoras polimórficas
:: : ( x  list)   list
[ ]:  list
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
97
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Novos operadores de tipos
Esta capacidade do ML mostra o real poder do mecanismo de
definição de tipos.
Todos os tipos e operadores de tipos (excepto  e x) podem ser
introduzidos pelo programador.
Os tipos pré-definidos são incluídos apenas por uma questão de
eficiência. Em particular, os tipos pré-definidos int e string
poderiam ser modelados como novos tipos, no entanto isso não
seria muito conveniente.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
98
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores
Árvores aparecem com frequência nas ciências da computação e
existem diversas maneiras de as descrever.
Vamos falar das árvores, mais concretamente em algumas das
suas diversas variações: árvores binárias que só têm valores nas
folhas e árvores binárias com valores em todos os nós.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
99
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Estas árvores são chamadas binárias porque, a partir de cada nó,
existe um par de ramos que conduzem a outros dois nós.
Os nós que não têm ‘descendentes’ são chamados de folhas.
Vamos chamar ao tipo que define árvores binárias com valores
apenas nas folhas de bintree.
Mais precisamente, vamos chamar  bintree, a árvores cujos
valores que se encontram nas folhas sejam do tipo .
De forma a construirmos uma nova definição de tipo para estes
objectos, temos de considerar a forma como estes podem ser
construídos.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
100
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Pode existir um único nó, que nesse caso será considerado uma
folha e como tal (foi construído a partir de) contém um valor do
tipo .
No caso geral as árvores binárias serão compostas. Cada bintree
composta pode ser construída se juntarmos as duas bintrees mais
pequenas imediatamente abaixo do ponto de união, tal como
mostra a figura:
Lf(6)



6
9
3
6
6
9
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
101
3
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Isto sugere que apenas iremos necessitar de dois operadores
(construtoras do tipo) que vamos chamar de Lf e . O que é
pretendido para estas duas construtoras será:
Lf:    bintree
: ( bintree x  bintree)   bintree
em que a primeira serve para construir as folhas a partir do valor
recebido e a segunda para formar árvores binárias compostas a
partir de duas sub-árvores.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
102
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Assim, a definição para as construtoras polimórficas que
constroem o tipo recursivo bintree é a seguinte:
datatype  bintree = Lf of 
|  of ( bintree x  bintree)
infix 
Desta forma a definição da árvore apresentada no diagrama é:
val arv = Lf 6  (Lf 9  Lf 3)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
103
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Após a introdução deste novo operador de tipos, vamos definir
algumas operações sobre árvores binárias.
As mais imediatas serão left e rigth que seleccionam,
respectivamente, a sub-árvore da esquerda e da direita que se
encontra imediatamente abaixo. Estas operações não estão
definidas para árvores que sejam apenas uma folha.
fun left (t1  t2) = t1
| left (Lf a) = error “left de Lf não está definido”
fun right (t1 t2) = t2
| right (Lf a) = error “right de Lf não está definido”
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
104
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Temos também o predicado isleaf, que indica se uma dada árvore
é ou não uma folha e as funções leftmostleaf, que retorna o valor
da folha mais à esquerda da árvore e sumofleaves, que soma
todos os valores que estão nas folhas da árvore.
fun isleaf (t1  t2) = false
| isleaf (Lf v) = true
fun leftmostleaf (t1  t2) = leftmostleaf t1
| leftmostleaf (Lf v) = v
fun sumofleaves (t1  t2) = sumofleaves t1 + sumofleaves t2
| sumofleaves (Lf v) = v
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
105
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Existem ainda funções de ordem superior com árvores binárias,
analogamente às que existem para listas (map, accumulate, etc.).
Muitas operações sobre árvores binárias envolvem que se
perscrute a árvore, ao mesmo tempo que se aplica uma qualquer
função f aos valores das folhas. Deve existir ainda uma função
binária g que combina os valores retornados por cada incursão
nas sub-árvores esquerda e direita.
Assim define-se uma função de âmbito geral btreeop:
fun btreeop f g (Lf a) = f a
| btreeop f g (t1  t2) = g (btreeop f g t1) (btreeop f g t2)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
106
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Note-se que operações tais como leftmostleaf e sumofleaves
podem facilmente ser definidas à custa de btreeop:
val sumofleaves = btreeop id plus
À medida que a árvore é perscrutada, a função identidade é
aplicada aos valores encontrados nas folhas (retornando os
valores inalterados) e a função plus é aplicada aos resultados
retornados pela incursão nas sub-árvores esquerda e direita,
somando, assim, todos os valores das folhas.
Isto é análogo ao uso de reduce plus 0 para somar todos os
elementos de uma lista.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
107
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores binárias com valores nas folhas
Outra operação genérica sobre árvores binárias, btreemap, que
aplica uma função às folhas da àrvore (análoga ao map no caso
das listas) também pode ser definida como um caso especial de
btreeop:
fun join t1 t2 = t1  t2
fun btreemap f = btreeop (Lf ° f) join
A função join é apenas uma versão ‘curried’ do construtor .
O que está a ser feito é decompor a árvore, até chegar às folhas,
aplicar a função f aos valores das folhas e depois voltar a compor
a árvore, agora já com os valores modificados!
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
108
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores com valores em todos os nós
Vamos agora estudar as árvores binárias com valores também
nos nós internos, que a partir de agora chamaremos apenas de
árvores.
Uma definição de tipo para estes objectos será:
datatype  tree = Empty
| Tr of ( tree x  x  tree)
A primeira construtora é uma constante que representa o caso
especial da árvore sem nós.
A segunda construtora constrói uma árvore a partir de 2 subárvores e o nó que as une tem um valor do tipo .
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
109
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores com valores em todos os nós
Para estas árvores consideramos que estamos na presença de
uma folha quando ambas as suas sub-árvores têm o valor Empty.
Para poupar na escrita definimos uma função (que não é uma
construtora) que retorna uma folha:
leaf:    tree
fun leaf a = Tr(Empty, a, Empty)
A árvore
6
Departamento de Matemática e Engenharias
Elsa Carvalho
val t1 = Tr (leaf 6, 1, Tr (leaf 9, 2, leaf 3))
2
9
Universidade da Madeira
será representada por
1
3
110
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Árvores com valores em todos os nós
Também para estas árvores vamos definir algumas funções úteis.
Começamos por definir a operação análoga ao map (para listas) e
a btreemap (para árvores binárias), que será expressa da
seguinte forma:
fun treemap f Empty = Empty
| treemap f (Tr (t1, a, t2))
= Tr (treemap f t1, f a, treemap f t2)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
111
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)