Perhaps I mis-interpreted your question. I thought the question asked was:
GIven: * pure function "func" * some object "obj" * (def a (func obj)) * (def b (func obj)) Example: * obj = [1 2 3] * (defn func [lst] (map #(* 2 %) lst)) Then: * is there a O(1) way to check if (= a b) ? In the above, we create two _different_ lists, both of which stores [2 4 6], thus they're equal, but not identical Proposed solution: tag the returned-value with a meta object, where the meta object describes how the object was computed. in this case, both [2 4 6] would have _identical_ meta objects, since they're both from the list [1 2 3] On Mon, Feb 24, 2014 at 5:56 PM, Brian Craft <craft.br...@gmail.com> wrote: > You're solving a similar problem, but I'm asking specifically about using > object identity, not equality, for tracking changes in a nested structure. > > > On Monday, February 24, 2014 1:42:03 PM UTC-8, t x wrote: >> >> I finally have a chance to give back. :-) >> >> I hacked up a newb's half-React. It does tree diffing + dom updating, >> but not the virtual event handling system. >> >> I ran into this exact problem, and solved it as follows: >> >> >> ## problem definition: >> >> render: data -> dom >> tree-diff: dom * dom -> list of dom-update-actions >> >> we want to avoid "deep tree diffing" on tree-diff >> >> the key idea is as follows: >> >> when render is called twice with same args, >> >> * we still have to recompute every time >> * we don't have to re-compare every time >> >> if render is a pure function, we do somethign like: >> >> (defn render [data] >> (with-meta (render-pure data) {:pure data})) >> >> (render-pure data) gives us a dom-tree >> we tag it with a meta project, telling us that it came from "data", >> and that it was a pure function >> >> >> then, doing the tree-diff stage, we do: >> >> >> (defn tree-diff [old-dom new-dom] >> (let [mo (meta old-dom) >> no (meta new-dom)] >> (if (and (:pure mo) (:pure no) (= (:pure mo) (:pure no))) >> .. ah, they're from the same pure function, thus the same ... >> ... okay, let's do expensive deep diff))) >> >> >> so basically, we abuse meta objects, record >> >> * what data gave us this dom tree ? >> * was the func that gave us the dom tree pure ? >> >> And if so, we just do a equality check on the data -- which are are >> _not_ "regenerating" and thus matches an equality check. >> >> >> Please let me if: >> >> (a) this resolves the issue >> (b) I completely misunderstood the question >> >> >> Thanks! >> >> >> >> >> >> >> On Mon, Feb 24, 2014 at 1:00 PM, Brian Craft <craft...@gmail.com> wrote: >> > This is vaguely related to David's posts about om/react, where he talks >> > about optimizing state change tracking by checking object identity on >> > immutable objects: deep compares can be avoided if same identity implies >> > no >> > changes. >> > >> > My first thought was that there are many algorithms that will give you a >> > new >> > object every time, even if nothing has changed. E.g. if your state has >> > an >> > array whose elements must be validated, doing a map over the elements >> > will >> > give you a new array every time, even if it makes no changes. >> > >> > Enforcing non-negative values, for instance: >> > >> > => (let [x {:a [1 -2 3]}] (update-in x [:a] (fn [y] (mapv #(if (< % 0) 0 >> > %) >> > y)))) >> > {:a [1 0 3]} >> > >> > In the following case the values are already non-negative, but we still >> > get >> > a new object: >> > >> > => (let [x {:a [1 2 3]}] (identical? x (update-in x [:a] (fn [y] (mapv >> > #(if >> > (< % 0) 0 %) y))))) >> > false >> > >> > One can imagine trying to rewrite this so it passes through the vector >> > if >> > nothing has changed. E.g. >> > >> > => (let [x {:a [1 2 3]}] (identical? x (update-in x [:a] (fn [y] (reduce >> > (fn >> > [v i] (if (< (v i) 0) (assoc v i 0) v)) y (range (count y))))))) >> > true >> > >> > => (let [x {:a [1 -1 3]}] (identical? x (update-in x [:a] (fn [y] >> > (reduce >> > (fn [v i] (if (< (v i) 0) (assoc v i 0) v)) y (range (count y))))))) >> > false >> > >> > I expect many algorithms would need to be reworked like this in order to >> > rely on object identity for change tracking. Is this madness? Am I >> > thinking >> > about this the wrong way? >> > >> > >> > An interesting note here is that the next-to-last update-in, above, >> > returned >> > the same object. I didn't know update-in could return the same object. A >> > simpler example: >> > >> > => (let [x {"a" [1 2 3]} y (update-in x ["a"] (fn [z] z))] [x y >> > (identical? >> > x y)]) >> > [{"a" [1 2 3]} {"a" [1 2 3]} true] >> > >> > => (let [x {"a" [1 2 3]} y (update-in x ["a"] (fn [z] [1 2 3]))] [x y >> > (identical? x y)]) >> > [{"a" [1 2 3]} {"a" [1 2 3]} false] >> > >> > >> > Is this some kind of optimization in update-in, that it doesn't create a >> > new >> > object if the new attribute is identical to the old attribute? Is it >> > peculiar to the data type? Is it documented anywhere? >> > >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups "Clojure" group. >> > To post to this group, send email to clo...@googlegroups.com >> > Note that posts from new members are moderated - please be patient with >> > your >> > first post. >> > To unsubscribe from this group, send email to >> > clojure+u...@googlegroups.com >> > For more options, visit this group at >> > http://groups.google.com/group/clojure?hl=en >> > --- >> > You received this message because you are subscribed to the Google >> > Groups >> > "Clojure" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> > an >> > email to clojure+u...@googlegroups.com. >> > For more options, visit https://groups.google.com/groups/opt_out. > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with your > first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.