| Métodos de Programação I - 1998/99 |
|---|---|
| [ DI/UM ] |
Sumário: Apresentação da disciplina. Equipa docente. Programa da disciplina e seu enquadramento no plano de estudos. Regime de avaliação. Informação electrónica sobre a disciplina: URL: HTTP://WWW.DI.UMINHO.PT/ JNO/HTML/MPI.HTML. Bibliografia.
Sumário: Introdução à programação funcional -- sua motivação e antecendentes históricos.Iniciação à teoria dos tipos de dados. Conceito de função. A função como contrato. Diagramas funcionais. Domínio e codomínio. Igualdade extensional. Composição de funções. Função identidade. Notação com ou sem variáveis.
Sumário: Apresentação da disciplina. Equipa docente. Programa da disciplina e seu enquadramento no plano de estudos. Regime de avaliação . Informação electrónica sobre a disciplina: URL: HTTP://WWW.DI.UMINHO.PT/ JNO/HTML/MPI.HTML. Bibliografia.
Sumário: Introdução à programação funcional -- sua motivação e antecendentes históricos.Iniciação à teoria dos tipos de dados. Conceito de função. A função como contrato. Diagramas funcionais. Domínio e codomínio. Composição de funções. Função identidade. Notação com ou sem variáveis.
Sumário: Iniciação à teoria dos tipos de dados (cont.). Associatividade da composição. Polimorfismo da identidade. Funções constantes. Polimorfismo de uma função constante.Expectro da preservação da informação: funções injectivas, sobrejectivas e bijectivas. Noções de abstracção e de isomorfismo entre domínios de dados.
Sumário: Iniciação à teoria dos tipos de dados (cont.). Elaboração estrutural do domínio e/ou codomínio de uma função. Construções básicas da teoria de conjuntos usadas na estruturação dos tipos de dados:O produto A ×B («struct»), suas projecções e a construção <f,g>. O coproduto A + B («union»), suas injecções e a construção [f,g].
Propriedades de cancelamento-× e cancelamento-+. Lei da troca.
Sumário: Iniciação à teoria dos tipos de dados (cont.). Associatividade da composição. Polimorfismo da identidade. Funções constantes. Polimorfismo de uma função constante.Expectro da preservação da informação: funções injectivas, sobrejectivas e bijectivas. Noções de abstracção e de isomorfismo entre domínios de dados.
Construções básicas da teoria de conjuntos usadas na estruturação dos tipos de dados:
O produto A ×B («struct»), suas projecções e a construção <f,g>. Propriedades de cancelamento do produto. O coproduto A + B: analogia com («union»).
Sumário: As estruturas A + B e A ×B (cont.). As injecções em A + B e a construção [f,g].Propriedades de cancelamento-× e cancelamento-+. Lei da troca.
As construções f ×g e f+g. Propriedade da absorção-×.
Sumário: As estruturas A ×B e A + B (cont.). As construções f ×g e f+g. Propriedades de absorção e suas derivadas. Propriedades de fusão e de reflexão.
Sumário: As estruturas A ×B e A + B (cont.): Propriedades functoriais. Predicados e guardas. Condicional de McCarthy.Tipos elementares genéricos: 0 (Void), 1 (()), 2 (Bool) e Nat. O conceito de «apontador» 1 + A.
Sumário: As estruturas A ×B e A + B (cont.): Propriedades de absorção e suas derivadas. Propriedades de fusão e de reflexão.
Sumário: As estruturas A ×B e A + B (cont.): Propriedades functoriais. Predicados e guardas. Condicional de McCarthy.
Sumário: As estruturas A ×B e A + B (conclusão): Produtos e coprodutos n-ários ( n>=0). As funções ! : A ->1 e ? : 0 ->A.Introdução aos tipos de dados recursivos: uma analogia com a programação imperativa.
Sumário: Sessão de apoio ao trabalho laboratorial em curso.
Sumário: Sessão de apoio ao trabalho laboratorial em curso.
Sumário: Introdução aos tipos de dados recursivos: uma analogia com a programação imperativa.
Sumário: Introdução aos tipos de dados recursivos (cont.): Declaração de tipos de dados em HASKELL . Sua relação com o coproduto. Tipos enumerados. Tipos de dados recursivos.
Sumário: Introdução aos tipos de dados recursivos (cont.): apresentação dos conceitos de catamorfismo e anamorfismo usando como tipo de dados exemplo listas de inteiros - data X = Nil | Cons(Int,X).
Sumário: Introdução aos tipos de dados recursivos (cont.): Declaração de tipos de dados em HASKELL . Sua relação com o coproduto. Tipos enumerados. Tipos de dados recursivos.
Sumário: Introdução aos tipos de dados recursivos (cont.): apresentação dos conceitos de catamorfismo e anamorfismo usando como tipo de dados exemplo listas de inteiros - data X = Nil | Cons(Int,X).
Sumário: Introdução aos tipos de dados recursivos (cont.): apresentação do conceito de hilomorfismo usando como tipo de dados exemplo listas de inteiros - data X = Nil | Cons(Int,X).
Sumário: Introdução aos tipos de dados recursivos (cont.): O factorial como hilomorfismo de padrão X.
Sumário: Introdução aos tipos de dados recursivos (cont.): apresentação do conceito de hilomorfismo usando como tipo de dados exemplo listas de inteiros - data X = Nil | Cons(Int,X).
Sumário: Introdução aos tipos de dados recursivos (cont.): O factorial como hilomorfismo de padrão X, para data X = Nil | Cons(Int,X).Noção de estrutura de dados virtual e sua relação com a avaliação retradada.
Sumário: Introdução aos tipos de dados recursivos (cont.): Apresentação do algoritmo de ordenação por inserção simples como catamorfismo da estrutura data X = Nil | Cons(Int,X).
Sumário: Introdução à parametrização de tipos de dados recursivos e ao polimorfismo, tomando como exemplo data List a = Nil | Cons(a, List a).
Sumário: Apresentação do algoritmo de ordenação por inserção simples como catamorfismo da estrutura data X = Nil | Cons(Int,X).
Sumário: Introdução à parametrização de tipos de dados recursivos e ao polimorfismo, tomando como exemplo data List a = Nil | Cons(a, List a).Definição de mapList: (a -> b) -> X a -> X b como um catamorfismo «célebre».
Sumário: Introdução à parametrização e ao polimorfismo (cont.): Cálculo de mapList: (a -> b) -> X a -> X b como um catamorfismo «célebre».
Sumário: Generalização: noção de tipo base de uma definição recursiva e sua aplicação à catalogação de tipos de dados recursivos.Exemplo: catalogação de
(a) árvores binárias simples, ou listas bi-lineares: data BTree a = Empty | Node(a, (BTree a, BTree a));
(b) árvores binárias com folhas: LTree a = Leaf a | Split (LTree a, LTree a);
(c) árvores binárias com nós e folhas: LBTree a c = Unit a | Node(a, (LBTree a c, LBTree a c));
Sumário: Conclusão da aula anterior.
Sumário: Generalização: noção de tipo base de uma definição recursiva e sua aplicação à catalogação de tipos de dados recursivos.Exemplo: catalogação de
(a) árvores binárias simples, ou listas bi-lineares: data BTree a = Empty | Node(a, (BTree a, BTree a));
(b) árvores binárias com folhas: LTree a = Leaf a | Split (LTree a, LTree a);
(c) árvores binárias com nós e folhas: LBTree a c = Unit a | Node(a, (LBTree a c, LBTree a c));
Sumário: Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplos: os catamorfismos traces e map.
Sumário: Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplos: os catamorfismos traces e map, e o hilomorfismo qSort ('quick sort').
Sumário: Estudo da triologia cata-ana-hilo associada ao tipo LTree. Exemplos: o catamorfismo flatten e os hilomorfismos dfac (duplo factorial ) e fib (série de Fibonacci ).
Sumário: Triologia cata-ana-hilo associada ao tipo BTree (conclusão): Exemplos: o catamorfismo map e o hilomorfismo qSort ('quick sort').
Sumário: Triologia cata-ana-hilo associada ao tipo LTree (conclusão): Exemplos: o hilomorfismo mSort ('merge sort') e o catamorfismo map.Estudo da triologia cata-ana-hilo associada ao tipo FTree. O catamorfismo bmap.
Sumário: Noção de functor e de bi-functor, e sua realização em HASKELL , sob a forma das classes Functor e BiFunctor. Propriedades functoriais.
Sumário: Estudo da triologia cata-ana-hilo associada ao tipo LTree. Exemplos: os catamorfismos flatten e map; os hilomorfismos dfac (duplo factorial ), fib (série de Fibonacci ).
Sumário: Triologia cata-ana-hilo associada ao tipo LTree (conclusão): mSort ('merge sort').Triologia cata-ana-hilo associada ao tipo FTree.
Noção de functor e de bi-functor, e sua realização em HASKELL , sob a forma das classes Functor e BiFunctor. Propriedades functoriais.
Sumário: Tipos de dados são functores : Formulação genérica da triologia cata-ana-hilo para tipos de dados recursivos da forma T a1...an =B(a1,...,an,Ta1...an) .
Sumário: Tipos de dados são functores (cont.): Noção de functor tipo (map) e sua formulação genérica como catamorfismo de um tipo de dados recursivo da forma T a1...an =B(a1,...,an,Ta1...an) .
Sumário: Tipos de dados são functores (cont.): Noção de functor tipo (map) e sua formulação genérica como catamorfismo de um tipo de dados recursivo da forma T a1...an =B(a1,...,an,Ta1...an) .
Sumário: Tipos de dados são functores (conclusão): Noção de functor polinomial. Introdução ao estudo da construção exponencial BA. Noção de espaço funcional.
Sumário: Tipos de dados são functores (conclusão): Noção de functor polinomial. Introdução ao estudo da construção exponencial BA. Noção de espaço funcional.
Sumário: Estudo da construção exponencial BA (conclusão): Noção de função transposta . O operador implícito ap. Os isomorfismos curry e uncurry e sua importância na programação funcional.
Sumário: Estudo da construção exponencial BA (conclusão): Noção de função transposta . O operador implícito ap. Os isomorfismos curry e uncurry e sua importância na programação funcional.
Sumário: Inferência de tipos polimórficos: apresentação ao Algorítmo W de Hindley-Damas-Milner.Considerações finais. Encerramento da disciplina.
Sumário: Inferência de tipos polimórficos: apresentação ao Algorítmo W de Hindley-Damas-Milner.Considerações finais. Encerramento da disciplina.