Skip to content

Instantly share code, notes, and snippets.

@Qqwy

Qqwy/YCombinator.ex

Last active Oct 21, 2018
Embed
What would you like to do?
Explanation of using the Y-Combinator and wrapping functions in Elixir to write recursive functions and wrap them with extra functionality
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment