From: "Benjamin J. Tilly" <ben_tilly@...>
Date: 2001-03-10T23:53:22+09:00
Subject: [ruby-talk:12380] Re: Q re looping structures

>===== Original Message From "Christoph Rippel" <crippel@primenet.com> =====
>> From: Benjamin J. Tilly [mailto:ben_tilly@operamail.com]
>[..]
>
[...]
>> I already gave the example of a directory structure.
>> Recursive data structures are widely used, and a
>> friend verified for me that it is common to use a
>> caching algorithm like the one I coded.  (Hopefully
>> without that bug.)
>
>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.

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.

In fact I did it yesterday writing answers to the
Hamming sequence.

While I like it when a language catches my mistakes,
I prefer to have real mistakes caught.

>> [...]
>> >> In what you cut out I did construct them I thought.
>> >I know - I was thinking of [[[..],2],1]
>> >
>> Ah, that is a lot harder.  You can do it with streams,
>> but then you don't use the default array comparisons,
>> so we need not worry about it. :-)
>
>You can create this using reverse! ...
>
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.

Or do I misunderstand what you mean?

[...]
>> >require 'Ben'
>> >def cl( a, n)
>> >   base=loop= [a.clone]
>> >   (n-1).times { tmp = [a.clone]; loop << tmp; loop = tmp }
>> >   loop << base
>> >   base
>> >end
>> >
>> >p (cl("a",1) == cl("a",101))  # all id-cachings have this problem
>>
>> Is this a problem?
>
>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 ==?

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!

Cheers,
Ben

-------------------------------------------
The Fastest Browser on Earth now for FREE!!
Download Opera 5 for Windows now! Get it at
http://www.opera.com/download/
-------------------------------------------