| Métodos de Programação I - 2000/01 |
|---|---|
| [ DI/UM ] |
| Aula Teórica de 26.09.00 [Ref:6]: |
Sumário: Apresentação da disciplina. Equipa docente.
Programa da disciplina e seu enquadramento no plano de estudos. Teoria e método em programação. Composicionalidade. Interfaces. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programação.
Regime de avaliação. Bibliografia. Informação electrónica sobre a disciplina: URL: http://www.di.uminho.pt/~jno/html/mpi.html.
| Aula Teórica de 28.09.00 [Ref:8]: |
Sumário: Introdução à Programação funcional. Conceito de função. A função como contrato. Diagramas de blocos. Domínio e codomínio de uma função. Diagramas funcionais. Setas f : A -> B.
Início do estudo dos combinadores elementares de programas funcionais: A composição f ·g como combinador elementar de funções. Associatividade da composição. Função identidade id.
Aula Teórica de 3.10.00 [Ref:6]:
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.): Polimorfismo da função identidade. A propriedade f ·id = id ·f = f e seu diagramas comutativo. Notação funcional com ou sem variáveis.
O combinador <f,g> e o produto A × B (analogia com «struct» em C) e suas projecções. Propriedade de cancelamento- × . O combinador [f,g] e o coproduto A + B (analogia com «union» em C) e suas injecções.
Aula Teórica de 10.10.00 [Ref:6]:
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.): Propriedades universais de <f,g> e de [f,g] e suas derivadas (cancelamento, reflexão e fusão).
| Aula Teórica de 12.10.00 [Ref:8]: |
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Os combinadores f × g e f + g . Propriedades de absorção. Propriedades functoriais.
Apresentação da extensão Mpi.hs ao Prelude.hs do Hugs 98.
Aula Teórica de 17.10.00 [Ref:6]:
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Lei da troca. Diagrama da lei da troca. Exemplo: undistr. Noção de isomorfismo entre tipos de dados.
| Aula Teórica de 19.10.00 [Ref:8]: |
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Invertibilidade à esquerda e à direita. Funções sobrejectivas (com inversa à direita) e funções injectivas (com inversa à esquerda). Funções bijectivas ou isomorfismos. O isomorfismo A × B =B × A (swap). Outros isomorfismos célebres envolvendo produtos e coprodutos (assocr etc).
Predicados e guardas. Condicional de McCarthy. Lei da fusão do condicional de McCarthy.
Aula Teórica de 24.10.00 [Ref:6]:
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Tipos elementares genéricos: 0 , 1 e 2 (resp. Void, () e Bool em HASKELL). Segmentos iniciais e tipos enumerados.
Funções constantes. O combinador c . Propriedades. Polimorfismo da função constante: c = c ·f.
| Aula Teórica de 26.10.00 [Ref:8]: |
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Funções de ordem superior. Noção de espaço funcional. O combinador curry f e o operador ap. A exponencial B^A e seus isomorfismos (eg. curry, split, either etc). As funções ! : A ->1 e ? : 0 ->A .
Propriedade universal de curry f e cancelamento da exponencial.
Aula Teórica de 31.10.00 [Ref:6]:
Sumário: Estudo dos combinadores elementares de programas funcionais (conclusão) : As propriedades de fusão e reflexão da exponencial como consequência da propriedade universal de curry f . A construção f^A e a propriedade de absorção.
Produtos e coprodutos n -ários ( n>=0 ).
Introdução aos tipos de dados recursivos a partir de uma analogia com a programação imperativa : O conceito de «apontador» 1 + A (Maybe a em HASKELL). Tipos de dados recursivos vistos como equações. As listas ligadas e a equação L =1 + A × L .
| Aula Teórica de 02.11.00 [Ref:8]: |
Sumário: Introdução aos tipos indutivos : Declaração de tipos de dados em HASKELL. Sua relação com o coproduto. Álgebra e co-álgebra do tipo indutivo definido pela equação L =1 + A × L . Isomorfismo. Introdução à observação de tipos indutivos usando como exemplo listas de inteiros: data L = Nil | Cons (Int,L) .
Aula Teórica de 7.11.00 [Ref:6]:
Sumário: Introdução aos tipos indutivos (cont.) : Conceitos de catamorfismo e anamorfismo usando o tipo de dados exemplo listas de inteiros: data L = Nil | Cons (Int,L) .
| Aula Teórica de 9.11.00 [Ref:8]: |
Sumário: Introdução aos tipos indutivos (cont.) : Conceito de hilomorfismo usando o tipo de dados exemplo listas de inteiros - data L = Nil | Cons (Int,L) . O factorial visto como um hilomorfismo.
Aula Teórica de 14.11.00 [Ref:6]:
Sumário: Introdução aos tipos indutivos (cont.) : Cálculo de programas: eliminação da estrutura de dados intermédia de um hilomorfismo.
| Aula Teórica de 16.11.00 [Ref:8]: |
Sumário: Introdução aos tipos indutivos (cont.) : Apresentação do módulo RList.hs: o algoritmo de ordenação por inserção simples como hilomorfismo sobre a estrutura RList a.
| Aula Teórica de 21.11.00 [Ref:6]: |
Sumário: Introdução aos tipos indutivos (cont.) : Introdução ao tipo de dados árvores binárias simples, ou listas bi-lineares: data BTree a = Empty | Node(a, (BTree a, BTree a)).
Apresentação do módulo BTree.hs. Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplo: o hilomorfismo qSort ('quick sort').
| Aula Teórica de 23.11.00 [Ref:8]: |
Sumário: Introdução aos tipos indutivos (cont.) : Introdução à parametrização e ao polimorfismo. Formulação de map (em [a]) e de map em RList como catamorfismos. Propriedades:
map id = id
map (f ·g) = (map f) ·(map g)
| Aula Teórica de 28.11.00 [Ref:6]: |
Sumário: Noção de functor. Propriedades functoriais. Functores em HASKELL: a class Functor e o operador fmap. Exemplos: functor indentidade, functor constante e a exponencial. Propriedades naturais. Noção de bi-functor. Propriedades. Bi-functores em HASKELL: a class BiFunctor e o operador bmap. Exemplos: functor produto e coproduto.
| Aula Teórica de 30.11.00 [Ref:8]: |
Sumário: Definição genérica de um tipo indutivo de dados. Parametrização. Noção de functor de base. maps são catamorfismos: Politipismo da definição t a =b(a,t a) de um tipo indutivo genérico paramétrico. Noção de functor de tipo e sua formulação genérica como o catamorfismo t f =cata in ·b(f,id).
Polimorfismo versus politipismo. Programação dita «genérica».
| Aula Teórica de 05.12.00 [Ref:6]: |
Sumário: Propriedade universal de um catamorfismo cata f do tipo genérico t a =b(a,t a) e suas derivadas: cancelamento-cata.
| Aula Teórica de 07.12.00 [Ref:8]: |
Sumário: Derivação das leis genéricas de reflexão-cata e de fusão-cata. Exemplos de aplicação.
Aula Teórica de 12.12.00 [Ref:6]:
Sumário: Derivação da lei genérica de absorção-cata.
Noção de functor polinomial. Forma canónica de um functor polinomial. Lei do binómio de Newton. Noção de tipo de dados indutivo polinomial. t a1...an =b(a1,...,an,ta1...an) .
Generalização da triologia cata-ana-hilo à indução polinomial.
| Aula Teórica de 14.12.00 [Ref:8]: |
Sumário: Triologia cata-ana-hilo associada ao tipo BTree (conclusão) : Exemplos célebres: os catamorfismos de travessia (in/pre/pós-ordem).
Estudo da triologia cata-ana-hilo associada ao tipo LTree : Exemplos: os hilomorfismos dfac (duplo factorial) e fib (série de Fibonacci). O hilomorfismo mSort ('merge sort').
Aula Teórica de 19.12.00 [Ref:6]:
Sumário: Introdução ao conceito de mónada : Motivação e definição formal. Operadores de composição, multiplicação e applicação monádica ('bind'). Extensão monádica de uma função.
| Aula Teórica de 21.12.00 [Ref:8]: |
Sumário: Introdução ao conceito de mónada (conclusão) : Propriedades. Mónadas em HASKELL: a class Monad e os operadores return, (»=), » e fail. Exemplos de mónadas: excepções, listas e funcionalidade de entrada/saída.
Conclusão : Síntese final. Quadro sinóptico classificativo dos algoritmos analisados e estudados ao longo da disciplina:
Classe B(A,X) B(A,C,X) Travessias Ordenação Factorial Outros RList 1 + A × X iSort fac sq LList 1 + X × A BTree 1 + A × X² in/pré/pós qSort hanoi LTree A + X² flatten mSort dfac fib FTree C + A × X²
Preenchimento do questionário de avaliação da disciplina.
Voltar à página principal de MP-I.
Outras disciplinas leccionadas pelo DIUM