Infinite sequences hang sets and maps
and it's not hard to guess, and then prove, why: user=> (defn fibs [] (map first (iterate (fn [[a b]] [b (+ a b)]) [1 1]))) #'user/fibs user=> (take 10 (fibs)) (1 1 2 3 5 8 13 21 34 55) user=> (.hashCode 12) 12 user=> (.hashCode "foo") 101574 user=> (.hashCode (take 10 (fibs))) -1796812414 user=> (.hashCode (fibs)) Probably the seq .hashCode should consider only the first N elements for some maximum N and if two longer (or even infinite) sequences collide so be it. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
This is basically the behavior I would expect. I expect that when I put two sequences into a set, they are compared for equality, which is clearly impossible if they are infinite. I don't think I'd want some automatically truncated comparison. If I really wanted truncated comparison, there are ways to achieve that. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
agreed, I'm not sure how meaningful it would be to compare two infinite "things". On Wed, Oct 28, 2009 at 12:05 PM, Mark Engelberg wrote: > > This is basically the behavior I would expect. I expect that when I > put two sequences into a set, they are compared for equality, which is > clearly impossible if they are infinite. I don't think I'd want some > automatically truncated comparison. If I really wanted truncated > comparison, there are ways to achieve that. > > > > -- Omnem crede diem tibi diluxisse supremum. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
On Wed, Oct 28, 2009 at 12:05 PM, Mark Engelberg wrote: > This is basically the behavior I would expect. I expect that when I > put two sequences into a set, they are compared for equality, which is > clearly impossible if they are infinite. I don't think I'd want some > automatically truncated comparison. If I really wanted truncated > comparison, there are ways to achieve that. Yes, I doubt equals can be made to work, but hashCode can, and equals can do something a bit more reasonable for (some) infinite sequences such as throw an exception. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
How about having hashCode() on infinite sequences drill down into the composite infinite sequences until we arrive at the generative function? Given that values are generated on demand, the generators themselves can be compared. To take from your fibs example: hashCode(iterate f x) = hashCode(x) + (37 * (hashCode(fn) + (37 * base- iterate-hash-value)) (Apologies for infix representation.) Lazy-sequence functions that wrap the iterate call would have their own hashCode() function call iterate's in a composite fashion. This way we avoid iterating over the values generated and instead derive unique values for unique sequences. On Oct 28, 3:55 am, John Harrop wrote: > and it's not hard to guess, and then prove, why: > > user=> (defn fibs [] (map first (iterate (fn [[a b]] [b (+ a b)]) [1 1]))) > #'user/fibs > user=> (take 10 (fibs)) > (1 1 2 3 5 8 13 21 34 55) > user=> (.hashCode 12) > 12 > user=> (.hashCode "foo") > 101574 > user=> (.hashCode (take 10 (fibs))) > -1796812414 > user=> (.hashCode (fibs)) > > > Probably the seq .hashCode should consider only the first N elements for > some maximum N and if two longer (or even infinite) sequences collide so be > it. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
On Wed, Oct 28, 2009 at 3:56 PM, Tim Clemons wrote: > How about having hashCode() on infinite sequences drill down into the > composite infinite sequences until we arrive at the generative > function? Given that values are generated on demand, the generators > themselves can be compared. This runs into problems with things like (repeatedly rand) though. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
On Oct 28, 1:34 pm, John Harrop wrote: > This runs into problems with things like (repeatedly rand) though. How so? The repeatedly function returns a lazy sequence that (presumably) stores a reference to repeatedly as its generator function. That instance of repeatedly would, in turn, have to store a reference to the rand function in order to call it as necessary. So when the resulting lazy sequence has its hash code requested, it could return a value similar to the following: (+ (.hashCode rand) (* 37 (.hashCode repeatedly))) --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
> So when the resulting lazy sequence has its hash code requested, it > could return a value similar to the following: > > (+ (.hashCode rand) (* 37 (.hashCode repeatedly))) I think John's point is this: user=> (take 3 (repeatedly rand)) (0.07020342855887218 0.590736243072285 0.04997104958104426) user=> (take 3 (repeatedly rand)) (0.6445602419794128 0.12488917903865004 0.5784287452848529) Different sequences, even if the generators are the same. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
On Oct 28, 4:33 pm, Richard Newman wrote: > I think John's point is this: > > user=> (take 3 (repeatedly rand)) > (0.07020342855887218 0.590736243072285 0.04997104958104426) > user=> (take 3 (repeatedly rand)) > (0.6445602419794128 0.12488917903865004 0.5784287452848529) > > Different sequences, even if the generators are the same. Ah, right. My gut response to that is if the users are calling hashCode() on lazy sequences, then they should expect a value which based on how the sequence is generated. If they want a hash code based on the actual values of the sequence, it should be evaluated with a doall and have hashCode called on the resulting non-lazy sequence. This would also make the user consciously face the possibility of evaluating an infinite sequence rather than it being a "gotcha" hidden away in hashCode's internals. That said, I haven't read enough Clojure code in the wild to get a feel of how upsetting such a change would be. Creating a hashmap with lazy sequences as keys seems unintuitive. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
John Harrop wrote: > Probably the seq .hashCode should consider only the first N elements > for some maximum N and if two longer (or even infinite) sequences > collide so be it. I strongly disagree. Choosing some arbitrary magic cutoff point just seems cause for trouble and much confusion. Putting something in a hash set or using it as a map key implies evaluating it -- you'd expect summing or printing an infinite sequence to hang, so why shouldn't hashing it also hang? Also to those suggesting treating infinite sequences differently to regular ones: it's impossible to determine (in the general case) whether a sequence is infinite or not as it would involve solving the halting problem. Throwing an exception in some specific cases would require changing things like (repeat x) to use a different seq implementation class. I think this would gain you very little since there's only a couple of cases where this can be done and as soon as you do something with the seq you don't know whether it's infinite anymore. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
On Wed, Oct 28, 2009 at 9:35 PM, Alex Osborne wrote: > John Harrop wrote: > > Probably the seq .hashCode should consider only the first N elements > > for some maximum N and if two longer (or even infinite) sequences > > collide so be it. > > I strongly disagree. Choosing some arbitrary magic cutoff point just > seems cause for trouble and much confusion. For the specific case of hashCode, no; identical values must have identical hashes but different values need not have different hashes. Collisions due to the hypothetical cutoff get exponentially less likely with each additional increment of 1 of the cutoff length. You're right though that they still won't work in hashmaps and hashsets because the equals test will hang when the sequences are actually equal. This also stops them working in treemaps and treesets (even if we added Comparable to ISeq to use lexicographic order and comparisons of the elements, or supplied a comparator that did so; and even if the seq-compare function gave up after N identical pairs of elements, resulting in hash collisions). A workaround if you want to index something by infinite (or just very large) seqs might be to use (take n the-seq) for some constant n chosen large enough for the truncated sequences to tend not to collide in practice, with some contingency for the case of collisions. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
Hello, On Thu, Oct 29, 2009 at 3:35 AM, Alex Osborne wrote: > > John Harrop wrote: >> Probably the seq .hashCode should consider only the first N elements >> for some maximum N and if two longer (or even infinite) sequences >> collide so be it. > > I strongly disagree. Choosing some arbitrary magic cutoff point just > seems cause for trouble and much confusion. Putting something in a hash > set or using it as a map key implies evaluating it -- you'd expect > summing or printing an infinite sequence to hang, so why shouldn't > hashing it also hang? +1, I also disagree. If there is a need to compare parts of infinite sequences, just truncate them and compare the resulting finite parts. This is something that belongs in the application, not in the language, as the value for N depends on the application and there is no N that fits everyone (other than infinity). -- Miron Brezuleanu --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
John Harrop wrote: > On Wed, Oct 28, 2009 at 9:35 PM, Alex Osborne wrote: > > Choosing some arbitrary magic cutoff point just > seems cause for trouble and much confusion. > > For the specific case of hashCode, no; identical values must have > identical hashes but different values need not have different hashes. > Collisions due to the hypothetical cutoff get exponentially less likely > with each additional increment of 1 of the cutoff length. Yeah, that's true, but I meant in the usual context where you fall back to equality in the event of a collision (like, as you say, sets and maps). I think it would be very confusing if when you put an infinite sequence in one set it works (because there's no collision so it uses the cutoff) while putting the exact same sequence in a different set it hangs (because of a collision it falls back to equality). I can imagine that being a nightmare to debug particularly because in most programs it will only happen very rarely. --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
On Wed, Oct 28, 2009 at 11:08 PM, John Harrop wrote: > For the specific case of hashCode, no; identical values must have identical > hashes but different values need not have different hashes. Collisions due > to the hypothetical cutoff get exponentially less likely with each > additional increment of 1 of the cutoff length. I see your point that hashCode could be made to work on infinite sequences, but since hashing is almost always a prelude to testing for equality, I'm hard pressed to think of an example of why you'd want to be able to do this. Can you illustrate with an example? --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
Wouldn't hashCode be called every time you use an infinite sequence as a key in a hash map? That strikes me as a problem, since everything else in Clojure makes perfectly good map keys. On Oct 29, 4:01 am, Mark Engelberg wrote: > On Wed, Oct 28, 2009 at 11:08 PM, John Harrop wrote: > > For the specific case of hashCode, no; identical values must have identical > > hashes but different values need not have different hashes. Collisions due > > to the hypothetical cutoff get exponentially less likely with each > > additional increment of 1 of the cutoff length. > > I see your point that hashCode could be made to work on infinite > sequences, but since hashing is almost always a prelude to testing for > equality, I'm hard pressed to think of an example of why you'd want to > be able to do this. Can you illustrate with an example? --~--~-~--~~~---~--~~ 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: Infinite sequences hang sets and maps
Luke VanderHart wrote: > On Oct 29, 4:01 am, Mark Engelberg wrote: >> I see your point that hashCode could be made to work on infinite >> sequences, but since hashing is almost always a prelude to testing for >> equality, I'm hard pressed to think of an example of why you'd want to >> be able to do this. Can you illustrate with an example? > Wouldn't hashCode be called every time you use an infinite sequence as > a key in a hash map? Yes, but this is another case where hashing is a prelude for testing equality. If there's a hash collision then the map will have to use equality testing to distinguish between two keys. If you make hashCode always work on infinite sequences, then sometimes using them as keys in maps will work and other times -- seemingly randomly -- it won't. In my opinion this is much worse than them never working as map keys. > That strikes me as a problem, since everything else in Clojure makes > perfectly good map keys. "Everything else" in Clojure is also printable and equality testable in finite time. There's just some things you can't do reliably with infinite sequences. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
