find list in a list function

Discussion of Common Lisp

find list in a list function

Postby sepuku » Sat Nov 19, 2011 3:56 pm

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. :)
sepuku
 
Posts: 12
Joined: Thu May 12, 2011 11:00 am

Re: find list in a list function

Postby edgar-rft » Sun Nov 20, 2011 12:08 am

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
edgar-rft
 
Posts: 157
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: find list in a list function

Postby sepuku » Sun Nov 20, 2011 8:46 am

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. :)
sepuku
 
Posts: 12
Joined: Thu May 12, 2011 11:00 am

Re: find list in a list function

Postby edgar-rft » Sun Nov 20, 2011 7:14 pm

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
edgar-rft
 
Posts: 157
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: find list in a list function

Postby sepuku » Mon Nov 21, 2011 5:09 am

Ahh yes,thank you very much for your replies.I'll check and choose which version i prefer. :mrgreen:
sepuku
 
Posts: 12
Joined: Thu May 12, 2011 11:00 am

Re: find list in a list function

Postby virex » Thu Nov 24, 2011 8:04 am

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))))
virex
 
Posts: 17
Joined: Fri Oct 28, 2011 3:41 pm

Re: find list in a list function

Postby sepuku » Fri Nov 25, 2011 2:20 pm

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. :)
sepuku
 
Posts: 12
Joined: Thu May 12, 2011 11:00 am


Return to Common Lisp

Who is online

Users browsing this forum: Yahoo [Bot] and 1 guest

cron