4 ms·

And others of us have wasted thousands of man hours because now we need an interval tree that works with date ranges and numeric ranges. Now we need to generate

And others of us have wasted thousands of man hours because now we need an interval tree that works with date ranges and numeric ranges. Now we need to generate code (extra build step, slowing down development) or copy and paste (error prone). And then another repo adds another interesting use for this single data structure and that type needs to be supported. And that's one data structure. We've got thousands of developers, many of whom are now writing Go. This comes up all the time and is not a niche use case. At this scale it's quite costly. IMO slapping on even basic Java / C# style generics does not harm you and if anything lets you optionally choose to use higher order functions or novel data structures you can't implement today without reflection.

marcrosoft 10y ago
Can you point me to a real world use case for what you are describing? I am honestly asking, so I can understand the use case. Edit: I have never written code that required me to copy and paste or generate code.
- Zach_the_Lizard 10y ago
  Finding overlapping intervals and querying on those ranges. E.g. answering this question: on January 2nd, what payment schedules apply (more than one because different countries pay out differently)? Or: if I add this schedule, does it overlap another one? If so, which ones? That's a date range based use case for this interval tree structure. Another team is doing something similar query-wise, but with integer based ranges. I forget what their use case is, but our data structure is exactly what they need, but we either need to use reflection (unacceptable) or copy and paste (also garbage) or code generation (bad) to accept and return the right types. This is trivial in Java, where I have a version of this written and used without complaint.
  - marcrosoft 10y ago
    I could be totally off but, if all the intervals were integer based would this problem go away? If so (probably not), would that mean that the lack of generics in Go influence good design from the beginning? Edit: Thank you for the use case!
    - Zach_the_Lizard 10y ago
      >I could be totally off but, if all the intervals were integer based would this problem go away? No. Even if you represent date ranges as pairs of integer timestamps in UTC (for consistency) you now need to do annoying and possibly bug prone casting and converting. Remember, code not written is bug free. Those tests won't write themselves. Also think of N dimensions; those come up often and are hard to handle with this input type. The moment someone needs a pair of GPS coordinates that are doubles you're SOL. Which incidentally is a common situation with interval trees: find things in a viewport, intersecting roads, etc. Even the tree itself is actually generic. You could build on a red black tree and using generics use an internal data type to order the tree with some extra book keeping and thus use the same underlying tree implementation for, say, an ordered set structure, interval trees, etc. You can do this all now with error prone casting. I don't know if you've done Java pre generics but it is a vastly more error prone world than post generics Java. Incidentally the lack of these other structures leads to lots of OrderedXYZTypeSet type code in our codebase that are generated to avoid cssting. With generics we'd not only have one implementation for all types, but we'd likely open source it since the broader Go community could use it and add additional useful types and functions. Go has very few built in data structures which exacerbates this problem. It at least partially has so few because the generics support in maps and slices etc. is basically a special cased hack since it's not baked into the language and is thus likely hard to maintain.
    - HelloNurse 10y ago
      Intervals can only be "based" on ordered pairs of things with a total ordering and a finite computer representation, of which integers (trivially) and dates (only if represented with adequate constraints) are only two examples. If a generic implementation of interval trees is not possible, the programming language is (deliberately) simplified, for the sake of stupid users or stupid implementations. Note that this is a very low bar: in C interval extremes can be void* and their total ordering can be represented as a function pointer int (f)(void,void*), while in old Java the interval tree could refer to a suitable "Element" interface, leaving cumbersome adapters and downcasts to client code.

marcrosoft 10y ago

Can you point me to a real world use case for what you are describing? I am honestly asking, so I can understand the use case. Edit: I have never written code that required me to copy and paste or generate code.

Zach_the_Lizard 10y ago
Finding overlapping intervals and querying on those ranges. E.g. answering this question: on January 2nd, what payment schedules apply (more than one because different countries pay out differently)? Or: if I add this schedule, does it overlap another one? If so, which ones? That's a date range based use case for this interval tree structure. Another team is doing something similar query-wise, but with integer based ranges. I forget what their use case is, but our data structure is exactly what they need, but we either need to use reflection (unacceptable) or copy and paste (also garbage) or code generation (bad) to accept and return the right types. This is trivial in Java, where I have a version of this written and used without complaint.
- marcrosoft 10y ago
  I could be totally off but, if all the intervals were integer based would this problem go away? If so (probably not), would that mean that the lack of generics in Go influence good design from the beginning? Edit: Thank you for the use case!
  - Zach_the_Lizard 10y ago
    >I could be totally off but, if all the intervals were integer based would this problem go away? No. Even if you represent date ranges as pairs of integer timestamps in UTC (for consistency) you now need to do annoying and possibly bug prone casting and converting. Remember, code not written is bug free. Those tests won't write themselves. Also think of N dimensions; those come up often and are hard to handle with this input type. The moment someone needs a pair of GPS coordinates that are doubles you're SOL. Which incidentally is a common situation with interval trees: find things in a viewport, intersecting roads, etc. Even the tree itself is actually generic. You could build on a red black tree and using generics use an internal data type to order the tree with some extra book keeping and thus use the same underlying tree implementation for, say, an ordered set structure, interval trees, etc. You can do this all now with error prone casting. I don't know if you've done Java pre generics but it is a vastly more error prone world than post generics Java. Incidentally the lack of these other structures leads to lots of OrderedXYZTypeSet type code in our codebase that are generated to avoid cssting. With generics we'd not only have one implementation for all types, but we'd likely open source it since the broader Go community could use it and add additional useful types and functions. Go has very few built in data structures which exacerbates this problem. It at least partially has so few because the generics support in maps and slices etc. is basically a special cased hack since it's not baked into the language and is thus likely hard to maintain.
  - HelloNurse 10y ago
    Intervals can only be "based" on ordered pairs of things with a total ordering and a finite computer representation, of which integers (trivially) and dates (only if represented with adequate constraints) are only two examples. If a generic implementation of interval trees is not possible, the programming language is (deliberately) simplified, for the sake of stupid users or stupid implementations. Note that this is a very low bar: in C interval extremes can be void* and their total ordering can be represented as a function pointer int (f)(void,void*), while in old Java the interval tree could refer to a suitable "Element" interface, leaving cumbersome adapters and downcasts to client code.