Teoria de Categorias e Programação Funcional (23-2)

  • Professor: Hugo Nobrega
  • Turma 11974
  • Códigos no SIGA:
    • ICP35 Tóp. Esp. em Teoria da Computação I (currículo novo BCC)
    • ICP531 Tóp. Especiais em Teoria dos Grafos (currículo antigo BCC)
  • Grupo de discussões: Telegram
  • Fotos dos quadros: (a definir)
  • Local: Sala DCC (dentro do Instituto de Computação, segundo andar)

Funcionamento da disciplina

O meio primário de comunicação entre os alunos, monitores e professores será o grupo no Telegram listado acima.

As aulas serão realizadas em modalidade presencial, com aulas às 3as e 5as de 15:00 às 17:00 na sala DCC.

Bibliografia

Não seguiremos nenhum livro texto específico; nossas principais referências são o livros:

  • Milewski - Category Theory for Programmers: livro voltado para introduzir categorias para pessoas com perfil de programação. Livro gratuito!
  • Menezes, Haeusler - Teoria das Categorias para Ciência da Computação: idem acima, mas com uma pegada um pouco mais teórica (e em português!). Um pouco difícil de achar.
  • Leinster - Basic Category Theory: outro livro gratuito sobre teoria de categorias (recomendado por um ex-aluno da disciplina).
  • Awodey - Category Theory: livro mais no estilo “preciso”, e voltado principalmente para um público da matemática, mas que serve bem como referência.

Playlists de Youtube:

Outros livros (em ordem alfabética):

Outros links interessantes:

Listas de Exercícios

ListaData Limite de Entrega
Lista 14 de outubro às 23:59
Lista 24 de dezembro às 23:59
Lista 323 de dezembro às 23:59

Regras de colaboração

As listas de exercícios podem ser entregues em duplas. Não poderá haver repetição de duplas em diferentes listas! Isso é feito para aumentar a confiança do professor ao dar uma nota individual para cada aluno no final da disciplina.

As diferentes duplas podem sempre discutir os problemas e as ideias de como resolvê-los (e isso é recomendado, pois é uma ótima forma de estudar e aprender!), porém: soluções de exercícios não devem ser compartilhadas entre diferentes duplas (nem de outros períodos). O recomendável é que você não mostre suas soluções completas para alunos de outras duplas, nem veja as soluções completas de outros.

Soluções iguais ou parecidas demais entre duplas diferentes serão desconsideradas.

Cronograma planejado/registro de atividades

DataAulaConteúdoQuadros/Links
qui 10/81Introdução à disciplina; discussão sobre abstração0 a ?
ter 15/8-sem aula
qui 17/8-sem aula
ter 22/82Mais discussão sobre abstração e programação funcional
qui 24/83Definição informal de categorias e exemplos? a 24
ter 29/8-sem aula
qui 31/84Definição formal de categorias e exemplos25 a 31
ter 5/95Mais exemplos de categorias; a ideia de estruturas e preservação32 a 40
qui 7/9-sem aula
ter 12/96Preservação de estrutura (homomorfismos)41 a 51
qui 14/97Preservação de estrutura em categorias: Funtores52 a 64
ter 19/98Exemplos de funtor Set -> Set: “imagem direta”; discussão de funtores Prog -> Prog65 a 74
qui 21/99Introdução a Haskell; funtores em Haskell75 a 77; código; output do REPL
ter 26/910Mais introdução a Haskell: “condicionais” via pattern matching, if-then-else, case, guards; classes de tipos Show, Eq, Ord; construtor de tipos ArvBin + declaração de funtor78; código; output do REPL
qui 28/911Haskell: listas finitas e infinitas; foldcódigo
ter 3/1012Dúvidas da Lista 1; Haskell: discussão sobre “fold” para Naturais e Árvores Binárias79 a 81; código; output do REPL
qui 5/1013Haskell: Maybe; Categorias: produtos e coprodutos (discussão, intuição e definição)82 a 88
ter 10/1014Exemplos de produtos e coprodutos
qui 12/10-sem aula
ter 17/1015Mais sobre produtos e coprodutos (também em Haskell)slides; código em haskell; output do REPL
qui 19/1016Coproduto de monoides (exemplo de “construção livre”); isomorfismos (“produto é único a menos de isomorfismos”)slides
ter 24/1017Mais construções livres (monoides, magmas, números naturais, fórmulas da lógica proposicional); mais dicussão sobre isomorfismosslides; código em haskell; output do REPL
qui 26/1018Correção da frase “produtos de um mesmo par de objetos são únicos a menos de isomorfismo único”; diagramas, cones; objetos terminais; categoria de fatiasslides
ter 31/1019Diagramas, cones, limites, cocones, colimites; transformações naturais entre funtoresvídeo; slides
qui 2/11-sem aula
ter 7/11-sem aula
qui 9/1120Transformações Naturais: motivação, definição, exemplosvídeo; slides; output do REPL
ter 14/1121Cones e co-cones como transformações naturais de/para funtores constantes; transformações em Haskell são necessariamente naturais; isomorfismos naturais; equivalências de categorias; funtores adjuntos (pré-definição)vídeo; slides; código
qui 16/1122Adjunção: definição “misteriosa” usando o “método da mochila”; definição “mais intuitiva” buscando uma especificação da noção de “livre” para monoidesvídeo; slides; código; output do REPL
ter 21/1123Adjunção: mais exemplos e definições equivalentes; relações entre “liberdade” e outras noções (indução, recursão)vídeo; slides; código; output do REPL
qui 23/1124Funtores “Hom set”; 3a definição de adjunção; funtor adjunto à esquerda do produto (cópia)vídeo; slides
ter 28/1125Recap e correção do exemplo “funtor adjunto à esquerda do produto”; Haskell: Applicative (pure, “apply” <*>, lift)vídeo; slides; código; output do REPL
qui 30/1126Haskell: (mais) Applicative, Alternative, Traversable e suas leisvídeo; código; resumo das leis
ter 5/1227Haskell: “Acumulação de erros”, logs simples com Applicative; Monad (3 definições): categoria de Kleislivídeo; código; output do REPL; pequeno texto descrevendo Monads
qui 7/1228Haskell: mais sobre Monads; (>>) “e então”; notação “do”; exemplos de uso; (a,) e (r ->) são Monadsvídeo; slides; código; output do REPL
ter 12/12-sem aula
qui 14/12-sem aula
ter 19/12-sem aula
qui 21/12-sem aula

Método de avaliação

~5 listas de exercícios, com descarte de ~1 pior(es) nota(s). Não há prova final; a nota para aprovação ao final do período é 5,0.