Can Clojure memoize force me to evaluate my arguments?

Question

In Clojure, if I memoize a function, call it f and call it with argument a .

If a is a large lazy value, does memoize return a value based on a thunk match, as opposed to forcing a to evaluate and matching the result?

Where you are an invaluable part of the lazy sequence.

If this is not the case, is there a built-in way to get this behavior?

Thanks!

Answer 1

As pointed out by mikera, memoize does not process endless lazy sequences. I am adding this answer to give a brief description of the reasons for its implementation (plus two ideas for identification-based memoization schemes, one simple, another complex). (Editing: In fact, there is a simple, general solution based on identity, see below.)

Why it does not work

memoize uses a hash map to store the mapping from arguments to values, and hash maps use clojure.lang.Util/hasheq to determine if an object is one of their keys (except for empty maps that just return false ). Since the hasheq implementation for lazy seqs forces the entire section to specify any map, if the infinite lazy seq is one of its keys, it will force it to go into an infinite loop of extracting from memory. The same goes for memoize .

Strictly speaking, initially the map is an array map. (In Clojure, for efficiency reasons, small maps are usually array maps, and if assoc 'd elements are enough on the array map, the return value becomes a hash map.) However, non-empty map arrays also cannot handle endless lazy sessions for the same reason as the equivalence verification method.

Decision

System/identityHashCode returns that hashCode will be returned for given objects if it used the default implementation (regardless of whether its hashCode ).

 (defprotocol PWrapped (-unwrap [this])) PWrapped (defn wrap [o] (reify Object (hashCode [_] (System/identityHashCode o)) PWrapped (-unwrap [_] o))) ;;; adapted from clojure.core/memoize, (C) Rich Hickey, EPL-licenced (defn memoize "Returns a memoized version of a referentially transparent function. The memoized version of the function keeps a cache of the mapping from arguments to results and, when calls with the same arguments are repeated often, has higher performance at the expense of higher memory use." {:added "1.0" :static true} [f] (let [mem (atom {})] (fn [& args] (if-let [e (find @mem (map wrap args))] (val e) (let [ret (apply f args)] (swap! mem assoc (map wrap args) ret) ret))))) 

Now you can do this (which will not work with regular memoize ):

 user> (def r (lazy-cat (range 10000) (prn :foo) (range))) #'user/r user> (def f (memoize #(apply + (take 100 %)))) #'user/f user> (f [1 2 3]) 6 user> (fr) 4950 

---

The following is an initial discussion of alternative implementations.

I don’t think there is a built-in solution using pointer equality. To implement one of them as memoize , you will need to implement the map structure using hash based on the equality pointer (namely System/identityHashCode ). Or you can create a simple "last used" cache with clojure.lang.PersistentQueue .

Answer 2

Memoize will memoize based on the value of any argument you pass to it.

Therefore memoize works great with lazy sequences as arguments : since it looks at the value of the sequence, it will forcefully evaluate if necessary.

However, this means that you cannot use infinite lazy sequences , since using memoize can make them appreciate that it obviously won't end well.