[ruby-talk:12398] Re: Q re looping structures

> From: Benjamin J. Tilly [mailto:[e-mail]]
[...]
> >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

[...]