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<javascript:>>
> 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<javascript:>
> > 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 <javascript:>
> > 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 <javascript:>.
> > 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.
