«tutor»:e4p~basic-processes~fib

00-question.md

If you're up for a challenge…

The classic Fibonacci implementation is

def fib(0), 0
def fib(1), 1
def fib(n), fib(n-1) + fib(n-2)

This has a worst case performance of \( O( 1.6^{n+1} ) \). For large \( n \), this is a big number (20 digits or so long for \( n = 100 \)). This means it is slow, and it burns through stack space at an alarming rate.

However, you can make the function perform in linear time by implementing a simple cache. An Elixir map is a good data structure for this. Initialize it with %{ 0 => 0, 1 => 1 }, and add new values to it as you discover them.

Write a module that implements the cache. It should use an agent, and that agent's state should be the map.

Then write a Fibonacci module that uses this cache.

Try calculating fib(100). If it comes back without crashing your machine, and before the sun has expanded to consume the Earth, then your cache worked...

fib_cache.exs

defmodule Cache do

  @moduledoc """
  We implement a simple key/value cache. State is stored in an Agent, in
  the form of a map.

  The function `lookup` tries to look the value up in the cache, and then
  calls `complete_if_not_found`. This takes two forms. If there was
  no value in the cache, it calls the function passed in by the client
  to supply it, updating the cache at the same time.

  Otherwise, it simply returns the cached value.
  """

  @doc """
  Start the cache, run the supplied function, then stop the cache.
  
  Eventually we'll be able to do better than this.
  """
  
  def run(body) do
    { :ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1 } end)
    result = body.(pid)
    Agent.stop(pid)
    result
  end
 
  def lookup(cache, n, if_not_found) do
    Agent.get(cache, fn map -> map[n] end)
    |> complete_if_not_found(cache, n, if_not_found)
  end

  defp complete_if_not_found(nil, cache, n, if_not_found) do
    if_not_found.()
    |> set(cache, n)
  end

  defp complete_if_not_found(value, _cache, _n, _if_not_found) do
    value
  end
  
  defp set(val, cache, n) do
    Agent.get_and_update(cache, fn map ->
      { val, Map.put(map, n, val)}
    end)
  end
end


defmodule CachedFib do

  def fib(n) do
    Cache.run(fn cache ->
      cached_fib(n, cache)
    end)
  end

  defp cached_fib(n, cache) do
    Cache.lookup(cache, n, fn ->
      cached_fib(n-2, cache) + cached_fib(n-1, cache)
    end)
  end

end

I like @pragdave' s solution, the Agent/Cache is completely hidden from the user.

However, he uses a custom made (and dare I say an also more complicated) cache. (The function name complete_if_not_found is somewhat confusing, the second and last implementation of complete_if_not_found is doing the opposite which is nothing because the value was found!)

Why not use a 'standard Map cache', used in the Agent example in the getting started guide from elixir-lang.org ( see the example pf KV.Bucket ) and combine this with @fahrinh's Fib implementation?

defmodule MapCache do
  use Agent

  def start_link() do
    Agent.start_link(fn -> %{} end)
  end

  def get(bucket, key) do
    Agent.get(bucket, &Map.get(&1, key))
  end

  def put(bucket, key, value) do
    Agent.update(bucket, &Map.put(&1, key, value))
  end
end

defmodule Fib do
   def calc(n) do
    {:ok, cache} = MapCache.start_link()
    result = calc(cache, n)
    Agent.stop(cache)
    result
  end

  defp calc(_cache, 0), do: 0
  defp calc(_cache, 1), do: 1
  defp calc(cache, n) do
    result = MapCache.get(cache, n)
    if is_nil(result) do
      result = calc(cache, n-1) + calc(cache, n-2)
      MapCache.put(cache, n, result)
      result
    else
      result
    end
  end
end

Usage:

iex [19:35 :: 1] > Fib.calc(50)
12586269025
iex [19:35 :: 2] > Fib.calc(100)
354224848179261915075

PS: In this case I find the usage of a good old if statement more acceptable than an implementation like below:

defmodule Fib do
   def calc(n) do
    {:ok, cache} = MapCache.start_link()
    result = calc(cache, n)
    Agent.stop(cache)
    result
  end

  defp calc(_cache, 0), do: 0
  defp calc(_cache, 1), do: 1
  defp calc(cache, n) do
    result = MapCache.get(cache, n)
    show_result(result, cache, n)
  end

  def show_result(nil, cache, n) do
    result = calc(cache, n-1) + calc(cache, n-2)
    MapCache.put(cache, n, result)
    result
  end
  def show_result(result, _cache, _n), do: result
end

Here's my first solution, since it's slightly different from others shared here.

Some thoughts that came to my mind:

1. while generic cache implementations are nice, it seems to make the fib solution more difficult to read (or am I biased?)
2. as other's mentioned,I too did not consider Agent.stop like @pragdave used in his solution
3. I hide cache state behind the public fib function, this makes it impossible to reuse cache between multiple fib(n) runs. @pragdave solution has the same issue
4. is there a clean tail recursive version?

defmodule Fib do
    def fib(n) do
        {:ok, a} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
        fib(a, n)
    end

    defp fib(agent, n) do
        fib(agent, n, Agent.get(agent, &Map.get(&1, n)))
    end

    defp fib(agent, n, nil) do
        v = fib(agent, n - 1) + fib(agent, n - 2)
        Agent.update(agent, &Map.put(&1, n, v))
        v
    end

    defp fib(agent, n, value) do
        value
    end
end

Using the Bucket example I find my implementatio pretty elegant:

defmodule Fibonacci do
  alias Fibonacci.Cache

  def calculate(n) do
    {:ok, cache} = Cache.start_link()
    Cache.put(cache, 0, 0)
    Cache.put(cache, 1, 1)
    cal(n, cache, Cache.get(cache, n))
  end

  defp cal(n, cache, nil) do
    result = cal(n-1, cache, Cache.get(cache, n-1)) + cal(n-2, cache, Cache.get(cache, n-2))
    Cache.put(cache, n, result)
    result
  end

  defp cal(_, _, result) do
    result
  end
end

defmodule Fibonacci.Cache do
    use Agent
    
    def start_link() do
        Agent.start_link(fn -> %{} end)
    end

    def get(bucket, key) do
        Agent.get(bucket, &Map.get(&1, key)) ## fn map -> Map.get(map, key) end)
    end

    def put(bucket, key, value) do
        Agent.update(bucket, &Map.put(&1, key, value))
    end
end

I also left a small comment to better understand the catch operator

Here is a fib calculator of the same complexity with less code.

defmodule Fibonacci do
  def find(n), do: find(n, 0, 1)
  def find(1, _acc1, acc2), do: acc2

  def find(n, acc1, acc2) do
    find(n - 1, acc2, acc1 + acc2)
  end
end

iex> Fibonacci.find(100)
354224848179261915075

iex> Fibonacci.find(150)
9969216677189303386214405760200

Here is my implementation. Fibonacci.Cache is just a wrapper over a map/state. The public api for the Fibonacci module is just Fibonacci.fib(n). Everything else is abstracted away in private functions.

defmodule Fibonacci do
  alias Fibonacci.Cache

  def fib(n) do
    {:ok, agent} = Cache.intialize(fn -> %{0 => 0, 1 => 1} end)
    value = fib(agent, n)
    Agent.stop(agent)
    value
  end

  defp fib(agent, 0) do
    Cache.get(agent, 0)
  end

  defp fib(agent, 1) do
    Cache.get(agent, 1)
  end

  defp fib(agent, n) do
    fib_n_minus_one = fib(agent, n - 1, Cache.has_key?(agent, n - 1))
    fib_n_minus_two = fib(agent, n - 2, Cache.has_key?(agent, n - 2))

    fib_n_minus_one + fib_n_minus_two
  end

  defp fib(agent, n, _is_in_cache = true) do
    Cache.get(agent, n)
  end

  defp fib(agent, n, _is_in_cache = false) do
    Cache.update(agent, n, fib(agent, n))
  end
end

defmodule Fibonacci.Cache do
  def intialize(init_fn) do
    Agent.start_link(init_fn)
  end

  def get(agent, key) do
    Agent.get(agent, fn map -> Map.get(map, key) end)
  end

  def has_key?(agent, key) do
    Agent.get(agent, fn map -> Map.has_key?(map, key) end)
  end

  def update(agent, key, value) do
    Agent.update(agent, fn map -> Map.put(map, key, value) end)
    value
  end
end

and tests too

defmodule FibonacciTest do
  use ExUnit.Case
  doctest Fibonacci

  test "return 0 for 0" do
    assert Fibonacci.fib(0) == 0
  end

  test "return 1 for 1" do
    assert Fibonacci.fib(1) == 1
  end

  test "return 1 for 2" do
    assert Fibonacci.fib(2) == 1
  end

  test "return 2 for 3" do
    assert Fibonacci.fib(3) == 2
  end

  test "return 55 for 10" do
    assert Fibonacci.fib(10) == 55
  end

  test "return 55 for 100" do
    assert Fibonacci.fib(100) == 354_224_848_179_261_915_075
  end
end

My final version

I changed my API after seeing @pragdave's solution with using a lambda in Cache.run/1.
By using the lambda i was able to easily remove the pid aka cache from the Fibonacci API, but still keep the calculation logic I had before.

THX @pragdave for the awesome course so far and also the other solutions which are very inspiring !

fibonacci.exs

defmodule Fibonacci do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n) do
    fib(n - 1) + fib(n - 2)
  end

  def cached_fib(n) do
    Cache.start(fn cache -> calculation(cache, n) end)
  end

  defp calculation(cache, n) do
    cached_fib = Cache.get(cache, n)
    case cached_fib do
      nil ->
        result = calculation(cache, n - 1) + calculation(cache, n - 2)
        Cache.add(cache, n, result)
       _ ->
        cached_fib
    end
  end
end

defmodule Cache do
  def start(lambda) do
    {:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
    result = lambda.(pid)
    Agent.stop(pid)
    result
  end

  def add(pid, key, value) do
    Agent.get_and_update(pid, fn(map) -> {value, Map.put(map, key, value)} end)
  end

  def get(pid, n) do
    result = Agent.get(pid, &(&1))
    result[n]
  end
end

defmodule Cache do
  def new() do
    Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
  end

  def contains(agent, key) do
    Agent.get(agent, fn state -> Map.has_key?(state, key) end)
  end

  def get(agent, key) do
    Agent.get(agent, fn state -> Map.get(state, key) end)
  end

  def insert(agent, key, value) do
    Agent.update(agent, fn state -> Map.put(state, key, value) end)
  end
end

defmodule Fibonacci do
  def fib(n) do
    {:ok, cache} = Cache.new()
    fib_cache(cache, n)
  end

  defp fib_cache(cache, n) do
    case Cache.contains(cache, n) do
      false ->
        result = fib_cache(cache, n - 1) + fib_cache(cache, n - 2)
        Cache.insert(cache, n, result)
        result

      true ->
        Cache.get(cache, n)
    end
  end
end

I have done it without recursion but I do not know if that'd be a problem. Also, don't know if it makes sense to hold the full cache of all numbers if the problem statement asks for the nth Fibbonaci number. My below solution only holds latest two and calculates.
`defmodule Cache do

def start_value do
%{:first => 0, :second => 1}
end

def init() do
Agent.start_link(fn -> start_value end, name: :cache)
end

def init({:error, _}) do
Cache.init
end

def init({:ok, _}) do

end

def get(key) do
Agent.get(:cache, fn(keymap) -> keymap |> Map.get(key) end )
end

def update(key, value) do
Agent.update(:cache, fn(keymap) -> keymap |> Map.put(key, value) end)
end

def reset() do
Agent.update(:cache, fn(keymap) -> start_value end)
end

end

defmodule fibocached do

def fibbonaci(0) do Cache.get(:first) end
def fibbonaci(1) do Cache.get(:second) end

def fibbonaci(n) do
Cache.reset
range = 2..n
|> Enum.map(&step/1)
Cache.get(:second)
end

def step(number) do
first = Cache.get(:first)
Cache.update(:first, Cache.get(:second))
Cache.update(:second, Cache.get(:second) + first)
end

def run(n) do
Cache.init
FiboCached.fibbonaci(n)
end

def print_cache do
IO.puts("First is #{Cache.get(:first)} Second is #{Cache.get(:second)}")
end

end`

Thanks @praddave for the awesome course ! Continuing with further modules with lots of enthusiasm..

My humble version:

I wanted to ensure that the cache process was stoped before returning, thus no creating zombie processes, is that right?

defmodule FibCache do
    def start() do
      Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
    end

    def get(cache) do
      Agent.get(cache, & &1)
    end

    def update(cache, k, v) do
      Agent.update(cache, fn cache -> Map.put(cache, k, v) end)
    end

    def get_and_update(cache, k, v) do
      Agent.get_and_update(cache, fn cache ->
        new_cache = Map.put(cache, k, v)
        {new_cache, new_cache}
      end)
    end

    def stop(cache) do
      Agent.stop(cache)
    end
  end

  defmodule Fibonacci do
    @moduledoc """
     Calculates Fibonacci numbers using the FibCache cache.
    """

    defp cached_fib(cache, n) do
      hit_cache = FibCache.get(cache)[n]

      cond do
        hit_cache != nil ->
          hit_cache

        hit_cache == nil ->
          FibCache.update(cache, n, cached_fib(cache, n - 1) + cached_fib(cache, n - 2))
          FibCache.get(cache)[n]
      end
    end

    def fib(n) do
      {:ok, cache} = FibCache.start()

      result = cache |> cached_fib(n)
      FibCache.stop(cache)
      result
    end
  end

defmodule FibCache do
  def start() do
    Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
  end

  def get_fib(pid, n) do
    state = Agent.get(pid, fn state -> state end)
    Map.get(state, n)
  end

  def update(pid, n, value) do
    Agent.update(pid, fn state -> Map.put(state, n, value) end)
  end
end

defmodule Fib do
  def start() do
    FibCache.start()
  end

  def fib(_pid, 0), do: 0
  def fib(_pid, 1), do: 1

  def fib(pid, n) do
    case FibCache.get_fib(pid, n) do
      nil ->
        answer = fib(pid, n - 1) + fib(pid, n - 2)
        FibCache.update(pid, n, answer)
        answer

      value ->
        value
    end
  end
end

iex> {:ok, pid} = Fib.start
iex> Fib.fib(pid, 100)

A version (the Cache module is straightforward)

defmodule FiboOpt.Compute do

    def fibo(n) do
        {:ok, cacheID} = Cache.start()
         result = find_result(cacheID, n)
         Agent.stop(cacheID)
         result
    end

    defp find_result(cacheID, n) do
        check_value(cacheID, n)
        |> compute_result(cacheID, n)
        |> update_and_get
    end

    defp check_value(pid, n), do: Cache.get(pid, n)

    defp compute_result(_value_not_exists = nil, pid, n) do
        value = find_result(pid, n - 2) + find_result(pid, n - 1)
        {value, pid, n, :update}
    end

    defp compute_result(value, pid, n), do: {value, pid, n, :no_update}

    defp update_and_get({value, pid, n, :update}) do
         Cache.add(pid, n, value)
         value
    end

    defp update_and_get({value, _, _, :no_update}), do: value
end

So after reading i guess ive forgotton to kill the agent, but it does work :)

defmodule Fib do
  def start do
    {:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
    pid
  end

  def fib(n) do
    start()
    |> fib(n)
  end

  def fib(pid, n) do
    Agent.get(pid, fn state -> state[n] end)
    |> return_or_calculate(pid, n)
  end
  
  def return_or_calculate(result, _pid, _n) do
    result
  end

  def return_or_calculate(nil, pid, n) do
    calculated = fib(pid, n - 1) + fib(pid, n - 2)

    Agent.update(pid, fn state ->
      Map.put(state, n, calculated)
    end)

    calculated
  end
end

I don't think it will affect the result, but I believe there's a race condition in that code.

…

On Sun, Oct 13, 2019 at 5:57 AM Rene Weteling ***@***.***> wrote: So after reading i guess ive forgotton to kill the agent, but it does work :) defmodule Fib do def start do {:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end) pid end def fib(n) do start() |> fib(n) end def fib(pid, n) do Agent.get(pid, fn state -> state[n] end) |> return_or_calculate(pid, n) end def return_or_calculate(result, _pid, _n) do result end def return_or_calculate(nil, pid, n) do calculated = fib(pid, n - 1) + fib(pid, n - 2) Agent.update(pid, fn state -> Map.put(state, n, calculated) end) calculated endend — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://gist.github.com/f8c7684b69d235269139bad0a2419273?email_source=notifications&email_token=AAACTGF7H4FD256WH7ACCILQOL5IJA5CNFSM4HQCVAUKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2MWE#gistcomment-3053922>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAACTGAQ4HRWQQLOBGF6H7DQOL5IJANCNFSM4HQCVAUA> .

@pragdave so that would be in in the:

Agent.update(pid, fn state ->
      Map.put(state, n, calculated)
    end)

It should probably be Agent.get_and_update to make it sequential? Like you mentioned it did not affect the result so I didn't notice it.

And I must say, I'm enjoying myself immensely with the course, its funny, insightful and great to do. It has taken me quite some time to start, I was intrigued by the language by your talk in Amsterdam, and now finally started working with Elixir, it's great. Thanks for the course! Can't wait to continue tonight 👍

That's right. It's kinda a big deal, though. Being a language that encourages concurrency, that kind of nontransactional update can cause problems more easily than in most. Thanks for the kind words. Dave

…

On Mon, Oct 14, 2019 at 2:17 AM Rene Weteling ***@***.***> wrote: @pragdave <https://github.com/pragdave> so that would be in in the: Agent.update(pid, fn state -> Map.put(state, n, calculated) end) It should probably be Agent.get_and_update to make it sequential? Like you mentioned it did not affect the result so I didn't notice it. And I must say, I'm enjoying myself immensely with the course, its funny, insightful and great to do. It has taken me quite some time to start, I was intrigued by the language by your talk in Amsterdam, and now finally started working with Elixir, it's great. Thanks for the course! Can't wait to continue tonight 👍 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <https://gist.github.com/f8c7684b69d235269139bad0a2419273?email_source=notifications&email_token=AAACTGA6OKOIGC7ACTBJMSTQOQMJ3A5CNFSM4HQCVAUKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2NXG#gistcomment-3054451>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAACTGAT5H2BPKCFUCL3RO3QOQMJ3ANCNFSM4HQCVAUA> .

My solution just calculates the nth Fibonacci number without providing caching functionality.

defmodule Fib do
  defp init() do
    { :ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1 } end)
    pid
  end

  def calc(n) do
    pid = init()

    Enum.each(2..n, fn x ->
      Agent.update(pid, fn state ->
        Map.put(state, x, state[x-2] + state[x-1])
      end)
    end)

    state = Agent.get(pid, fn x-> x end)
    state[n]
  end
end

My initial version:

defmodule Fib do
  alias Fib.Cache

  def fib(n) do
    {:ok, agent_pid} = Cache.init()
    fib(n, agent_pid)
  end

  defp fib(n, agent_pid) do
    fib_value = Cache.get(agent_pid, n)
    fib(n, agent_pid, fib_value)
  end

  defp fib(n, agent_pid, _fib_value = nil) do
    fib_value = fib(n - 1, agent_pid) + fib(n - 2, agent_pid)
    Cache.put(agent_pid, {n, fib_value})
    fib_value
  end

  defp fib(_n, _agent_pid, fib_value) do
    fib_value
  end
end

defmodule Fib.Cache do
  use Agent

  def init() do
    Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
  end

  def stop(agent_pid) do
    Agent.stop(agent_pid)
  end

  def put(agent_pid, {number, fib_value}) do
    Agent.update(agent_pid, fn map -> Map.put(map, number, fib_value) end)
  end

  def get(agent_pid, number) do
    Agent.get(agent_pid, fn map -> Map.get(map, number) end)
  end
end

I know I should extract cache functions to another module but this is roughly my solution:

defmodule FibonacciWithCache do
  def fib(0), do: 0

  def fib(1), do: 1

  def fib(n) do
    cache_pid = init_cache()
    value = fib(cache_pid, n)
    clean_cache(cache_pid)
    value
  end

  defp fib(cache_pid, 0) do
    get_from_cache(cache_pid, 0)
  end

  defp fib(cache_pid, 1) do
    get_from_cache(cache_pid, 1)
  end

  defp fib(cache_pid, n) do
    calculate_fib_storing_in_cache(cache_pid, n, get_from_cache(cache_pid, n))
  end

  defp calculate_fib_storing_in_cache(cache_pid, n, nil) do
    value = fib(cache_pid, n - 1) + fib(cache_pid, n - 2)
    update_cache_and_get_value(cache_pid, n, value)
  end

  defp calculate_fib_storing_in_cache(_cache_pid, _n, value), do: value

  defp init_cache do
    {:ok, cache_pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
    cache_pid
  end

  defp clean_cache(cache_pid) do
    Agent.stop(cache_pid)
  end

  defp update_cache_and_get_value(cache_pid, n, value) do
    Agent.get_and_update(cache_pid, fn cache_value ->
      {value, Map.merge(cache_value, %{n => value})}
    end)
  end

  defp get_from_cache(cache_pid, n) do
    Agent.get(cache_pid, fn cache_value -> cache_value[n] end)
  end
end

My solution for a Fibonacci with Agent:

fibonacci_cached.exs:

defmodule FibonacciCached do
  def start() do
    Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
  end

  def get(agent, key) do
    state = Agent.get(agent, fn state -> state end)
    Map.get(state, key)
  end

  def add(agent, key, value) do
    Agent.update(agent, fn state -> Map.put(state, key, value) end)
  end

  def print(agent) do
    Agent.get(agent, fn state -> state end)
  end
end

fibonacci.exs:

defmodule Fibonacci do
  def start() do
    FibonacciCached.start()
  end

  def print(agent) do
    FibonacciCached.print(agent)
  end

  def calculate(_agent, 0), do: 0
  def calculate(_agent, 1), do: 1

  def calculate(agent, key) do
    case FibonacciCached.get(agent, key) do
      nil ->
        value = calculate(agent, key-1) + calculate(agent, key-2)
        FibonacciCached.add(agent, key, value)
        value
      cached_value ->
        cached_value
    end
  end
end

call IEx:

$ iex
iex> c "fibonacci_cached.exs"
[FibonacciCached]
iex> c "fibonacci.exs"       
[Fibonacci]
iex> {:ok, agent} = Fibonacci.start()
{:ok, #PID<0.125.0>}
iex> Fibonacci.calculate(agent, 10)
55
iex> Fibonacci.print(agent)        
%{
  0 => 0,
  1 => 1,
  2 => 1,
  3 => 2,
  4 => 3,
  5 => 5,
  6 => 8,
  7 => 13,
  8 => 21,
  9 => 34,
  10 => 55
}

This is kind of a simple solution. First thing I came up with; I need to look over some of the other solutions to see what I missed.

[NB] Guess I missed the point about having a separate module for the cache...

defmodule Fib do

  def find(0), do: 0
  def find(1), do: 1
  def find(2), do: 1

  def find(count)  do

    {:ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1} end)
    for _n <- 1..div(count, 2), do: update(pid)
    Agent.get(pid, fn map -> map end)
    |> pick(count)

  end

  def pick(map,count) when rem(count,2) == 0, do: map[0]

  def pick(map,_), do: map[1]

  def update(pid) do
    Agent.update(pid, fn map -> %{map | 0 => (map[0] + map[1])} end)
    Agent.update(pid, fn map -> %{map | 1 => (map[0] + map[1])} end)
  end
end

iex(7)> Fib.find 100
354224848179261915075
iex(8)> Fib.find 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
iex(9)> Fib.find 10000
336447648764317832666216120051075433103021484606800639065647699746800814421666623681555955136337340255820... . . .
642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
iex(110)>

My first solution used an externally exposed PID. After stealing the run(body) portion of @pragdave's solution that hides the PID, here's where I arrived:

fibonacci.ex:

defmodule Fibonacci do
  def fib(pid, n) do
    state = Agent.get(pid, fn state -> state end)
    cond do
      state[n] -> state[n]
      true ->
        result = fib(pid, n-1) + fib(pid, n-2)
        Agent.update(pid, fn state -> Map.put(state, n, result) end)
        result
    end
  end

  def cached_fib(n) do
    FibCache.run(fn pid -> fib(pid, n) end)
  end

end

cache.ex:

defmodule FibCache do
  def run(body) do
    {:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
    result = body.(pid)
    Agent.stop(pid)
    result
  end
end

I find this a lot more readable, albeit with the use of cond.

@pragdave @reneweteling

Could you explain why there's a race race condition with Agent.update() vs none with Agent.get_and_update()?

That's right. It's kinda a big deal, though. Being a language that encourages concurrency, that kind of nontransactional update can cause problems more easily than in most. Thanks for the kind words. Dave
…
On Mon, Oct 14, 2019 at 2:17 AM Rene Weteling @.***> wrote: @pragdave https://github.com/pragdave so that would be in in the: Agent.update(pid, fn state -> Map.put(state, n, calculated) end) It should probably be Agent.get_and_update to make it sequential? Like you mentioned it did not affect the result so I didn't notice it. And I must say, I'm enjoying myself immensely with the course, its funny, insightful and great to do. It has taken me quite some time to start, I was intrigued by the language by your talk in Amsterdam, and now finally started working with Elixir, it's great. Thanks for the course! Can't wait to continue tonight 👍 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://gist.github.com/f8c7684b69d235269139bad0a2419273?email_source=notifications&email_token=AAACTGA6OKOIGC7ACTBJMSTQOQMJ3A5CNFSM4HQCVAUKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2NXG#gistcomment-3054451, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAACTGAT5H2BPKCFUCL3RO3QOQMJ3ANCNFSM4HQCVAUA .

Using || can remove all the explicit testing against nil, and it's very convenient having your update function return the new value.

defmodule Cache do

  def start(initial_map = %{}) do
    {:ok, pid } = Agent.start_link(fn -> initial_map end)
    pid
  end

  def put(pid, key, value) do
    Agent.update(pid, &Map.put(&1, key, value))
    value
  end

  def get(pid, key) do
    Agent.get(pid, &Map.get(&1, key))
  end

end

defmodule FibCache do

  def fib(n) do
    Cache.start(%{ 0 => 0, 1 => 1 })
    |> fib_iter(n)
  end

  defp fib_iter(cache, n) do
    Cache.get(cache, n) ||
      Cache.put(cache, n, fib_iter(cache, n-1) + fib_iter(cache, n-2))
  end

end