A Beleza da Recursão e Pattern Matching (Casamento de Padrões) em Linguagens de Programação Funcionais
- Artigo original: The beauty of recursion and pattern matching in functional programming languages
- Tradução: Eric Douglas
%% Função lookup recebe uma Key e um Node
lookup(_, {node, 'nil'}) ->
undefined;
lookup(Key, {node, {Key, Val, _, _}}) ->
{ok, Val};
lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey ->
lookup(Key, Smaller);
lookup(Key, {node, {_, _, _, Larger}}) ->
lookup(Key, Larger).
%% Explicação sobre parâmetros e estrutura de dados
%%
%% Nó vazio -> {node, 'nil'}
%% Nó não vazio -> {node, {Key, Val, Smaller, Larger}}
%% node -> é apenas um atom, como uma constante
%% Key e Val -> podem ser de tipos diferentes
%% Smaller e Larger -> Pode ser estruturas de nós vazios ou não vazios,
%% então você pode ter sua árvore bináriaGostaria de te convidar para admirar a beleza, concisão e poder do código acima [1].
É uma função que encontra um valor em uma árvore binária, usando recursão e pattern matching (casamento de padrões).
Podemos ver quão simples e extremamente declarativo é escrever uma função com esses conceitos e técnicas oriundas de linguagens de programação funcional.
Temos absolutamente ZERO instruções dizendo COMO o algoritmo deve trabalhar! Nós apenas expressamos O QUÊ ele deve fazer, não como.
O código foi escrito em Erlang.
Essa função vai buscar em uma árvore binária pela chave Key passada para ela, e vai retornar uma tupla com o valor Val (valor) associado com a chave passada, ou undefined se a chave não for encontrada.
Uma grande vantagem que temos no Erlang e Elixir é a possibilidade de criar mais casos para a mesma função apenas mudando o padrão em seus parâmetros.
A função tem o mesmo nome e aridade (número de parâmetros), mas como o padrão é diferente, é como se fosse uma outra função.
Os casos vão ser verificados de cima pra baixo, então devemos colocar os casos específicos primeiro, e casos gerais no fim. Pense nisso como uma forma funcional de escrever declarações switch ou if / else.
Nós temos quatro casos possíveis em nossa função lookup/2, então vamos ver o que cada um faz:
O primeiro lookup vai ignorar o primeiro valor passado para ele (_), e se o segundo valor casar, ele vai retornar undefined. Como você pode ver, o segundo valor é um nó vazio.
O segundo lookup vai ver se a chave Key que passamos é a mesma Key do nó passado. Se for, nós acabamos de encontrar o nó que contém o valor que queremos retornar.
Nesse caso, lookup retorna {ok, Val}, onde Val é o valor que estávamos interessados.
O terceiro lookup vai identificar com o caso onde a chave que passamos é diferente da chave do nó passado.
Também temos uma cláusula de guarda na assinatura da função, para deixá-la mais específica. A cláusula de guarda when Key < NodeKey é importante para decidirmos em que direção devemos ir para buscar o valor que esperamos.
Nesse caso, sabemos que se a chave Key é menor que NodeKey, nós precisamos continuar nossa busca no nó Smaller. Então usamos pattern match (casamento de padrão) para extrair o valor Smaller (menor) e ignorar o resto dos dados que não vamos usar com _ novamente.
Para continuar nossa busca, quando nós paramos na terceira função lookup, nós vamos chamá-la recursivamente, agora com os seguintes dados lookup(Key, Smaller).
Isso é recursão e casamento de padrões em ação! ❤
No último caso, e o mais geral, é quando todas as prévias funções lookup não foram "casadas". Nós sabemos que isso só vai acontecer quando a chave Key passada é diferente da Key do nó atual, e a Key passada é maior que a chave no nó atual, então temos que continuar a buscar no nó maior Larger.
Nesse caso, vamos chamar lookup recursivamente com os seguintes dados lookup(Key, Larger).
E é isso!
Com ZERO instruções sobre COMO fazer, nós temos uma função super simples, declarativa e completa, que retorna um valor de uma árvore binária! Isso é absolutamente incrível e surpreendente <3.
Espero que tenha gostado!
Abraço! :)
- Código extraído do capítulo 7 - Recursão, seção "Mais que listas", do livro Learn You Some Erlang for Great Good. LINK