To be a list or not

To be a list or not

[Lennart Borgman (gmail)]

The first of these complaints that it wants a list, the second says is 
is a list:

     ;; (length '(prop . val))
     ;; (listp '(prop . val))

(With Emacs 22)

Re: To be a list or not

[Eric Hanchrow]

    The first of these complaints that it wants a list, the second says is
    is a list:

        ;; (length '(prop . val))
        ;; (listp '(prop . val))

    (With Emacs 22)

Well, it's working as advertised:

    listp is a built-in function in `src/data.c'.
    (listp OBJECT)

    Return t if OBJECT is a list, that is, a cons cell or nil.
    Otherwise, return nil.

Although I myself don't think that any old cons cell ought to be
considered a list either.

-- 
Like most people, I would like to use the words ''parameters''
and ''behoove'' in the same sentence, but I am not sure how.
        -- A Question for 'Ask Mister Language Person'

Re: To be a list or not

[Nick Roberts]

 > The first of these complaints that it wants a list, the second says is 
 > is a list:

No it doesn't.

 >      ;; (length '(prop . val))

Debugger entered--Lisp error: (wrong-type-argument listp val)
  length((prop . val))

So it's saying that val should be a list:

(length '(prop . (val)))
2

'(prop . (val))
(prop val)

 >      ;; (listp '(prop . val))


 -- Function: length sequence
     This function returns the number of elements in SEQUENCE.  If
     SEQUENCE is a dotted list, a `wrong-type-argument' error is
     signaled.

I would start with the manual.

-- 
Nick                                           http://www.inet.net.nz/~nickrob

Re: To be a list or not

[Lennart Borgman (gmail)]

Nick Roberts wrote:
>  > The first of these complaints that it wants a list, the second says is 
>  > is a list:
> 
> No it doesn't.
> 
>  >      ;; (length '(prop . val))
> 
> Debugger entered--Lisp error: (wrong-type-argument listp val)
>   length((prop . val))
> 
> So it's saying that val should be a list:
> 
> (length '(prop . (val)))
> 2
> 
> '(prop . (val))
> (prop val)
> 
>  >      ;; (listp '(prop . val))
> 
> 
>  -- Function: length sequence
>      This function returns the number of elements in SEQUENCE.  If
>      SEQUENCE is a dotted list, a `wrong-type-argument' error is
>      signaled.
> 
> I would start with the manual.


Eh, yes but (sequencep '(prop . val)) also returns t at least in my 
version of Emacs. But maybe this has been changed?

Re: To be a list or not

[Nick Roberts]

 > Eh, yes but (sequencep '(prop . val)) also returns t at least in my 
 > version of Emacs. But maybe this has been changed?

I don't know what point you are making but all lists are sequences, so
if listp returns t so must sequencep.

-- 
Nick                                           http://www.inet.net.nz/~nickrob

Re: To be a list or not

[Lennart Borgman (gmail)]

Nick Roberts wrote:
 >  > Eh, yes but (sequencep '(prop . val)) also returns t at least in my
 >  > version of Emacs. But maybe this has been changed?
 >
 > I don't know what point you are making but all lists are sequences, so
 > if listp returns t so must sequencep.

You cited the following from the manual:

 >  -- Function: length sequence
 >      This function returns the number of elements in SEQUENCE.  If
 >      SEQUENCE is a dotted list, a `wrong-type-argument' error is
 >      signaled.

However (sequencp '(prop . val)) returns t.

What I wanted to know was the recommended way to check if something is a 
cons cell, but not a sequence, ie something like '(prop . val).

Thanks for the pointer to the manual.

Re: To be a list or not

[Bob Rogers]

   From: "Lennart Borgman (gmail)" <lennart.borgman@gmail.com>
   Date: Sat, 29 Dec 2007 01:18:34 +0100

   . . .

   However (sequencp '(prop . val)) returns t.

   What I wanted to know was the recommended way to check if something
   is a cons cell, but not a sequence, ie something like '(prop . val).

This is called an "improper list"; you could check for it thus:

	(defun proper-list-p (x)
	  (and (listp x)
	       (null (cdr (last x)))))

But of course, this is O(N), and would not even terminate for circular
lists, which is why the predicates are designed not to go to all that
trouble.

   FWIW, format.el defines a format-proper-list-p that is equivalent.

					-- Bob Rogers
					   http://rgrjr.dyndns.org/

Re: To be a list or not

[Richard Stallman]

    The first of these complaints that it wants a list, the second says is 
    is a list:

	 ;; (length '(prop . val))

It says that `val' is not a list.

Re: To be a list or not

[Thien-Thi Nguyen]

() Richard Stallman <rms@gnu.org>
() Sat, 29 Dec 2007 08:51:34 -0500

       The first of these complaints that it wants a list,

            ;; (length '(prop . val))

   It says that `val' is not a list.

read in L->R the orig. paren taunts:
"structure consistent", as poor function wants.
but Quality trumps all else, no use believing
the model unPerceived, the misunderstood deceiving.
poor function not so poor, maybe a little wiser:
shares news w/ company, w/ caller no miser.

thi

Re: To be a list or not

[Richard Stallman]

    Eh, yes but (sequencep '(prop . val)) also returns t at least in my 
    version of Emacs. But maybe this has been changed?

In a strict sense, that is not a sequence.  So ideally `sequencep'
should return nil.

However, making it return nil would require changing it from a
constant-time function to a linear-time function, and that seems like
a bad idea overall.

Re: To be a list or not

[Stephen J. Turnbull]

Bob Rogers writes:

 > This is called an "improper list"; you could check for it thus:
 > 
 > 	(defun proper-list-p (x)
 > 	  (and (listp x)
 > 	       (null (cdr (last x)))))

But please call it `true-list-p', which is the name of the similar
XEmacs built-in.  The XEmacs built-in uses a tortoise-hare algorithm
to ensure that cyclic lists are caught.  I don't know who may have
touched it so I won't post code here.

As several people have pointed out, it's still O(n).  In most cases it
make a lot more sense to use a condition-case around your list-
processing code and handle the error thrown appropriately only for the
last cons.

`true-list-p' is a built-in function
  -- loaded from "/playpen/src/XEmacs/git-integration/src/data.c"
(true-list-p OBJECT)

Documentation:
Return t if OBJECT is an acyclic, nil-terminated (ie, not dotted), list.

Re: To be a list or not

[Miles Bader]

"Stephen J. Turnbull" <stephen@xemacs.org> writes:
>  > 	(defun proper-list-p (x)
>  > 	  (and (listp x)
>  > 	       (null (cdr (last x)))))
>
> But please call it `true-list-p', which is the name of the similar
> XEmacs built-in.

I think "proper" is the commonly used terminology though...

-Miles

-- 
Ich bin ein Virus. Mach' mit und kopiere mich in Deine .signature.

Re: To be a list or not

[Tom Tromey]

>>>>> "Stephen" == Stephen J Turnbull <stephen@xemacs.org> writes:

Stephen> But please call it `true-list-p', which is the name of the
Stephen> similar XEmacs built-in.

Here's one stab at it.  This is basically lifted from safe-length.

I tested it with various inputs.

Is there an Emacs test suite?  I'd be happy to put tests there, if
there is one.

Tom

ChangeLog:
2007-12-29  Tom Tromey  <tromey@redhat.com>

	* lisp.h (Ftrue_list_p): Declare.
	* data.c (Ftrue_list_p): New function.
	(syms_of_data): Update.

Index: lisp.h
===================================================================
RCS file: /sources/emacs/emacs/src/lisp.h,v
retrieving revision 1.603
diff -u -r1.603 lisp.h
--- lisp.h	22 Nov 2007 01:01:26 -0000	1.603
+++ lisp.h	29 Dec 2007 23:10:43 -0000
@@ -2205,6 +2205,7 @@
 EXFUN (Fconsp, 1);
 EXFUN (Fatom, 1);
 EXFUN (Fnlistp, 1);
+EXFUN (Ftrue_list_p, 1);
 EXFUN (Fintegerp, 1);
 EXFUN (Fnatnump, 1);
 EXFUN (Fsymbolp, 1);
Index: data.c
===================================================================
RCS file: /sources/emacs/emacs/src/data.c,v
retrieving revision 1.287
diff -u -r1.287 data.c
--- data.c	22 Nov 2007 20:29:48 -0000	1.287
+++ data.c	29 Dec 2007 23:10:44 -0000
@@ -285,6 +285,28 @@
     return Qnil;
   return Qt;
 }
+
+DEFUN ("true-list-p", Ftrue_list_p, Strue_list_p, 1, 1, 0,
+       doc: /* Return t if OBJECT is an acyclic, nil-terminated list.  */)
+     (object)
+     Lisp_Object object;
+{
+  Lisp_Object tail, halftail;
+  int len = 0;
+
+  /* halftail is used to detect circular lists.  */
+  halftail = object;  
+  for (tail = object; CONSP (tail); tail = XCDR (tail))
+    {
+      if (EQ (tail, halftail) && len != 0)
+	return Qnil;
+      ++len;
+      if ((len & 1) == 0)
+	halftail = XCDR (halftail);
+    }
+
+  return tail == Qnil ? Qt : Qnil;
+}
 \f
 DEFUN ("symbolp", Fsymbolp, Ssymbolp, 1, 1, 0,
        doc: /* Return t if OBJECT is a symbol.  */)
@@ -3291,6 +3313,7 @@
   defsubr (&Stype_of);
   defsubr (&Slistp);
   defsubr (&Snlistp);
+  defsubr (&Strue_list_p);
   defsubr (&Sconsp);
   defsubr (&Satom);
   defsubr (&Sintegerp);

Re: To be a list or not

[Andreas Schwab]

Tom Tromey <tromey@redhat.com> writes:

> +  return tail == Qnil ? Qt : Qnil;
            NILP (tail)

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: To be a list or not

[Stephen J. Turnbull]

Tom Tromey writes:
 > >>>>> "Stephen" == Stephen J Turnbull <stephen@xemacs.org> writes:
 > 
 > Stephen> But please call it `true-list-p', which is the name of the
 > Stephen> similar XEmacs built-in.
 > 
 > Here's one stab at it.  This is basically lifted from safe-length.

Looks very familiar.

XEmacs implements one change you might think about.  Specifically, it
delays starting the tortoise until the length is "long enough to
suspect circularity".  I don't know if the value chosen was tuned or
not.  As I understand it, this makes the function slightly faster for
shorter lists, slightly slows down longer true lists, and might double
the detection time for cyclical lists.

Looks like a win to me, but YMMV.

Re: To be a list or not

[Richard Stallman]

    Is there an Emacs test suite?  I'd be happy to put tests there, if
    there is one.

No, but it would be good to start one.  Would you like to start one?

Re: To be a list or not

[Bob Rogers]

   From: "Stephen J. Turnbull" <stephen@xemacs.org>
   Date: Sun, 30 Dec 2007 09:54:41 +0900

   Tom Tromey writes:
    > >>>>> "Stephen" == Stephen J Turnbull <stephen@xemacs.org> writes:
    > 
    > Stephen> But please call it `true-list-p', which is the name of the
    > Stephen> similar XEmacs built-in.
    > 
    > Here's one stab at it.  This is basically lifted from safe-length.

   Looks very familiar.

   XEmacs implements one change you might think about.  Specifically, it
   delays starting the tortoise until the length is "long enough to
   suspect circularity".  I don't know if the value chosen was tuned or
   not.  As I understand it, this makes the function slightly faster for
   shorter lists, slightly slows down longer true lists, and might double
   the detection time for cyclical lists.

   Looks like a win to me, but YMMV.

Another trick is to unroll the loop so that it follows the tortoise, as
done in the CMU Common Lisp list-length function shown below (which is
in the public domain).  If you combine both tricks, you would have two
loops, the first of which only needs to maintain a tail and a counter,
and the second only needs to maintain a tail and a tortoise.

   But it's not at all clear that this is worth all that trouble . . .

					-- Bob

------------------------------------------------------------------------
(defun list-length (list)
  "Returns the length of the given List, or Nil if the List is circular."
  (do ((n 0 (+ n 2))
       (y list (cddr y))
       (z list (cdr z)))
      (())
    (declare (fixnum n) (list y z))
    (when (endp y) (return n))
    (when (endp (cdr y)) (return (+ n 1)))
    (when (and (eq y z) (> n 0)) (return nil))))

Re: To be a list or not

[Tom Tromey]

>>>>> "Andreas" == Andreas Schwab <schwab@suse.de> writes:

Andreas> Tom Tromey <tromey@redhat.com> writes:
Andreas> +  return tail == Qnil ? Qt : Qnil;
Andreas>             NILP (tail)

Thanks, I didn't know about that.  BTW I see a number of EQ(...,Qnil)
comparisons in the current code.

Here's a revised patch.

I considered Stephen's suggestion of having two loops, but I think it
probably is not worthwhile.

Tom

2007-12-31  Tom Tromey  <tromey@redhat.com>

	* lisp.h (Ftrue_list_p): Declare.
	* data.c (Ftrue_list_p): New function.
	(syms_of_data): Update.

Index: data.c
===================================================================
RCS file: /sources/emacs/emacs/src/data.c,v
retrieving revision 1.287
diff -u -r1.287 data.c
--- data.c	22 Nov 2007 20:29:48 -0000	1.287
+++ data.c	31 Dec 2007 17:04:24 -0000
@@ -285,6 +285,28 @@
     return Qnil;
   return Qt;
 }
+
+DEFUN ("true-list-p", Ftrue_list_p, Strue_list_p, 1, 1, 0,
+       doc: /* Return t if OBJECT is an acyclic, nil-terminated list.  */)
+     (object)
+     Lisp_Object object;
+{
+  Lisp_Object tail, halftail;
+  int len = 0;
+
+  /* halftail is used to detect circular lists.  */
+  halftail = object;  
+  for (tail = object; CONSP (tail); tail = XCDR (tail))
+    {
+      if (EQ (tail, halftail) && len != 0)
+	return Qnil;
+      ++len;
+      if ((len & 1) == 0)
+	halftail = XCDR (halftail);
+    }
+
+  return NILP (tail) ? Qt : Qnil;
+}
 \f
 DEFUN ("symbolp", Fsymbolp, Ssymbolp, 1, 1, 0,
        doc: /* Return t if OBJECT is a symbol.  */)
@@ -3291,6 +3313,7 @@
   defsubr (&Stype_of);
   defsubr (&Slistp);
   defsubr (&Snlistp);
+  defsubr (&Strue_list_p);
   defsubr (&Sconsp);
   defsubr (&Satom);
   defsubr (&Sintegerp);
Index: lisp.h
===================================================================
RCS file: /sources/emacs/emacs/src/lisp.h,v
retrieving revision 1.603
diff -u -r1.603 lisp.h
--- lisp.h	22 Nov 2007 01:01:26 -0000	1.603
+++ lisp.h	31 Dec 2007 17:05:52 -0000
@@ -2205,6 +2208,7 @@
 EXFUN (Fconsp, 1);
 EXFUN (Fatom, 1);
 EXFUN (Fnlistp, 1);
+EXFUN (Ftrue_list_p, 1);
 EXFUN (Fintegerp, 1);
 EXFUN (Fnatnump, 1);
 EXFUN (Fsymbolp, 1);

Re: To be a list or not

[Andreas Schwab]

Tom Tromey <tromey@redhat.com> writes:

>>>>>> "Andreas" == Andreas Schwab <schwab@suse.de> writes:
>
> Andreas> Tom Tromey <tromey@redhat.com> writes:
> Andreas> +  return tail == Qnil ? Qt : Qnil;
> Andreas>             NILP (tail)
>
> Thanks, I didn't know about that.  BTW I see a number of EQ(...,Qnil)
> comparisons in the current code.

The latter is ok, but x == Qnil will fail when Lisp_Object is a union.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."