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

I don't think the current cycle-checking cost is significant. Also, if
a program uses `assoc' on a list that's long enough for locality of the
turtle to matter, then it probably has bigger problems. But don't let
me stop you from experimenting!

At Sun, 24 Apr 2011 20:07:31 -0500, Robby Findler wrote:
> On Sun, Apr 24, 2011 at 8:06 PM, Eli Barzilay <eli at barzilay.org> wrote:
> > About a minute ago, Robby Findler wrote:
> >> 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).
> >
> > I don't think that there would be a locality issue -- you never
> > dereference the slow pointer.
> 
> I thought the way it worked was you had two pointers into the list and
> you did cdr on one and cddr on the other and checked if they were eq?.
> 
> Robby