# Need help trying to map procedural to functional

ello!

I’m trying to learn some Elixir by doing some exercises. Currently, I’m trying to understand how to write the equivalent of a fibonacci with a cache. At the moment, I came up with the following implementation:

``````defmodule M do
@moduledoc false
def main do
cache = spawn(M, :fib_cache, [%{}])
IO.puts(fib(10, cache))
end

def fib(n, cache_pid) do
case n do
1 -> 0
2 -> 1
3 -> 1
_ ->
send(cache_pid, {self(), :fetch, n})
if value != nil do
value
end
end
num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
send(cache_pid, {self(), :store, n, num})
{:ok} ->
num
end
end
end

def fib_cache(state) do
{from, :store, n, m} ->
IO.inspect(state)
send(from, {:ok})
fib_cache(Map.put(state, n, m))
{from, :fetch, n} ->
fib_cache(state)
end
end
end
``````

What is worrying me is the log that it prints when I run it:

``````
iex(3)> M.main
%{}
%{4 => 2}
%{4 => 2, 5 => 3}
%{4 => 2, 5 => 3}
%{4 => 2, 5 => 3, 6 => 5}
%{4 => 2, 5 => 3, 6 => 5}
%{4 => 2, 5 => 3, 6 => 5}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
%{4 => 2, 5 => 3, 6 => 5, 7 => 8, 8 => 13, 9 => 21}
34
:ok

``````

In short, the state gets printed multiple times when in a equivalent implementation in a procedural language it would print once. My question is: what am I missing here? Are the functions executed in parallel when I create the num variable? Shouldn’t it fill the state with all the values from 1 to 10 and fib(n-2) be a O(1) operation?

Looking forward to hearing from you

The problem is that the value returned from `fetch` doesn’t get used for anything, so the calculation continues despite getting a value from the cache.

You’d want to pull the calculation into an `else`:

``````      send(cache_pid, {self(), :fetch, n})
if value != nil do
value
else      # <= CHANGE STARTS HERE
num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
send(cache_pid, {self(), :store, n, num})
{:ok} ->
num
end
end
end
``````

Thanks a lot for your response! I’m just wondering, why is it that value is not used? Is it because elixir does not accept early returns?

How can I systematically find and solve these issues, coming from a procedural background? The pattern I’m seeing is an if without an else. Is this accurate?

Also, how do I avoid the Hadouken code that is forming? The depth of the context is getting somewhat overwhelming with the receive > else > receive. For such a pet example, it is not an issue, but for production code this will be an issue. I ask this because most of the time I leverage early returns to avoid having deep context in my code - therefore I need to understand what would be the Elixir way of doing this.

Any guidance would be invaluable. Thanks in advance

Even in a language (for instance, Ruby) where early returns were supported, you’d need to say `return(value)` or similar.

It’s technically possible to do early-return-ish things in Elixir with `catch` and `throw` but the preferred alternative is to write code that doesn’t need them.

Not specifically the problem - the root cause is that there’s no early-return.

Here’s another version with slightly less nesting:

``````      send(cache_pid, {self(), :fetch, n})

value =
end

if is_nil(value) do
num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
send(cache_pid, {self(), :store, n, num})
{:ok} ->
num
end
else
value
end
``````

Functions are cheap. Use lots.

For instance, this version mostly just moves code around:

``````  def fib(n, cache_pid) do
case n do
1 -> 0
2 -> 1
3 -> 1
_ ->
case get_cached(cache_pid, n) do
nil -> compute(cache_pid, n)
cached -> cached
end
end
end

defp get_cached(cache_pid, n) do
send(cache_pid, {self(), :fetch, n})
end
end

defp compute(cache_pid, n) do
num = fib(n-1, cache_pid) + fib(n - 2, cache_pid)
send(cache_pid, {self(), :store, n, num})
{:ok} ->
num
end
end
``````

Or you can get fancier with an anonymous function:

``````  def fib(n, cache_pid) do
case n do
1 -> 0
2 -> 1
3 -> 1
_ -> compute_cached(cache_pid, n, fn i -> fib(i-1, cache_pid) + fib(i-2, cache_pid) end)
end
end

defp compute_cached(cache_pid, n, fun) do
case get_cached(cache_pid, n) do
nil ->
num = fun.(n)
store_cache(cache_pid, n, num)
num
cached -> cached
end
end

defp get_cached(cache_pid, n) do
send(cache_pid, {self(), :fetch, n})
end
end

defp store_cache(cache_pid, n, num) do
send(cache_pid, {self(), :store, n, num})
{:ok} ->
num
end
end
``````

One nice property of this arrangement is that the caching machinery is now uninvolved in the specifics of Fibonacci-ness.

Most of the time that pattern is wrapped up into higher-level functions. For instance, here’s the code from the previous version but with the `fib_cache` cache replaced with an `Agent` from stdlib:

``````defmodule M do
@moduledoc false
def main do
{:ok, cache} = Agent.start_link(fn -> %{} end)
IO.puts(fib(10, cache))
end

def fib(n, cache_pid) do
case n do
1 -> 0
2 -> 1
3 -> 1
_ ->
compute_cached(cache_pid, n, fn i ->
fib(i-1, cache_pid) + fib(i-2, cache_pid)
end)
end
end

defp compute_cached(cache_pid, n, fun) do
case get_cached(cache_pid, n) do
value when is_integer(value) -> value
nil ->
num = fun.(n)
store_cache(cache_pid, n, num)
num
end
end

defp get_cached(cache_pid, n) do
Agent.get(cache_pid, fn s ->
Map.get(s, n)
end)
end

defp store_cache(cache_pid, n, num) do
Agent.update(cache_pid, fn s ->
IO.inspect(s)
Map.put(s, n, num)
end)
end
end
``````

The custom message formats (`{:fetch, ...}`, `{:reply, ...}` etc) are now handled by wrapper functions like `Agent.get` and `Agent.update`.

4 Likes

I appreciate the help. I just thought at the example that simply writing `value` in the body of the if would return the value. Thanks a lot for the patience and the snippets.

1 Like