Page 1 of 1

find list in a list function

Posted: Sat Nov 19, 2011 3:56 pm
by sepuku
Hello people,i'm trying to define a function that takes a list as an argument and returns true if one of its elements is a list.
My function for some reason always returns nil.
I'm using the listp predicate whichs returns true if something is a list but so far i fail to make it work as i want.

Code: Select all

(defun list-in-a-list? (lst)
  (or (listp (car lst)) (listp (cdr lst))))
Shouldn't or return true if one of " (listp (car lst)) " or " (listp (cdr lst)) " is true?

I also tried this which also won't work:

Code: Select all

(defun list-in-a-list? (lst)
  (if (listp (car lst))
  (list-in-a-list? (cdr lst))))
Any advice is welcome.
Thank you in advance. :)

Re: find list in a list function

Posted: Sun Nov 20, 2011 12:08 am
by edgar-rft
sepuku wrote:Shouldn't or return true if one of " (listp (car lst)) " or " (listp (cdr lst)) " is true?
Yes, but an empty list is also a list, and the CDR of a list is always a list, even in an empty list, so your list-in-a-list? function should always return true (not nil = false) as long as the argument is an empty or non-empty list (at least it does so with CLISP and SBCL).

CONSP tests for non-empty lists and SOME tests if at least one element of a sequence satifies a predicate:

Code: Select all

(defun sublistp (arg)
  (and (consp arg)
       (some #'listp arg)))
Replace (some #'listp arg) with (some #'consp arg) if you want to test for non-empty sublists only.

- edgar

Re: find list in a list function

Posted: Sun Nov 20, 2011 8:46 am
by sepuku
Ahhh thanks,your version works fine.But is there a way to achieve it without some?I'm asking for educational reasons.I'm asking from ansi common lisp book and so far "i've not being taught some" so there must be a way to do it without some.

Thanks for your help so far. :)

Re: find list in a list function

Posted: Sun Nov 20, 2011 7:14 pm
by edgar-rft
A Scheme style solution using recursion would look like:

Code: Select all

(defun sublistp (arg)
  (and (consp arg)
       (or (listp (car arg))
           (sublistp (cdr arg)))))
If the first element (car arg) is not a list, then SUBLISTP will be called recursively with the rest of the list (cdr arg) as argument. The recursive call will then test the second element of the original list, which is the first element in the recursive call. This will go on until either an element is a list or the last element is reached and SUBLISTP will be called recursively with an argument of (cdr arg) => NIL, which will fail the (consp arg) test.

But again there is the problem that NIL elements are recognized as sublists because NIL also represents the empty list:

Code: Select all

(sublistp '(1 2 3))    => NIL
(sublistp '(1 (2 3)))  => T
(sublistp '(1 2 nil))  => T  ; is that correct?
Whether the last result is correct or not depends on the particular use-case, there is no clear "yes" or "no" answer.

Testing for non-empty sublists would look like:

Code: Select all

(defun sublistp (arg)
  (and (consp arg)
       (or (consp (car arg))
           (sublistp (cdr arg)))))
This version will produce:

Code: Select all

(sublistp '(1 2 3))    => NIL
(sublistp '(1 (2 3)))  => T
(sublistp '(1 2 nil))  => NIL  ; different than above
- edgar

Re: find list in a list function

Posted: Mon Nov 21, 2011 5:09 am
by sepuku
Ahh yes,thank you very much for your replies.I'll check and choose which version i prefer. :mrgreen:

Re: find list in a list function

Posted: Thu Nov 24, 2011 8:04 am
by virex
Or if you prefer loops you could also use: (The proposed recursive version should be tail-recursive, but if you're unlucky with your compiler/interpreter it may blow the stack for very large lists)

Code: Select all

(defun sublist-p (list)
  (loop for el in list 
    for sublist-p = (consp el)
    do (when sublist-p (return t))))

Re: find list in a list function

Posted: Fri Nov 25, 2011 2:20 pm
by sepuku
virex wrote:Or if you prefer loops you could also use: (The proposed recursive version should be tail-recursive, but if you're unlucky with your compiler/interpreter it may blow the stack for very large lists)

Code: Select all

(defun sublist-p (list)
  (loop for el in list 
    for sublist-p = (consp el)
    do (when sublist-p (return t))))

Thank you very much for your reply. I will write down your version too. :)