Skip to content

Instantly share code, notes, and snippets.

@pragdave
Created May 16, 2014 03:17
Show Gist options
  • Save pragdave/644e39ee752c1f01bea7 to your computer and use it in GitHub Desktop.
Save pragdave/644e39ee752c1f01bea7 to your computer and use it in GitHub Desktop.
defmodule FibAgent do
defstruct cache: nil, highest_n: 0
def start_link do
initial_cache = Enum.into([ {0, 0}, {1, 1}], HashDict.new)
state = %__MODULE__{cache: initial_cache, highest_n: 1}
Agent.start_link(fn -> state end, name: __MODULE__)
end
def fib(n) do
Agent.update(__MODULE__, &fill_cache_up_to(&1, n))
Agent.get(__MODULE__, fn state -> Dict.get(state.cache, n) end)
end
# If the cache is already full at least as far as n, no action is required
def fill_cache_up_to(state = %__MODULE__{highest_n: highest_n}, n)
when n <= highest_n,
do: state
# otherwise fill in entries from highest+1 to n
def fill_cache_up_to(%__MODULE__{cache: cache, highest_n: highest_n}, n) do
next = highest_n + 1
fib1 = Dict.get(cache, next - 2)
fib2 = Dict.get(cache, next - 1)
cache = Dict.put cache, next, fib1 + fib2
fill_cache_up_to(%__MODULE__{cache: cache, highest_n: next}, n)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment