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