Recursive anonymous functions in Elixir

🇵🇹 Versão em português desse texto aqui! 🇧🇷

Some time ago I tried to create a recursive anonymous function in Elixir because I was inside iex and was feeling lazy about creating a module inside the repl. My first attempt was something like this:

# Anonymous recursive naive factorial
fact = fn
  0 -> 1
  n -> n * fact.(n-1)
end

Side note: Yes, you can define multiple clauses for anonymous functions!

This, of course, does not work, because fact/1 is not yet defined when it is called inside the function body.

I really do not remember why I needed a recursive anonymous function, but early this week I realized what I had to do in order to make it work. All we have to do is make sure the recursive function exists at the moment it is called, right?

So what if the anonymous function receives another function as an argument, and this received function is what is going to make the recursive call?

Now Elixir could not complain about the function not being defined, because I was supplied as an argument, which could be anything:

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

Well, but what is this recur function?

It could very well be fact itself! We just have to pass it when calling:

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

# Pass fact to itself, so it will be "recur" inside the function body
fact.(4, fact)

Of course this will raise an exception, because now fact has an arity of 2, and recur is being called with only one argument. Remember that recur is in fact fact! No pun intended.

To solve this, all we have to do is to call recur passing recur to itself, like this:

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

fact.(4, fact)

#=> 24

It works with tail recursion as well, of course. All you have to do is manage the parameters and returns correctly.

Nice, can I use it in an Enum.map or any other higher order function?

Well, only if we are careful.

If we write this:

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

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

Then Enum.map/2 will try to invoke fact with one argument only, raising an exception.

One way to solve this would be to wrap it into another function:

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]

Another way would be to define fact with a nicer interface.

The fact function could just receive an argument and then define the recursive anonymous function inside itself, and then call the just defined anonymous function passing it as the argument.

Something like this:

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]

Now we have a recursive anonymous function that works as expected. If I want to know the factorial of a number, I just have to pass the number to it, which is what Enum.map will try to do.

Even inline definition of this anonymous function will work:

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]

And tail recursive:

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

  # Remember to correctly set the accumulator's initial value. Here it is 1
  do_fact.(n, 1, do_fact)
end)

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

Having a nicer interface is not only good to use it as arguments of higher order functions, it is also nicer for us to invoke it normally, of course:

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

# No need to pass the accumulator nor the function itself
fact.(4)
#=> 24

Now if I want to know the factorial of 4, I just have to call the function fact/1 with 4 as an argument, no weird passing itself around manually on function calls.

Nice, but is this useful?

To be sincere, I do not know.

For starters, it is not ilegal to define a module inside the repl, so the "I'm lazy in iex" scenario is not all that meaningful. I mean, I had to write so much extra content just to create this anonymous recursive function that simply writing defmodule M do ... end might be easier and faster.

Another situation where we could use this would be in normal elixir files where we have some Enum functions or other higher order functions work, but then we would probably already be inside a module, where we could define a named private function to do this work and give it a meaningful name while we're at this, culminating in a better, more readable code than the "solution" with the crazy recursive anonymous functions.

But hey, even if it is not all that useful, at least it is always nice to think about functions and recursion, right?

And it was also very fun to write this post! 😁

That's it for today. Thanks for reading, and have a nice day! (: