@nolyoi 23 September 2020 more from that month

Recursion in Elixir

As Elixir is a purely functional language, it doesn’t have loops. Instead, it uses a wide variety of recursive functions to achieve the same or better results. Below is an example of a list and calculating it's length. This shows how recursive functions can be used to work like a loop. **Tail Call Optimization** A traditional function stack looks like this, with each member of the list becoming another function on the stack: ┌────────────────────────┐ │ length([1, 2, 3, 4], 0)│ <── Each member of the list ├────────────────────────┤ becomes a function on │ length([2, 3, 4], 1) │ the stack ├────────────────────────┤ │ length([3, 4], 2) │ ├────────────────────────┤ │ length([4], 3) │ ├────────────────────────┤ │ length([], 4) │ └────────────────────────┘ A tail call optimized function stack, like that used in Elixir, looks like this: ┌────────────────────────┐ ┌────────────────────────┐ │ length([1, 2, 3, 4], 0)│ <──── │ length([2, 3, 4], 1) │ └────────────────────────┘ ├────────────────────────┤ │ length([3, 4], 2) │ ├────────────────────────┤ │ length([4], 3) │ ├────────────────────────┤ │ length([], 4) │ └────────────────────────┘ Function calls on the stack are replaced, so there is only one function on the stack at a time. **Requirements for Tail Call Optimization** In order to be tail call optimized, a function must call itself as the last operation. This is not a proper tail call: def join([h|t]) do h <> " " <> join(t) end But this is: def join([h|t], string) do string = string <> " " <> h join(t, string) end So, now let's look at some examples of a list (MyList) and calling different recursive functions that allow us to work with the list's data. **MyList.length/1** defmodule MyList do def length(list) do length(list, 0) end defp length([], count) do count end defp length([_|t], count) do length(t, count + 1) end end **MyList.each/2** defmodule MyList do def each([], _fun) do :ok end def each([h|t], fun) do fun.(h) each(t, fun) end end Usage: MyList.each [1, 5, 12], fn(num) -> IO.puts(num) end # 1 # 5 # 12 # => :ok **MyList.map/2** defmodule MyList do def map(list, fun) do do_map(list, fun, []) end defp do_map([], _fun, acc) do :lists.reverse(acc) end defp do_map([h|t], fun, acc) do result = fun.(h) acc = [result | acc] do_map(t, fun, acc) end end The final do_map clause could also be shortened like this: defp do_map([h|t], fun, acc) do do_map(t, fun, [fun.(h) | acc]) end Usage: list = [ {"Nolan", 30}, {"Alex", 32} ] MyList.map list, fn({name, _age}) -> name end # => ["Nolan", "Alex"]