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.
