Re: object identity
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.comwrote: 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.comwrote: 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.comwrote: 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
Re: object identity
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.comjavascript:
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.
Re: object identity
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
Re: object identity
I would try to write code that behaves like this where possible, because it
certainly improves performance (because of faster identity checks + less GC
pressure as you suggest). I think it is good practice in general when
implementing immutable data structures.
However I would generally not *rely* on this behaviour. It should be seen
as an implementation detail.
On Thursday, 27 February 2014 03:11:25 UTC+8, Brian Craft 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
Re: object identity
This seems like a reasonable optimization. I read something similar a few
years ago
(http://lorgonblog.wordpress.com/2008/05/24/catamorphisms-part-four/):
What we want is a function which will be smart, and only allocate new data
structures when necessary. Indeed, one of the main advantages of immutable
data structures is the ability to share portions of structure.
Bobby
On Monday, February 24, 2014 4:00:34 PM UTC-5, Brian Craft 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 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.
Re: object identity
[start slightly insane idea]
Perhaps we need the following:
* a way to tag a function as _pure_
* a map with uber_weak keys + values
by uber_weak, I mean the k/v pair vanishes when either the key
_or_ the value is gc-ed
Then, what we do here, is that every function auto-memoizes:
(func args) ==
* lookup in my uber_weak k/v map; if args is already there, return
last computed value
* if not, compute value, then put it into the uber_weak k/v map
Suppose uber_weak maps exist, this does not cause gc problems because:
* if our uber_weak map is the last reference to the either the k or
the v, the entire k/v pair gets removed from the uber_weak map
[end slightly insane idea]
I'm also going to mention that I know no where near enough about
js/java GC to say anything about how to implement uber_weak maps.
On Wed, Feb 26, 2014 at 8:37 PM, Bobby Eickhoff beickh...@gmail.com wrote:
This seems like a reasonable optimization. I read something similar a few
years ago
(http://lorgonblog.wordpress.com/2008/05/24/catamorphisms-part-four/):
What we want is a function which will be smart, and only allocate new data
structures when necessary. Indeed, one of the main advantages of immutable
data structures is the ability to share portions of structure.
Bobby
On Monday, February 24, 2014 4:00:34 PM UTC-5, Brian Craft 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 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.
Re: object identity
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.comjavascript:
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
Re: object identity
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.br...@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)
Re: object identity
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.br...@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 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.
Re: object identity
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.comjavascript:
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.comjavascript:
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 -
Re: object identity
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
Re: Object identity and with-meta
Hi,
only for persistent data structures (with a few caveats) [1]. For other
objects, such as function objects, equality check falls back to .equals().
Since with-meta returns a new object instance of an anonymous class,
.equals will always be false.
[1]
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Util.java#L23
Hope it helps,
Las
2012/11/23 N8Dawgrr nathan.r.matth...@gmail.com
I have unexplained behavior for with-meta.
As far as I understand with-meta should not alter object identity. E.g. if
we have the (= a b) = true for some a and b then
(= (with-meta a ma) (with-meta b mb)) = true should also hold for any ma
and mb.
So why do I get the following behavior at the REPL?
user (def f (partial * 2))
user (= f f)
true
user (= (with-meta f {:a 1}) (with-meta f {:a 1}))
false
Any help appreciated.
--
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
--
László Török
--
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
Re: Object identity and with-meta
When you compare functions, it only checks if it is the same function
object (not if the function behaves the same way).
For example:
(= (fn []) (fn []))
;= false
The reason you get false in your case is because with-meta returns a new
object every time you call it.
We need a new object to keep the immutability.
If you want to check whether two things are the same object, you can use
identical?, as so:
(identical? (fn []) (fn []))
;= false
(identical? {:b 3} {:b 3})
;= false
(def t {:b 3})
(identical? t t)
;= true
(identical? t (with-meta t {}))
;= false
As you can see on the last line, with meta returns a new object.
Note that:
(= t (with-meta t {}))
;= true
This is because = for maps check the actual contents of the map,
as opposed to how it works with functions
where it only checks if it is the same object.
Jonathan
On Fri, Nov 23, 2012 at 7:12 PM, N8Dawgrr nathan.r.matth...@gmail.comwrote:
I have unexplained behavior for with-meta.
As far as I understand with-meta should not alter object identity. E.g. if
we have the (= a b) = true for some a and b then
(= (with-meta a ma) (with-meta b mb)) = true should also hold for any ma
and mb.
So why do I get the following behavior at the REPL?
user (def f (partial * 2))
user (= f f)
true
user (= (with-meta f {:a 1}) (with-meta f {:a 1}))
false
Any help appreciated.
--
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 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
