I will mention a case that I wasn't thinking about when I wrote my previous message in this thread.
If one is commonly dealing with tree-like data structures, e.g. maps that contains maps as keys or values, which in turn contain other maps, or vectors, or sets, etc., it is relatively trivial in Clojure to write data transforms on those tree-like structures such that sub-structures of the returned value are identical to the sub-structures in the original. For example, the implementation of assoc on a map currently has the property that all keys and values _that are not affected by the assoc_ are identical to the corresponding keys and values in the original map. Similarly assoc on a vector returns a vector where all indices not affected by the assoc contain values that are identical to the original vector elements. Thus if your data transformation does not "modify" a large fraction of the tree-like structure, most sub-structures will be identical to the corresponding sub-structures in the original. I am not certain, but that may be what David Nolen is referring to in this article: http://swannodette.github.io/2013/12/17/the-future-of-javascript-mvcs/ Not that the entire transformed data structure is identical to the original, but a large fraction of the sub-structures are, so if you do a "diff" like comparison of an older structure and a newer one, you will find many identical sub-structures. Andy On Wed, Feb 26, 2014 at 6:14 PM, Andy Fingerhut <andy.finger...@gmail.com>wrote: > There are likely to be common ways of writing data transforms that happen > to return the same identical object as they were given, because > 'primitives' like assoc often do. > > I don't know of anyone who intentionally relies upon this behavior for > correctness of their code, and would strongly advise against ever doing so. > > I also don't know of anyone who intentionally tries to write such code in > order to improve performance of their Clojure programs. If they did, I > would guess they would often be frustrated by small changes to their > program that reduced performance by no longer returning identical objects. > > Andy > > > > On Wed, Feb 26, 2014 at 11:11 AM, Brian Craft <craft.br...@gmail.com>wrote: > >> Ok, trying a different way of asking this: >> >> Is it common practice in clojure to write data transforms in a way that >> will return the same object when possible (when the transform would be a >> noop), such as the mapv vs. reduce/assoc in my example? Would you do this >> to speed up equality checks, or to reduce gc pressure? Or is this an >> anti-pattern like using identical? >> >> b.c. >> >> >> On Tuesday, February 25, 2014 9:59:11 AM UTC-8, David Nolen wrote: >> >>> I don't really have anything to add to this thread but I will say that >>> Om's use of identical? is an implementation detail that's likely to change. >>> = already does an identical? check, ideally Om could use not= in the future >>> instead of (not (identical? ...)). >>> >>> David >>> >>> >>> On Tue, Feb 25, 2014 at 12:54 PM, Brian Craft <craft...@gmail.com>wrote: >>> >>>> No, my question isn't "is there a way" to do this. I'm sure there are a >>>> dozen ways to do it. My question is about a specific way of doing it. In >>>> particular, if your solution does not involve calling (identical? ..), then >>>> it's not what I'm asking about. >>>> >>>> In om core there's a call to identical? under the >>>> :shouldComponentUpdate key, which I suspect is what David was talking about >>>> in his blog posts about avoiding deep compares via immutable data >>>> structures. My question is about whether that has implications for how you >>>> write algorithms that update state, and whether the semantics of update-in >>>> (or assoc, really) that allow it to return the same object if the update >>>> would return an identical object, are related to this mechanism, if these >>>> semantics are documented, and if they depend on the data type being >>>> assoc'd. >>>> >>>> >>>> >>>> On Monday, February 24, 2014 6:27:02 PM UTC-8, t x wrote: >>>> >>>>> 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...@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 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 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.
