Design: memoizing functions with composite type arguments



Hi, I have been troubled by a specific design problem for a few days. The problem is as follows:

I have a function f

struct foo

function f(x::foo)

Since f is fairly expensive, I want to memoize its results using Dict. However, changing will not change its hash. In this sense, function f may return wrong results because of memoization.

Any suggestions to resolve this problem?

Since can be very large, I do not want to memoize the results with as keys. The best approach I can think of is to make immutable, which I don’t know how to do.


You can either

  1. Write a method for Base.hash that uses data. The default just falls back to object_id(x).

  2. Avoid changing values.

While 1. is an immediate fix, and helps you reuse results for structures that share the same matrix, think about 2. in addition. It sometimes leads to more transparent code.


Thanks, I think I will try to avoid changing values. However, I have a question regarding the first approach: How does hash works for a composite type? Why changing does not change hash(x).


Look at the sources, eg

@edit hash(f, zero(UInt))

and you will see what is going on. The fallback method for composite hashes does not actually look into the object.

You can also try

if you don’t want to implement hashing yourself.