Lisp - How can I check if a list is a dotted pair?

Question

How can I check if a list in lisp is a dotted pair?

CL-USER 20 : 3 > (dotted-pair-p (cons 1 2))
T

CL-USER 20 : 3 > (dotted-pair-p '(1 2))
NIL

CL-USER 20 : 3 > (dotted-pair-p '(1 2 3))
NIL

I tried checking if length=2 but got error:

CL-USER 28 : 1 > (= (length (cons 2 3)) 2)
Error: In a call to LENGTH of (2 . 3), tail 3 is not a LIST.

Dunton

Note also that all proper lists are dotted pairs of a particular form. – Wake

Look at my answer and think about what is different between the two. length is going to assume there is an empty list. That is how it knows to stop. – Summerlin

(= (length (cons 2 3) 2)) should be (= (length (cons 2 3)) 2). – Weinshienk

Answer 1

A lisp list in "dotted pair notation" looks something like:

(1 . ()).

Since this is homework, I'll let you take this to the logical conclusion. Compare

(LIST 1 2) => (1 . (2 . ()))

with

(CONS 1 2) => (1 . 2).

What is different between these two? How can you tell the difference using predicates?

Remember all proper lisp lists end with the empty list. Ask yourself how do you access the second element of a cons pair? The solution from there ought to be clear.

Summerlin

The difference is that the first list has an empty list in the end and the second one doesn't, but hoe=w can I find out? – Dunton

Ask yourself how, in common lisp, is the empty list represented? (eq '() ??) Fill the ?? in. And of course you need to access the second element of the cons pair. What functions have you been taught? Go through them and put the puzzle pieces together. – Summerlin

'(1 . ()) is not a dotted list, it is simply (1)! – Tavern

Answer 2

Because a list always ends with the empty list, while a pair doesn't:

(listp (cdr '(1 2))) => T
(listp (cdr '(1 . 2))) => NIL

Delsiedelsman

Answer 3

(not(listp(cdr (cons 1 2))))=> T
(not(listp(cdr (list 1 2))))=> nill

Loreenlorelei

This answer needs some explanation to be useful; please edit it to include some. – Stratton

Answer 4

A dotted pair is a cons cell where it's CDR is not a cons itself (recursive definition). So this '(1 . 2) is a dotted pair, but this '(1 . ()) isn't, since it is just the printed representation of and the same as '(1).

(defun dotted-pair-p (x)
  (and (consp x)
       ;; Check that CDR is not a list with LISTP
       ;; since (CONSP ()) ;;=> NIL
       ;; and the CDR of a pair can't be NIL for it
       ;; to be dotted.
       (not (listp (cdr x)))))

(dotted-pair-p '(1 . 2))            ;T
(dotted-pair-p '(1 . ()))       ;NIL

Dotted lists (lists whose last cons cell is dotted) are defined in Common Lisp by LIST*. We can now use the above function to define a predicate for them too:

(defun list*p (x)
  (dotted-pair-p (last x))) 

(list*p (list* 1 2 3 4))        ;T
(list*p (list 1 2 3 4))         ;NIL

Tavern

Answer 5

You can check if a list is dotted (ends with a non-nil atom) with:

(defun dotted-listp (l)
  (cond ((null l) nil)
        ((atom l) t)
        (t (dotted-listp (cdr l)))))

Foochow

(dotted-listp 1) returns T – Julianejuliann