Estruturas de dados puramente funcionais
Índice
Apresentação do Curso
Quando programadores de C, C++, Java, Python,… precisam de uma estrutura de dados específica:
- Usam uma biblioteca;
- Abrem um dos inúmeros livros de algoritmos como o CLRS e copiam o código.
Infelizmente programadores de linguagens funcionais como Haskell Erlang/Elixir, Clojure ou ML não podem se dar a esse luxo. Apesar de muitos desses textos se dizerem independentes da linguagem de programação, eles são independentes apenas no sentido Henry Ford: "Programadores podem usar a linguagem que quiserem, contanto que ela seja imperativa!".
Figura 1: Henry Ford certa vez disse sobre as cores disponíveis para o Ford T: "[Os clientes] podem escolher a cor que quiserem, contanto que seja preta".
Apesar de linguagens funcionais estarem amplamente disponíveis há mais de 50 anos (Lisp foi apresentada ao mundo em 1958), surpreendentemente o primeiro livro texto que aborda estruturas de dados e seus algoritmos em um contexto funcional só foi publicado por Okasaki em 1998, ou seja, 40 anos após o nascimento de Lisp.
EDs funcionais têm diversas características que as diferenciam de suas colegas imperativas. Essas diferenças são tantas que justificam o seu estudo de maneira independente. Por exemplo, EDs funcionais são persistentes, o que significa que diversas versões da mesma ED podem conviver simultaneamente facilitando, por exemplo, a programação concorrente e paralela nestas estruturas.
Neste curso vamos explorar algumas das estruturas de dados funcionais mais comuns. Também veremos as técnicas mais comuns que são utilizadas nas suas implementações. Assim, ao final deste curso, o aluno saberá desenvolver a sua própria ED ou adaptar uma ED imperativa a um contexto funcional sempre que precisar.
Metodologia
O livro texto principal para este curso é o "Purely Functional Data Structures" de Chris Okasaki. Este livro é uma versão com pequenas modificações da sua tese de doutoramento que está disponível gratuitamente aqui.
Diversas outras referências também foram utilizadas neste curso. Estas referências serão dadas no próprio material didático disponibilizado aos alunos.
As aulas serão teóricas com exemplos e demonstrações reais dos algoritmos, estruturas de dados e códigos implementados durante as aulas.
Pré-requisitos
É desejável que os participantes tenham noções de análise de algoritmos além de conhecimento sobre estruturas de dados básicas (tradicionais).
Os exemplos de código serão dados em Haskell (o livro texto também traz alguns códigos em ML). Contudo você pode utilizar a linguagem de programação que desejar para fazer os trabalhos a serem entregues. Atente-se, contudo, ao fato de que caso escolha alguma linguagem não funcional algumas coisas vão ficar bem mais complicadas de programar.
O foco do curso são as estruturas de dados puramente funcionais e, apesar de utilizarmos Haskell, não é voltado a uma linguagem específica.
Apesar de ser possível acompanhar o curso sem nunca ter visto Haskell, isto vai exigir um pouco mais de estudo por parte do aluno para entendimento dos exemplos dados em aula.
Avaliação
A avaliação será dada através de 03 atividades de programação que deverão ser entregues em até duas semanas após o término das aulas.
O aluno será considerado aprovado se:
- obtiver no mínimo 75% de presença.
- entregar 60% das atividades corretamente.
Programação
23/11: Por que EDs funcionais?; Persistência; Listas; Heaps; Árvores
30/11: Árvores de busca balanceadas (Rubro-Negra e AVL); Avaliação preguiçosa; Princípios de análise amortizada; Heaps preguiçosos
7/12: Listas com acesso aleatório; Monoides; Finger trees
Datas e Sala
- Datas: 23/11, 30/11 e 07/12
- Horário: 08h30 às 12h30
- Sala: S-211-0
O curso será ministrado pelo professor Emílio Francesquini e terá duração de 12 horas.
Inscrições
- Número de vagas: 110
- Para se inscrever:
https://sig.ufabc.edu.br/sigaa/link/public/extensao/visualizacaoAcaoExtensao/927
- Para se cadastrar o usuário deve clicar em "Clique aqui para fazer a sua Inscrição" → "Ainda não possuo cadastro".
- Insira os dados solicitados e aguarde e-mail para finalização do cadastro. Após a finalização do cadastro, insira o e-mail e senha, clique em “Cursos e Eventos Abertos" e faça o cadastro no curso.
Pré-requisitos
Gostar de programar e ter noções de estruturas de dados e algoritimos.
Como Chegar
Universidade Federal do ABC
Avenida dos Estados, 5001
Santo André - SP
CEP 09210-580
Acesso pelos endereços:
- Av. dos Estados, 5001.
- R. Abolição, 378
- R. Santa Adélia, (em frente ao no. 221)
Estações de trem próximas (recomendamos utilizar Uber para o trajeto estação-campus):
- Prefeito Saladino (CPTM L10)
- Santo André (CPTM L10)
Mais informações: http://www.ufabc.edu.br/a-ufabc/campi/santo-andre
Material do Curso
Atividades e Suporte
As atividades do curso estão descritas e deverão ser submetidas pelo GitHub Classroom.
| Aula | Prazo | Atividade | Link para submissão |
|---|---|---|---|
| Aula 01 | 22/12 | Lista 01 | https://classroom.github.com/a/fDhdMEit |
| Aula 02 | 22/12 | Lista 02 | https://classroom.github.com/a/OAbRlbWI |
| Aula 03 | 22/12 | Lista 03 | https://classroom.github.com/a/yPDUUsCS |
- Para submeter uma atividade, basta clicar no link da atividade para criar um novo repositório no Github.
- Não deixe de escolher o seu nome na lista para que possamos relacionar o usuário GitHub à você!
- O repositório é privado e todos os arquivos e alterações adicionados ao repositório poderão ser acessados apenas pelo aluno e pelo professor da disciplina.
Discussão e dúvidas
Durante o curso, utilizem o Discord (https://discord.gg/qDPxdbE) para tirar dúvidas. Nele também serão compartilhados materiais extras.
Contato
Emilio Francesquini - e.francesquini@ufabc.edu.br
Ou via Discord em: https://discord.gg/qDPxdbE