Teoria de Categorias e Programação Funcional (2022.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 F2-027

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

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 21/9)4 de outubro no começo da aula

Regras de colaboração

É permitido (e até recomendado) que os alunos estudem juntos, porém cada aluno(a) deve escrever e entregar suas próprias soluções. Soluções iguais ou muito parecidas serão desconsideradas. Para evitar problemas, recomendo que você nem mesmo olhe soluções prontas de seus colegas, e também recomendo que ao discutir soluções com colegas, você não tenha as sua soluções abertas à sua frente.

Cronograma planejado/registro de atividades

DataAulaConteúdo
ter 30/8Aula 1Introdução; Discussão sobre abstração; Funções puras e “impuras”; A ideia de Categorias
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)
ter 6/9Aula 3Definição “oficial” de categorias; Exemplos
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”
ter 13/9Aula 5Discussão mais precisa de assinaturas, estruturas e homomorfismos (“mapeamentos que preservam estrutura”); funtores (“homomorfismos entre categorias”)
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)
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 haskell
qui 22/9Aula 8Continuação do “minicurso de haskell” (definindo tipos [exemplo com Naturais], a ideia do “lazy”). Código em haskell
ter 27/9
qui 29/9
ter 4/10
qui 6/10
ter 11/10
qui 13/10
ter 18/10
qui 20/10
ter 25/10
qui 27/10
ter 1/11
qui 3/11
ter 8/11
qui 10/11
ter 15/11sem aulaFeriado
qui 17/11
ter 22/11
qui 24/11
ter 29/11
qui 1/12
ter 6/12
qui 8/12
ter 13/12
qui 15/12
ter 20/12
qui 22/12
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…