yes - ok - I agree with that. I don't see this as a problem with the definition of equality.
D On Thursday, 23 April 2015 00:40:20 UTC+10, Hannes Steffenhagen wrote: > > > This. x = y => f(x) = f(y) obviously doesn't hold for arbitrary functions > and arbitrary notions of equality (e.g. all sets that contain the same > elements are equal, but the structures used to implement 'equal' sets need > not be equal themselves). So if you then introduce a function that derives > its result from the internal structure of the set - such as seq does - then > you obviously break that property for your notion of 'set equality'. This > doesn't mean the function isn't pure. It means your assumptions are wrong. > If you want to guarantee a specific ordering then you have to use > containers and/or algorithms that do actually guarantee a specific ordering. > > On Wednesday, April 22, 2015 at 9:53:47 AM UTC-4, Andy Fingerhut wrote: >> >> 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 equalThis. >> 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. >> >> 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 <dave...@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 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.
