Julia memo-izing

Question

In Mathematica if you want a function to remember its values, it is syntactically quite painless. For example, here is the standard example - Fibonacci:

fib[1] = 1
fib[2] = 1
fib[n_]:= fib[n] = fib[n-1] + fib[n-2]

Is there some syntactically pleasant way to do this in Julia? Part of what it makes it more involved is the type system - here is an implementation for a single untyped arg:

function memoizeany(func)
    thedict = Dict()
    return (a)-> memoizeanyaux(a, func, thedict)
end

function memoizeanyaux(a, func, thedict)
    if haskey(thedict, a)
        return thedict[a]
    end
    res = func(a)
    thedict[a] =res
    return res
end

Doing this for every type signature seems a little painful, and presumably the most Julia way to do this is with a @memoize macro, but that does not actually answer the question. Surely this has come up before.

Answer 1

When I need to use functions that use persistent memory, I simply create structs and overload the call notation to make them functors. For the example you provide, I would write the Fibonacci sequence as

struct MyFib{T<:Real}
  n::Vector{T}

  function (::Type{MyFib})(::Type{T} = Int) where T
    new{T}([0, 1])
  end

  function (m::MyFib{T})() where T
    result = sum(m.n)
    m.n .= [result, m.n[1]]
    return result
  end
end

m = MyFib()

for n in 1:10
  @show n, m()
end

This way of using structs is generic enough for me to encapsulate anything I need in my computations. Plus, because it is strictly typed using the parameter T, it is efficient, too.

Then, for the above example, you can also use some parametric function and function recursion, that would hopefully benefit from the integer constant propogation in v0.7 to get as efficient as its templated counterpart in C++:

myfib(::Val{0}) = 0
myfib(::Val{1}) = 1

function myfib(::Val{N})::Int where N
  return myfib(Val{N-1}()) + myfib(Val{N-2}())
end

# or, as a single liner, as per crstnbr's comment,
myfib(::Val{N}) where N = myfib(Val{N-1}()) + myfib(Val{N-2}())

# and, with some syntactic sugar, thanks to SalchiPapa,
myfib(n::Int) = myfib(Val{n}())

for n in 1:10
  @show n, myfib(n)
end

I assume the latter one is more friendly for your example, as compared with the Mathematica version. But it is not as generic as the former, and you would be putting some stress on the compiler as it is a compile-time technique.