Estruturas de Dados Puramente Funcionais

Playlists

1 Introdução

Quando programadores de C, C++, Java, Python, … precisam de uma estrutura de dados específica:

  • Usam uma biblioteca.
    • Legal! Também funciona em funcional! (sic)
  • Abrem um livro como o [CLRS] e copiam o código.
    • Infelizmente, programadores de linguagens funcionais como Haskell, e ML não podem se dar a esse luxo.

Apesar desses livros se dizerem “independentes da linguagem de programação”, eles são independentes apenas no sentido do Henry Ford:

Programadores podem usar a linguagem que quiserem, contanto que ela seja imperativa1.

Queremos ajudar a resolver este problema!

1.1 Objetivos

Nas aulas seguintes, mostraremos como implementar e manipular algumas estruturas de dados clássicas no contexto funcional. Além disto também apresentaremos algumas estruturas nascidas no contexto funcional para lidar com as suas peculiaridades como imutabilidade, persistência, transparência referencial, avaliação preguiçosa, …

2 Estruturas funcionais vs. estruturas imperativas

  • Apesar de muitos reconhecerem os benefícios das linguagens funcionais, até recentemente elas eram pouco utilizadas e até mesmo pouco conhecidas.

  • Isso explica, em parte, porque os códigos existentes atualmente são majoritariamente imperativos.

  • Além disto, historicamente, linguagens funcionais tinham um desempenho bem inferior ao de linguagens tradicionais. Isso tem mudado bastante com a evolução de compiladores que fazem análises sofisticadas de código.

  • De qualquer modo, mesmo com compiladores espetaculares é improvável que eles sejam capazes de resolver problemas de uso de estruturas de dados com desempenhos ruins.

Então basta usarmos boas estruturas!

2.1 Mais fácil falar do que fazer…

Mas porque desenvolver estruturas de dados funcionais é mais difícil que estruturas imperativas?

  • Motivo 1 - Inexistência de atualizações destrutivas

Atualizações destrutivas exigem cuidado em seu uso, porém podem ser extremamente poderosas e eficientes se bem utilizadas.

  • Motivo 2 - Aumento de expectativa

Em uma estrutura imperativa, raramente esperamos que ela seja persistente (en: persistent ⬌ ephemeral).

Estruturas de dados persistentes são aquelas que permitem a existência simultânea de diversas versões da estrutura (tipicamente com compartilhamento de dados).
Estruturas de dados efêmeras são aquelas que permitem a existência de apenas uma versão da estrutura de dados simultaneamente.

2.2 Paradigma funcional vs. imperativo

  • Em linguagens de programação funcional, estruturas de dados funcionais são sempre persistentes.
  • Em linguagens imperativas, estruturas de dados são tipicamente efêmeras e, quando programadores destas linguagens precisam de estruturas persistentes, eles não se surpreendem e aceitam estruturas cuja facilidade de uso, implementação e complexidade computacional são superiores às suas versões efêmeras.

Queremos, então:

  • Persistência.
  • Mesma complexidade computacional de EDs efêmeras.

Não nos ajuda o fato de que é possível mostrar que, em alguns casos, linguagens funcionais são intrinsecamente menos eficientes que suas colegas imperativas.

  • Era de se esperar, já que o hardware é imperativo.

2.3 Jogamos a toalha?

Ainda há esperança! A verdade é que, na prática, a coisa não é tão assustadora assim!

  • Para praticamente todas as estruturas de dados cobertas em um curso de graduação de computação, já se conhecem implementações funcionais cuja complexidade assintótica é a mesma das versões imperativas.
  • Nas próximas aulas vamos explorar algumas estruturas de dados funcionais mais comuns. Mas não vamos dar um catálogo, vamos, na verdade, mostrar as técnicas usadas para que você possa desenvolver a sua própria ED quando precisar.

3 Referências

3.1 Livros

  • [CO]
  • Purely Functional Data Structures
    • Por Chris Okasaki

4 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.

  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” ↩︎