Andy Fingerhut <andy.finger...@gmail.com> writes: > Dave, you say "seq on a set cannot be pure unless you were to provide an > argument to explicitly specify which order the items should be in". > > I think I would instead say: seq *is* a pure function, even though it > violates the property of "x equals y implies f(x) equals f(y)". There is > nothing impure about the definition of seq on sets. I would say that it is > the way equals is defined on hash sets, intentionally ignoring internal > implementation details that are visible to seq, that leads to the violation > of that property. > > I have updated my article with a Conclusion section since yesterday. I > have copied it below for those that have already read the article and want > to see only the new stuff: > > In hindsight after writing this, it now seems clear to me that if one > wants to maintain the property "x is equal to y implies f(x) is equal > to f(y)" for all functions f, then it is pretty important to be clear > on what "equal" means. > > As a silly example, if one gets to define their own equals for lists, > and you decide to define lists as equal if they contain the same > number of items, e.g. the list (1 2 3) is equal to the list (4 5 6) > because they both have 3 items, then you are easily going to violate > the property.
another example is that in clojure '(2) is equal to [2] - and this is a good thing, but (conj '(2) 3) is not equal to (conj [2] 3). so I agree that the property x = y => f(x) = f(y) is not reasonable for normal equality. It could be for pure functions and identical? > > Example 3 highlights this point: one can create implementations of > data structures using only pure functions, and a 'reasonable' > definition of equality, where the property can be violated. The root > of this issue is: sometimes reasonable definitions of equality regard > two values as equal, intentionally ignoring internal implementation > details of the data structure, but those differences ignored by equal > can be made observable by other functions you implement on the data > structure (like `seq` / `toList`). > > Andy > > > On Wed, Apr 22, 2015 at 1:22 AM, Dave Sann <daves...@gmail.com> wrote: > >> "x is equal to y" to imply "f(x) is equal to f(y)" - can only be true >> where a function is really based only on its arguments. I hadn't considered >> this before - while it seems simple, it is also a bit subtle. >> >> for example: seq on a set cannot be pure unless you were to provide an >> argument to explicitly specify which order the items should be in. If you >> do not do this, the order is defined either by some random interaction of >> the of the data and function implementations - that you thought was >> irrelevant - or has to be literally picked at random by the implementation. >> The former of these will appear to be pure until you hit the special cases. >> >> I speculate that only functions that retain or reduce the information >> content of their inputs can be pure. So if you rearrange or filter or map >> they can be pure. But if you *implicitly* add new information - as (seq >> set) does - then they cannot be. >> >> Dave >> >> On Wednesday, 22 April 2015 15:28:30 UTC+10, Andy Fingerhut wrote: >>> >>> One thing I was surprised by in my investigation was the lengths that >>> some people are willing to go to in order to avoid such things. >>> >>> Some people seem to *really* want the property "x is equal to y" to imply >>> "f(x) is equal to f(y)" for all functions, without exception, and consider >>> it a bug if a single function violates that property. >>> >>> I'm personally on the side of violating it if there is no good way to >>> keep it true for a particular function, preferably with documentation if >>> you are aware that you are not preserving it. >>> >>> Andy >>> >>> On Tue, Apr 21, 2015 at 8:32 PM, Dave Sann <dave...@gmail.com> wrote: >>> >>>> Just to expand on this slightly - seq applied to a set must introduce an >>>> order that is not present in the set. This order in principle comes from >>>> nowhere in the data. But it does in practice come from some arbitrary >>>> decisions in the implementation. Maybe this was andy's point. >>>> >>>> >>>> On Wednesday, 22 April 2015 13:18:43 UTC+10, Dave Sann wrote: >>>>> >>>>> Agree it's an interesting writeup. >>>>> >>>>> I think that the behaviour of seq should be entirely expected though. >>>>> Sets have no ordering (logically) so turning them into an ordered sequence >>>>> should be considered to be an entirely arbitrary operation (unless >>>>> specific >>>>> guarantees are provided). The fact that the implementations sometimes >>>>> maintain an order should not be used or relied upon at all. >>>>> >>>>> a seq of a set is not itself a set and therefore is not subject to the >>>>> same referential transparency rules as a set. >>>>> >>>>> Dave >>>>> >>>>> On Wednesday, 22 April 2015 12:39:42 UTC+10, Mike Rodriguez wrote: >>>>>> >>>>>> Thanks for sharing this. I found the write-up to be very informative >>>>>> and to have good background sources. >>>>>> >>>>>> I certainly never thought about this sneaky behavior concerning `seq` >>>>>> and hash sets before now. I'll have to look out for that one! >>>>>> >>>>>> On Tuesday, April 21, 2015 at 8:13:48 PM UTC-5, Andy Fingerhut wrote: >>>>>>> >>>>>>> I had come across the issue of Clojure hash sets that contain the >>>>>>> same set of elements returning their elements in different orders from >>>>>>> each >>>>>>> other, depending upon which order they were added to the set (only if >>>>>>> they >>>>>>> have equal values for (hash x)). >>>>>>> >>>>>>> This and other questions on referential transparency on the Clojure >>>>>>> group got me thinking on my commutes about it some more, and I dug into >>>>>>> it >>>>>>> way more than I expected to, and wrote up an article on it. If you >>>>>>> think >>>>>>> such a topic would interest you, you can read more about it here: >>>>>>> >>>>>>> >>>>>>> https://github.com/jafingerhut/thalia/blob/master/doc/other-topics/referential-transparency.md >>>>>>> >>>>>>> Guaranteed at least 99% epiphany free >>>>>>> >>>>>>> Andy >>>>>>> >>>>>>> -- >>>> 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/d/optout. >>>> >>> >>> -- >> 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/d/optout. >> -- Maik Schünemann Email: maikschuenem...@gmail.com Github: https://github.com/mschuene -- 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/d/optout.
