From: Christoph Rippel Date: 2001-03-11T07:21:31+09:00 Subject: [ruby-talk:12398] Re: Q re looping structures > From: Benjamin J. Tilly [mailto:ben_tilly@operamail.com] [...] > >You can always write a specialised directory tree > >class for this (you can base this class on array > >and change the equal operator with any equality > >scheme you want and id-caching is not the only > >possibility) there is not need to burden the > >general array class with the heavy cost and > >problems of more complicated equality notions ... > > > Your basic linked list is another example. It may be > acceptable to decree that Ruby will break on recursive > data structures. It may even be reasonable to say > that you will do it because of performance. But you > are not about to convince me that it shouldn't be done > because what you get is conceptually too complicated. Okay you can cook up the notion of absolute equality for those things (as some sort graph with ordered content and ordered edges - you need this for deep perfect copying, basically what tar does) but this equality does not generalize the notion of equality for recursive Array's. Take the standard example x = [1]; y = [x,x]; z =[[1],[1]] in the graph interpretation there is huge difference between y and z but none as arrays. The question is how to generalize ordinary array equality to all graphs and this not obvious otherwise we would not have this discussion ... the two possible answers - id caching and ``untangle!'' (the algorithm does not simply cut some edges it is a bit more complicated) do this by describing an equivalence relation on the path space associated to the graph - so a full fledged tangle package should contain a path space and loop space generator (whose elements are themselves generators are) and you are more then welcome to provide them) > > FWIW the main reason that I see as a user for working > with a language with full gc rather than reference > counting is exactly because the languge will handle > recursive data structures better. > > [...] > >Simple crashing (the current behavior) - it tells you that > >there is probably something fundamentally wrong with your > >program and/or input - a type exception simply tells what > >went wrong and where ... > > > To the best of my knowledge I have never written a > recursive data structure unintentionally. But I have > before accidentally written a function that does deep > recursion quite a few times. Me neither, but it probably took me less then a minute to crash the interpreter when I stumbled on ``recursive'' in matju's flattening code - ruby needs a facilities to protected against milieus input - the taint/freeze mechanism is not enough and in general is just disconcerting that standard ruby has non facilities to handle recursive array's and that you can crash the interpreter so easily. As for programming errors it would be nice to have a package which gives you better control over the value type of an Array/Hash that would include path-depth and or (sub)type tainted ness etc. which throws an exception with detailed error information if you screwed up on your parameters... once you got your program debugged you can return to your happily un-parameterized standard container classes. Parameterized container classes easily catch logical programming errors which are hard to track down otherwise ... (but lets not get into a discussion about generic types again I am not about to fight windmills) [...] > You can create a data structure that looks like: > > [[[[[...], 4], 3], 2], 1] > > in a finite number of steps using arrays? I would like > to see this. irb(main):001:0> a=[1,[2,[3,[4]]]] [1, [2, [3, [4]]]] irb(main):002:0> a[1][1][1] << a [4, [1, [2, [3, [...]]]]] irb(main):003:0> a[1][1][1].reverse! [[1, [2, [3, [...]]]], 4] irb(main):004:0> a[1][1].reverse! [[[1, [2, [...]]], 4], 3] irb(main):005:0> a[1].reverse! [[[[1, [...]], 4], 3], 2] irb(main):006:0> a.reverse! [[[[[...], 4], 3], 2], 1] [...] > >Yes because you identify a loop of size 100 with loop > >of size one - you might think this is natural I don't > >(certainly not as a default behavior) and do say it > >again the algorithm takes forever to figure out that > >(cl("a",100) == cl("a",101)) are equal because you > >have run through the loop 100*101 times before > >realizing that they are equal . > > > You create an infinite data structure, and then in a > loop you unroll it a finite bit. Since the initial > data structure was infinite, why is it a surprise that > you can unroll as much as you want and still preserve > == when that was the defined behaviour of ==? Okay this a news group but you that I know this ... > > As for the other problem, you have found a worst case > performance case. It is still only quadratic in the > real size of the intial data structures. And it is > sufficiently hard to get into that I don't think that > people will do it by accident. > > IMHO it would be more reasonable to complain that > Enumerable offers a find method, which will result in > people into using that instead of hashing, thereby > making them more likely to make the mistake of writing > quadratic algorithms than it had to be. > > I guarantee you that Enumerable's find method will be > the cause of more quadratic Ruby programs than the > worst case of the id caching algorithm could ever hope > for! But enumerable is basically an abstraction of a list you would expect #find to be linear - enumerable is not an abstraction of an ordered hash - You already pointed out that the worst case of id-caching is probably O(n^3) and on the average O(n^2) on anything of type array of array ... it would be really stupid to make this the default behavior. Christoph [...]