Programa resumido

• Motivação. Teoria e método em programação. Cálculo e raciocínio sobre programas. Composicionalidade. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programação.

• Programação funcional: sua motivação e antecendentes históricos. Composição de funções. Noções de abstracção e de isomorfismo.

• Iniciação à estruturação de dados. Combinadores básicos e suas propriedades estruturais (reflexão, fusão, absorção, cancelamento e de functorialidade). Álgebra de um tipo de dados. Lei da troca.

• Introdução às estruturas de dados indutivas regulares. Álgebras de functores. A triologia «cata-ana-hilo». Recursividade polinomial. Caso de estudo: algoritmos de ordenação.

• Regras para codificação de estruturas de dados funcionais na linguagem de programação C.

• Parametrização e polimorfismo. Inferência de tipos polimórficos. Programação genérica. Functores de tipo. Introdução ao politipismo.

• Programação modular.

• Programação funcional com mónades. `Input/output'. Excepções.

Programa detalhado

1. Teoria e método em programação. Concepção composicional e reutilização. Combinadores de programas. Modelação funcional de problemas.

2. 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. Igualdade extensional. Diagramas funcionais. Recurso a setas f : A -> B e diagramas. Notação funcional com ou sem variáveis.

3. Combinadores de programas funcionais. A composição f · g como combinador elementar de funções. Associatividade da composição: Função identidade id. O polimorfismo de id e a propriedade f ·id = id ·f = f e seu diagramas comutativo. O combinador <f,g> e o produto A × B (analogia com «struct» em C) e suas projecções. O combinador [f,g] e o coproduto A + B (analogia com «union» em C) e suas injecções. Os combinadores f × g e f + g . Noção de isomorfismo entre tipos de dados. Funções bijectivas ou isomorfismos. Função inversa. Predicados e guardas. Condicional de McCarthy.

4. Álgebra da programação funcional. Inferência de tipos polimórficos com recurso a diagramas. Propriedades naturais e propridades universais. Propriedades de reflexão. Propriedades de cancelamento e fusão. Lei da troca. Propriedades de absorção e propriedades functoriais. Leis de fusão do condicional de McCarthy.

5. Programação funcional em HASKELL. Costumização de produtos e coprodutos. Álgebras e coálgebras de tipos de dados. O conceito de «apontador» 1 + A (Maybe a em HASKELL). Funções parciais.

6. Programação com tipos de dados indutivos. Tipos de dados recursivos vistos como equações. Os número naturais e a equação N =1 + N. As listas ligadas e a equação L = 1 + A × L. Noção de combinadores recursivos. Exemplos: catamorfismos e anamorfismos. Hilomorfismos (anamorfismos seguidos de catamorfismos). Apresentação do módulo List.hs. Estudo da triologia cata-ana-hilo associada ao tipo List. O algoritmo de cálculo do quadrado de um número visto como hilomorfismo sobre a estrutura List a. O algoritmo de ordenação por inserção simples visto como hilomorfismo sobre a estrutura List a. Introdução ao tipo de dados árvores binárias simples, ou listas bi-lineares. Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplo: o hilomorfismo qSort (`quick sort'). Estudo da triologia cata-ana-hilo associada ao tipo LTree. Exemplos: o hilomorfismo fib (série de Fibonacci) e o hilomorfismo mSort (`merge sort').

7. Definição genérica de um tipo indutivo de dados. Noção de functor de base. Operadores fmap vs 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)). Propriedade universal de um catamorfismo cata (f) do tipo genérico T a =B(a,t a) e suas derivadas: cancelamento-cata e reflexão-cata.

8. Classificação algorítmica. Quadro sinóptico dos principais algoritmos analisados e estudados ao longo da disciplina. Polimorfismo versus politipismo. Programação dita «genérica».

9. Programação funcional monádica. Motivação: funções parciais e sua composição. Manipulação de erros e mecanismos de excepção («exception handling»). Funções monádicas envolvendo listas. Mónadas versus functores. Noção de functor. Propriedades functoriais. Functores em HASKELL: a class Functor e o operador fmap. Regra geral para a composição monádica. Definição formal de mónade. Composição e sua unidade. Multiplicação e suas propriedades. Exemplos: listas e Maybe. Mónadas em HASKELL: a class Monad e os operadores return, (»=) e ». A notação do. Introdução à notação em compreensão. A definição fmap f x = do { a <- x ; return (f a) }. Regras para a monadificação de funções arbitrárias com recurso à notação "do".