Subject: bug#62037: (proper-list-p '#1=(a #1#)) => 2. It should return nil.

From: Alan Mackenzie <[email-masked]>
Date: Tue, 28 Jan 2025 13:11:38 +0000

Hello, Basil.

On Sun, Jan 26, 2025 at 13:40:25 +0100, Basil L. Contovounesios wrote:
> Alan Mackenzie [2023-03-18 08:29 +0000] wrote:

> > The list #1=(a . #1#) is clearly circular.  proper-list-p should return
> > nil for it.

> It does.

> But the subject of the bug report is about #1=(a #1#) not #1=(a . #1#).

> > The purpose of proper-list-p is surely to find out in advance whether an
> > algorithm one wishes to run on a list can proceed without taking special
> > precautions for dottedness or circularity.  proper-list-p fails here.

> proper-list-p checks along the list's cdrs.

Yes.

> Detecting the circularity in #1=(a #1#) requires checking along the cars
> as well.  To me that implies a (more expensive) proper-tree-p (or
> similar) rather than proper-list-p, for the same reason that 'length'
> returns the same result as proper-list-p for #1=(a 1#).

> Would it help if the documentation of proper-list-p just mentioned the
> phrase 'along the cdrs', in the same way that copy-tree does?

I'm not sure.  I bumped into the above scenario when I was writing or
amending some algorithm which worked on a generic list structure, and
got infinite loops when that list was as above, despite first checking
it with proper-list-p.

To my mind, #1=(a #1#) is not a "proper list", despite what Drew has
said about the matter.  proper-list-p doesn't seem very useful when
ones purpose is to filter out lists that will break list traversing
algorithms.

Perhaps there ought to be a proper-tree-p function too, like you
suggest.

> Thanks,
> -- 
> Basil

-- 
Alan Mackenzie (Nuremberg, Germany).