[racket-dev] Optional equality predicate for assoc and member

On Sun, Apr 24, 2011 at 8:00 PM, Eli Barzilay <eli at barzilay.org> wrote:
> About a minute ago, Robby Findler wrote:
>> On Sun, Apr 24, 2011 at 7:53 PM, Eli Barzilay <eli at barzilay.org> wrote:
>> > Here's another idea: in a world of immutable lists there are *much*
>> > less circular lists.  (Even more: the fact that they're generated via
>> > a temporary structure that is then copied means that they're usually
>> > very short too.)  Maybe it's fine to take it to the next level and
>> > just have all the standard functions ignore cycles?  Possibly with
>> > alternative names (or a new module) for versions that do account for
>> > cycles -- therefore putting the burden on the rare uses of circular
>> > lists?
>>
>> How about, instead of that: keep a counter and when you've seen 1000
>> (or 10000) cons cells or some other large number, then switch into a
>> safe mode?
>
> But that means that there's still an extra variable to keep around,
> which is the main penalty with the tortoise pointer, right?  (The
> other part being the almost inevitable code repeatage...)

We'd have to try it out, but I believe that it requires more
instructions to maintain the two pointers into the list and also it
has bad locality, so I expect it to be a win (no clue how much tho).

Robby