Funções recursivas e anônimas em Elixir

🏴󠁧󠁢󠁥󠁮󠁧󠁿 English version of this text here!

Um tempo atrás, eu tentei criar uma função recursiva e anônima em Elixir porque eu estava dentro do iex e estava com preguiça de criar um módulo dentro do repl. Minha primeira tentativa foi algo assim:

# Fatorial ingênuo, anônimo e recursivo
fact = fn
  0 -> 1
  n -> n * fact.(n-1)
end

OBS: Sim, é possível definir múltiplas cláusulas para funções anônimas!

É claro que isso não funcionou, porque fact/1 ainda não está definida no momento em que é chamada dentro do corpo da função.

Eu realmente não lembro por que eu precisava de uma função anônima e recursiva, mas no começo dessa semana eu percebi o que que eu tinha que fazer para que funcionasse. Tudo o que temos que fazer é assegurar-nos que a função existe no momento em que é chamada, certo?

E se a função anônima recebesse, então, outra função como argumento, e essa função recebida fosse a que faz a chamada recursiva?

Agora o Elixir não poderia reclamar da função não estar definida, porque ela foi fornecida via um argumento, que poderia ser qualquer coisa:

fact = fn
  0, _ -> 1
  n, recur -> n * recur.(n-1)
end

Bom, mas o que é essa função recur?

Ela poderia muito bem ser a própria fact! Somente temos que passá-la quanto a estivermos chamando:

fact = fn
  0, _ -> 1
  n, recur -> n * recur.(n-1)
end

# Passe fact para si mesma, para que ela seja "recur" dentro do corpo da função
fact.(4, fact)

É claro que isso vai lançar uma exceção, pois agora fact tem uma aridade de 2, e recur está sendo chamada com apenas um argumento. Lembre-se que recur é de "facto" fact! Sim, tentei fazer um trocadilho.

Para resolver isso, tudo que temos que fazer é chamar recur passando recur para si mesmo, assim:

fact = fn
  0, _ -> 1
  n, recur -> n * recur.(n-1, recur)
end

fact.(4, fact)

#=> 24

Também funciona com recursão de cauda, é claro. Tudo que teríamos que fazer é gerenciar os parâmetros e retornos corretamente.

Legal, posso usar isso num Enum.map ou alguma outra função de ordem superior?

Bom, somente se tomarmos cuidado.

Se escrevermos isso:

fact = fn
  0, _ -> 1
  n, recur -> n * recur.(n-1, recur)
end

Enum.map([1,2,3,4], fact)

Então Enum.map/2 tentará invocar fact com um argumento apenas, lançando uma exceção.

Uma maneira de resolver isso seria encapsulando-a dentro de uma outra função:

fact = fn
  0, _ -> 1
  n, recur -> n * recur.(n-1, recur)
end

Enum.map([1,2,3,4], &(fact.(&1, fact)))

#=> [1, 2, 6, 24]

Outra maneira seria definir fact com uma interface mais legal.

A função fact poderia simplesmente receber um argumento e daí definir a função anônima e recursiva dentro de si mesma, e daí chamar a função anônima recém definida passando a mesma como argumento.

Seria algo assim:

fact = fn n ->
  do_fact = fn
    0, _ -> 1
    n, recur -> n * recur.(n-1, recur)
  end

  do_fact.(n, do_fact)
end

Enum.map([1,2,3,4], fact)

#=> [1, 2, 6, 24]

Agora nós temos uma função recursiva e anônima que funciona como o esperado. Se eu quiser saber o fatorial de um número, apenas tenho que passar o número para a função, que é exatamente o que Enum.map tentará fazer.

Até definir na mesma linha essa função anônima funcionará:

Enum.map([1,2,3,4], fn n ->
  do_fact = fn
    0, _ -> 1
    n, recur -> n * recur.(n-1, recur)
  end

  do_fact.(n, do_fact)
end)

#=> [1, 2, 6, 24]

E recursiva de cauda:

Enum.map([1,2,3,4], fn n ->
  do_fact = fn
    0, acc, _ -> acc
    n, acc, recur -> recur.(n-1, n*acc, recur)
  end

  # Lembre-se de definir corretamente o valor inicial do acumulador. Aqui ele é 1
  do_fact.(n, 1, do_fact)
end)

#=> [1, 2, 6, 24]

Ter uma interface mais legal não é bom somente para usá-la como argumentos de uma função de order superior, também é mais legal para nós invocarmos essa função, é claro:

fact = fn n ->
  do_fact = fn
    0, acc, _ -> 1
    n, acc, recur -> recur.(n-1, n*acc, recur)
  end

  do_fact.(n, 1, do_fact)
end

# Não há necessidade de passar nem o acumulador nem a própria função
fact.(4)
#=> 24

Agora se eu quiser saber o fatorial de 4, tenho que apenas chamar a função fact/1 com 4 como argumento, sem ter essas coisas estranhas de passar a própria função por aí manualmente na chamada.

Legal, mas isso é útil?

Para ser sincero, eu não sei.

Para começo de conversa, não é ilegal definir um módulo dentro do repl, então o cenário de "Estou com preguiça dentro do iex" não é tão importante assim. Quero dizer, eu tive que escrever tanta coisa a mais só para criar essa função recursiva e anônima que talvez simplesmente escrever defmodule M do ... end seja mais fácil e mais rápido.

Outra situação em que poderíamos usar isso seria em arquivos elixir normais onde temos algums Enums ou outras funções de ordem superior trabalhando, mas daí a gente provavelmente já vai estar dentro de um módulo, onde poderíamos definir uma função privada "com nome" (não anônima) para fazer esse trabalho e já dando um nome significativo a ela, aproveitando que vamos estar ali. Isso vai culminar num código melhor e mais legível do que a "solução" com as funções recursivas e anônimas malucas.

Mas ei, mesmo que isso não seja assim tão útil, pelo menos é sempre legal pensar sobre funções e recursão, certo?

E também foi bem divertido escrever esse post! 😁

É isso por hoje. Obrigado por ler e tenha um bom dia! (: