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

  • Professor: Hugo Nobrega
  • Códigos no SIGA:
    • ICP035 Tóp. Esp. em Teoria da Computação I, turma 8823 (currículo novo BCC)
    • ICP531 Tóp. Especiais em Teoria dos Grafos, turma 12857 (currículo antigo BCC)
  • Grupo de discussões: Discord
  • 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 Discord listado acima.

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

Bibliografia

PDF com os conteúdos dos quadros ao longo do semestre (arquivo atualizado periodicamente)

Não seguiremos nenhum livro texto específico; nossas três 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.
  • 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 1 (atualizada 29/9)11 de outubro no começo da aula
Lista 218 de outubro no começo da aula
Lista 3 (atualizada 26/10)3 de novembro no começo da aula
Lista 4 (atualizada 2/12)22 de dezembro no começo da aula
Lista 5 e Parser.hs14 de janeiro à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
ter 30/8Aula 1Introdução; Discussão sobre abstração; Funções puras e “impuras”; A ideia de Categorias1 a 8
qui 1/9Aula 2Exemplo de abstração em matemática (“unicidade de elemento neutro de uma operação, quando existe”); Definição semi-formal de categoria; primeiro exemplo (conjuntos e funções)9 a 19
ter 6/9Aula 3Definição “oficial” de categorias; Exemplos20 a 32
qui 8/9Aula 4Resolução do exercício (categoria vinda de um conjunto+relação); mais exemplos de categorias (“1”, “1+1”, “2”, “categoria oposta” ou “dual”); primeira discussão da ideia de “preservação de estrutura”33 a 44
ter 13/9Aula 5Discussão mais precisa de assinaturas, estruturas e homomorfismos (“mapeamentos que preservam estrutura”); funtores (“homomorfismos entre categorias”)45 a 59
qui 15/9Aula 6Prova de que P (“powerset”, conjunto das partes) é um funtor Set -> Set; exemplo de categoria (Prog), dos tipos e funções em uma linguagem de programação funcional pura (fortemente tipada)60 a 69
ter 20/9Aula 7Recap do funtor “partes” (Set -> Set) e de funtores Prog -> Prog (construtor de tipos F :: t -> s + implementação de fmap :: (t -> s) -> (F(t) -> F(s))); ideia de “como seria” o fmap de listas em python (código de python); primeiro contato com Haskell, exemplo de funtores List e Maybe; definição de um novo funtor “Talvez”; definição (incompleta) de um novo funtor “ArvBin”; código de haskell70 a 73
qui 22/9Aula 8haskell: definindo tipos [exemplo com Naturais], a ideia do “lazy”. Código em haskell74 e 75
ter 27/9Aula 9haskell: definindo funções prefixas e infixas; definindo classes de tipos (typeclasses); definindo instâncias de classes de tipos; código em haskell76 e 77
qui 29/9Aula 10haskell: condicionais em haskell; listas; lazy “just in time evaluation”); exemplo de Fibonacci e Crivo de Eratóstenes (da Aula 8; código em haskell78 a 80
ter 4/10Aula 11haskell: foldr, foldl; “funções produtivas” e laziness; código em haskell ; output do REPL do haskell; código em python; output do REPL do python81 e 82
qui 6/10Aula 12haskell: exemplos de uso do fold: produto, soma, length; “fold para Natural”: soma, produto, potência, etc, como folds; hierarquia de funções recursivas de crescimento muito rápido; motivação para os próximos assuntos: “como especificar que um tipo X serve como retorno de uma função se eu queria na verdade retornar um Integer e uma String?”; código em haskell; output do REPL do haskell83 a 87
ter 11/10Aula 13especificação de “produto de A e B” em haskell; implementação (3 versões: “manual”, tuplas, records); discussão sobre especificação usando apenas a linguagem das categorias; código em haskell; output do REPL do haskell88 a 95
qui 13/10Aula 14Diagramas e diagramas comutativos; produto (definição e exemplos: em Haskell, em Set, na categoria “Naturais com menor ou igual”, na categoria “Naturais com divisibilidade”, na categoria do Rufino da Aula 3)96 a 109
ter 18/10Aula 15Mais discussão sobre produtos; prova de que o exemplo com “Dumbo” e “papagaio” (exemplo 2b) é um produto em Set; isomorfismos em categorias (motivação e definição); prova de que produtos são “únicos a menos de isomorfismo”110 a 120
qui 20/10Aula 16Discussão sobre definições equivalentes para “isomorfismos”; coproduto (definição e exemplos)121 a 130
ter 25/10Aula 17Discussão sobre a expressão “… a menos de isomorfismo único” usada para falar sobre produtos, coprodutos, etc (o isomorfismo é único, mas em outra categoria!); busca por coproduto de monoides (difícil!)131 a 137
qui 27/10Aula 18Coprodutos (“tipos soma” ou “sum types”) em Haskell; Produtos e coprodutos no poset “conjuntos e ‘contido’”; Coprodutos para monoides gerais não é o produto (mas funciona para monoides comutativos!); Coprodutos de monoides (a ideia de “geração livre”)138 a 147
ter 1/11Aula 19Mais sobre construções livres (magma livre); construções livres em haskell; “eliminadores”: setas obtidas pela UMP de um coproduto (either para Either, bool para Bool, ±foldr para listas); desvio discutindo relação entre recursão, soluções de “equações” e pontos fixos; código em haskell148 a 153
qui 3/11Aula 20Mais discussão sobre recursão, soluções de “equações” e pontos fixos; recap da ideia de “a menos de isomorfismo único”: construção de uma categoria dos diagramas com “formato de produto”; definição de objetos iniciais e objetos terminais154 a 164
ter 8/11Aula 21Exemplos de objetos iniciais e terminais em diversas categorias (incluindo Hask); visão geral da construção da aula 20: índices, diagramas, cones, limites; código em haskell; output do REPL165 a 176
qui 10/11Aula 22Definição de cones, cocones, limites, colimites de um diagrama; recap da lista 1: como ver um grafo como um funtor da categoria •⇉• para Set; homomorfismos de grafos nesse novo contexto; transformações naturais: definição e alguns exemplos177 a 188
ter 15/11sem aulaFeriado
qui 17/11Aula 23
ter 22/11Aula 24
qui 24/11sem aulaJogo do Brasil na Copa
ter 29/11Aula 25
qui 1/12Aula 26
ter 6/12Aula 27haskell: Applicative; código em haskell; output do REPL
qui 8/12Aula 28haskell: mais sobre Applicative; código em haskell; output do REPL
ter 13/12Aula 29haskell: Alternative e Traversable; código em haskell; output do REPL
qui 15/12Aula 30haskell: Monad; código em haskell
ter 20/12Aula 31Última aula! haskell: código em Haskell
qui 22/12sem aulaRecesso de fim de ano
ter 27/12sem aulaRecesso de fim de ano
qui 29/12sem aulaRecesso de fim de ano
ter 3/1
qui 5/1
ter 10/1
qui 12/1

Método de avaliação

A definir…