DEV Community

Willian Frantz
Willian Frantz

Posted on

Mas e os loops em Elixir?

Se você está vindo de uma linguagem de paradigma imperativo, orientada a objetos, muito provavelmente você vai esbarrar nessa pergunta do título.

Pois bem, Elixir não possui esse termo em seu vocabulário. Apesar de ser possível iterar sobre uma lista de elementos utilizando o for:

iex> for n <- [1, 2, 3, 4], do: n * n
[1, 4, 9, 16]
Enter fullscreen mode Exit fullscreen mode

Isso não significa que o Elixir possui loops, esse for nada mais é do que uma chamada nativa ao List Comprehensions do Erlang.

Curioso né? Como fazer para lidar com uma coleção de itens então?

Há 2 maneiras de trabalhar com este tipo de problema, sendo elas:

  1. High Order Functions (map, reduce, filter, find, etc...)
  2. Recursividade

High Order Functions

É muito comum se deparar com uma situação onde você tem uma lista de elementos e precisa manipular os dados dela.

E para isso podemos utilizar funções como map, reduce, filter, etc.

Digamos que você precise multiplicar todos os elementos da sua lista por 2, isso deveria ser um problema trivial, certo?

A implementação desse problema em js utilizando uma estrutura de repetição (loop) seria mais ou menos assim:

const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
for (let i = 0; i < list.length; i++) {
  list[i] = list[i] * 2;
}

> list
> [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
Enter fullscreen mode Exit fullscreen mode

Em Elixir é possível resolver isso com map/2:

iex> list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
iex> sum = fn x -> x * 2 end
iex> Enum.map(list, sum)
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
Enter fullscreen mode Exit fullscreen mode

Comparando os exemplos acima, diferente da estrutura de repetição, com o map/2 não é necessário definir nada além da fórmula para mapear os dados da minha lista, onde a fórmula é x -> x * 2.

O próprio map/2 faz o resto do trabalho aplicando a fórmula pra cada elemento da nossa lista, e gerando uma nova lista ao final da execução.

Segue o mesmo conceito para as demais funções, como:

  • map/2 manipula os elementos e gera uma nova lista
  • filter/2 filtra os elementos e gera uma nova lista
  • reduce/2 manipula os elementos acumulando seus resultados anteriores

Existem diversos tipos de High Order Functions disponíveis no Elixir, feitas para facilitar a sua vida na hora de resolver problemas sejam eles triviais ou não.

Recursividade

Mesmo que você seja uma pessoa de linguagens imperativas, o termo recursividade ainda é algo familiar!

E o que é recursividade? É uma forma de iterar sob listas (ou não), onde a função chama ela própria até atingir uma condição de parada.

Um exemplo muito conhecido sobre recursividade, é o cálculo fatorial de um número, onde 4! = 4 x 3 x 2 x 1 = 24

Destrinchando esse cálculo, teríamos algo semelhante a:

4! = 3! * 4
   = 2! * 3
   = 1! * 2
   = 1
Enter fullscreen mode Exit fullscreen mode

Considerando o exemplo acima, a condição de parada para essa execução é o valor 1. Quando a função fatorial receber como argumento o valor 1, ela deverá retornar 1 e as outras execuções devem se basear neste valor, exemplo:

4! = (6) * 4 = 24
   = (2) * 3
   = (1) * 2
   = 1
Enter fullscreen mode Exit fullscreen mode

Em parênteses: resultado da chamada fatorial anterior.

A implementação em JS:

fact = (val) => {
  if (val == 1) return 1;

  return fact(val - 1) * val;
};
Enter fullscreen mode Exit fullscreen mode

Essa mesma função em Elixir fica assim:

def fact(1), do: 1
def fact(a), do: fact(a - 1) * a
Enter fullscreen mode Exit fullscreen mode

Nota-se que na chamada recursiva, a função fact/1 chama a si mesma passando o argumento - 1, e quando essa função é chamada com o valor 1, ela retorna somente o valor 1 e encerra sua execução em cadeia.

Vamos analisar mais de perto essa chamada do fact/1:

# Considere que estamos chamando fatorial com o argumento 4 (4!)

fact(4) -> fact(4 - 1) * 4 # Esse será o retorno
# Ele estará chamando fact(3) e multiplicando por 4.
# E assim sucessivamente...

fact(3) -> fact(3 - 1) * 3
fact(2) -> fact(2 - 1) * 2
fact(1) -> 1

# Essa abordagem gera uma cadeia de chamadas que precisam ser resolvidas.
# Quando a chamada em cadeia chega na nossa condição de parada (1)
# O processador começa a desencadear essas chamadas que empilhamos.
# Seguindo assim:

fact(1) -> 1
fact(2) -> (1) * 2 -> 2
fact(3) -> (2) * 3 -> 6
fact(4) -> (6) * 4 -> 24
Enter fullscreen mode Exit fullscreen mode

Implementar uma função fatorial utilizando recursividade é bem simples, né? Mas se formos considerar a explicação que acabamos de ver, isso pode se tornar um problema?

Imagine que temos uma função que precisará iterar milhares de vezes para resolver um determinado problema, precisaremos empilhar várias chamadas não-resolvidas na nossa pilha de chamadas, e isso poderá estourar o limite da pilha.

Para esse problema em específico, há uma solução chamada Tail Call Optimization (ou TCO). Com TCO é possível eliminar essas chamadas não-resolvidas que uma função recursiva costuma criar.

O pulo do gato quando aplicamos Tail Call Optimization em uma função recursiva é que essa função saiba o valor processado em todas as suas chamadas, sendo assim, ela não depende do desencadeamento para encontrar o valor final de sua execução.

E como podemos fazer isso? Segue o exemplo de uma chamada sem TCO:

# nossa condição de parada
def fact(1), do: 1

# função fatorial recursiva
def fact(val), do: fact(val - 1) * val
Enter fullscreen mode Exit fullscreen mode

com TCO:

def fact(val), do: fact(val - 1, val)

# nossa condição de parada
defp fact(1, res), do: res

# função fatorial recursiva
defp fact(val, res), do: fact(val - 1, res * val)
Enter fullscreen mode Exit fullscreen mode

A grande diferença, é que na função fatorial com TCO, ela sabe exatamente o valor da sua execução.

fact(4) -> fact(4 - 1, 4)
fact(3, 4) -> fact(3 - 1, (4 * 3)) -> fact(2, 12)
fact(2, 12) -> fact(2 - 1, (12 * 2)) -> fact(1, 24)
fact(1, 24) -> 24
Enter fullscreen mode Exit fullscreen mode

Portanto, quando a nossa função chega na sua condição de parada, não é necessário desencadear todas as chamadas anteriores e seus respectivos cálculos. Ela só precisa retornar seu valor final (24) para a função que originou a sua chamada fact(4).

Fato curioso: Por padrão, Elixir/Erlang implementam Tail Call Optimization, por isso a utilização de recursividade é algo muito comum e encorajada! Inclusive as High Order Functions são implementadas através de recursividade, no final das contas.


Conclusão

Elixir é amor, Erlang é vida.

thats all

Discussion (4)

Collapse
adolfont profile image
Adolfo Neto • Edited

Oi Willian, poderia explicar melhor o que você quis dizer com "Por padrão, Elixir/Erlang implementam Tail Call Optimization, por isso a utilização de recursividade é algo muito comum e encorajada! Inclusive as High Order Functions são implementadas através de recursividade, no final das contas."?

Não preciso escrever minhas funções com TCO? Erlang converte elas para TCO ao compilar?

Collapse
wlsf profile image
Willian Frantz Author

Boa noite professor, como comentei com você, seria mais ou menos isso mesmo. Erlang enquanto linguagem funcional, tem uma forte base de interpretação de funções recursivas para conseguir entender quando eliminar as ultimas chamadas (jumps) de suas execuções.

Com isso, geralmente funções recursivas irão ocupar o mesmo tanto de memória que uma função com TCO. O que elimina o problema citado no texto, de estourar a pilha de chamadas.

Collapse
adolfont profile image
Adolfo Neto

Fiz um vídeo comentando este texto e algumas outras coisas relacionadas: youtube.com/watch?v=XLriwylg3qI

Collapse
jpbrab0 profile image
João Pedro Resende

Parabéns pelo artigo Will!