Speaking of definitions of equality: Writing a university project jvm to llvm 'compiler', I found myself designing a type in Haskell whose Ord and Eq instances 'naturally' got defined in such a way that "less than AND equal to" made sense. I doubt anyone's sanity except mine survived the project.
Joel On Wed, Apr 22, 2015 at 6:25 PM, Maik Schünemann <maikschuenem...@gmail.com> wrote: > 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. > -- 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.
