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. 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 <[email protected]> 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 <[email protected]> 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 [email protected] >>> Note that posts from new members are moderated - please be patient with >>> your first post. >>> To unsubscribe from this group, send email to >>> [email protected] >>> 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 [email protected]. >>> 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 [email protected] > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > [email protected] > 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 [email protected]. > 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 [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] 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 [email protected]. For more options, visit https://groups.google.com/d/optout.
