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

From: Drew Adams <[email-masked]>
Date: Tue, 28 Jan 2025 19:10:24 +0000

Hello Alan!

> 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.

If your use case requires checking the elements
of a list ahead of time, to ensure that they
aren't infinite lists or don't involve infinite
lists, then yep, you need to do just that
(whatever "that" is, specifically, for your use
case).

And as I said, depending on what your actual
requirement is in that regard, that could mean
different kinds of checking, and it can be more
or less involved.

> To my mind, #1=(a #1#) is not a "proper list",
> despite what Drew has said about the matter.

We needn't agree on what "proper list" means.
What's important is what the predicate does.

IMO, the test needed - far and away the most
useful and most commonly needed - is a test
whether the list itself is circular/infinite.
And that means checking that its (extensional,
explicit) _length is finite_.

Whether to have other, more general (or more
specific, depending on your view point)
predicates, which check the list _elements_
for possible list values that are infinite,
or that test the elements for strings or
symbols that have properties whose values are
infinite lists, or ... -- that's a different
question (or a different basket of questions).

A priori, I don't see a need for Elisp to
predefine any such predicate(s).  My reasons:

1. Different use cases will call for different
   checks.
2. Such use cases aren't that common.
3. Providing such a general predicate, which
   can be costly to use, might encourage its
   use when it's not really needed or it's
   better to code a predicate specific to the
   given use.

   Let's not give the impression that such a
   check is parallel/equivalent to a check
   such as `proper-list-p'.  The latter has
   many, many, many more uses than any such
   check-cars-too predicate.
4. Users can anyway code up such a check if /
   when they really need it.

> proper-list-p doesn't seem very useful when
> ones purpose is to filter out lists that will
> break list traversing algorithms.

Be specific about your list traversal.  But
sure, if you need to traverse all branches
of a tree, and if one of those branches is
infinite, then ... Check each car that's a
list, to be sure it, in turn, has finite
length.  And hey - guess what! there's a
predicate for that...

(But sometimes you don't need to traverse
all branches all the way down or even know
whether you can do that.  Sometimes you can
traverse lazily, or at least breadth-first,
and not bother to find or act on nodes past
a given depth.)

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

Just please don't get rid of or redefine the
useful predicate `proper-list-p'.  (I don't
care so much about its name; it's its behavior
that's useful.)