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

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.

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!