Explanation of using the Y-Combinator and wrapping functions in Elixir to write recursive functions and wrap them with extra functionality

YCombinator.ex

defmodule YCombinator do
  @moduledoc """
  Some functions explaining the Y-Combinator.

  Can definitely be improved upon, but this is as much as time allowed me this evening.
  """


  def factorial(n) do
    y_combinator(&almost_factorial/1).(n)
  end

  def debug_factorial(n) do
    y_combinator(print_wrapper(&almost_factorial/1)).(n)
  end

  def memo_factorial(n) do
    y_combinator(memoize_wrapper(&almost_factorial/1)).(n)
  end

  def memo_debug_factorial(n) do
    y_combinator(memoize_wrapper(print_wrapper(&almost_factorial/1))).(n)
  end

  def debug_memo_factorial(n) do
    y_combinator(print_wrapper(memoize_wrapper(&almost_factorial/1))).(n)
  end


  @doc """
  Performs the logic of the mathematical 'Factorial' function,
  but rather than recursing directly,
  calls `rec_fun` that was passed in instead.

  Giving this function to the y-combinator makes it recursive.
  """
  def almost_factorial(rec_fun) do
    fn n ->
      if n < 2 do
        1
      else
        n * rec_fun.(n - 1)
      end
    end
  end

  def fibonacci(n) do
    y_combinator(&almost_fibonacci/1).(n)
  end

  def debug_fibonacci(n) do
    y_combinator(print_wrapper(&almost_fibonacci/1)).(n)
  end

  def memo_fibonacci(n) do
    y_combinator(memoize_wrapper(&almost_fibonacci/1)).(n)
  end

  def memo_debug_fibonacci(n) do
    y_combinator(memoize_wrapper(print_wrapper(&almost_fibonacci/1))).(n)
  end

  def debug_memo_fibonacci(n) do
    y_combinator(print_wrapper(memoize_wrapper(&almost_fibonacci/1))).(n)
  end

  @doc """
  Performs the logic of the mathematical 'Fibonacci' function,
  but rather than recursing directly,
  calls `rec_fun` that was passed in instead.

  Giving this function to the y-combinator makes it recursive.
  """
  def almost_fibonacci(rec_fun) do
    fn n ->
      if n < 2 do
        1
      else
        rec_fun.(n - 2) + rec_fun.(n - 1)
      end
    end
  end

  @doc """
  A crazy function, that has the semantics that y_combinator(f) === f.(y_combinator(f))

  which means that function `f` is called with a recursive version of itself as argument,
  so calling this function-passed-as-argument in the 'recursive case' of a problem will
  make a function magically recursive!
  
  For the really crazy, you can define the function without using explicit recursion as:
  
      call_with_itself(fn y -> f.(fn arg -> call_with_itself(y).(arg) end) end)
  """
  def y_combinator(f) do
    f.(fn x -> y_combinator(f).(x) end)  
  end

  @doc """
  Calls single-argument function `fun` with itself as argument.

  Also known as the 'U-combinator' (U f = f f)
  """
  def call_with_itself(fun) do
    fun.(fun)
  end

  @doc """
  Wraps a function to print its output after returning from its recursive call.
  """
  def print_wrapper(fun) do
    fn recfun ->
      fn input ->
        result = fun.(recfun).(input)
        IO.inspect("For input #{inspect input} we get: #{inspect result}")
        result
      end
    end
  end

  @doc """
  Wraps a function with a memoization layer.
  The inner function will only be called once its input is different than before.

  Do note that it uses a mutable store (right now an Agent) to keep track of its caching.
  I'm not currently sure if there is a way to perform this threading directly
  in an immutable language like Elixir.

  (Also, the agent currently does not close after the memoization call was done,
  so we are essentially leaking memory. And a new one is started during every call to the function,
   rather than sharing results between function calls =/.)
  """
  def memoize_wrapper(fun) do
    {:ok, pid} = __MODULE__.MemoizationAgent.start_link(fn -> {} end)
    fn recfun ->
      fn input ->
        case __MODULE__.MemoizationAgent.lookup(pid, input) do
          {:ok, val} -> val
          {:error, _} ->
            val = fun.(recfun).(input)
            __MODULE__.MemoizationAgent.store(pid, input, val)
            val
        end
      end
    end
  end

  defmodule MemoizationAgent do
    use Agent

    def start_link(_) do
      Agent.start_link(fn -> Map.new end)
    end

    def lookup(pid, input) do
      Agent.get(pid, fn cache ->
        if Map.has_key?(cache, input) do
          {:ok, cache[input]}
        else
          {:error, :unexistent}
        end
      end)
    end

    def store(pid, input, output) do
      Agent.update(pid, fn cache ->
        Map.put(cache, input, output)
      end)
    end
  end

end