how to test for nil input in a recursive function?
in [Lisp]
|
Prev: intro to chinese punctuation for english speakers (with computing & linguistic perspective)
Next: intro to chinese punctuation for english speakers (with computing & linguistic perspective)
From: ccc31807 on 6 Aug 2010 11:50 The usual template for a recursive function recurs down the list applying some test and returns when the list is null. If you are testing each element for some value to see if all values in the list meet the test, you will return nil if some value fails the test. If every value meets the test, you return T when the list is null. However, if the input list is null, this function will return T, even though no element of the list meets the test. For example, to test whether all the members of the list are equal to 7: (defun all-seven (ls) (cond ((null ls) t) ((/= 7 (car ls)) NIL) (t (all-seven (cdr ls))))) If you pass the function the empty list, it returns true, even though no element of the list is equal to 7. What is the logic to fix this problem? Thanks, CC.
From: Joshua Taylor on 6 Aug 2010 12:18 On 2010.08.06 11:50 AM, ccc31807 wrote: > The usual template for a recursive function recurs down the list > applying some test and returns when the list is null. > > If you are testing each element for some value to see if all values in > the list meet the test, you will return nil if some value fails the > test. If every value meets the test, you return T when the list is > null. > > However, if the input list is null, this function will return T, even > though no element of the list meets the test. For example, to test > whether all the members of the list are equal to 7: > > (defun all-seven (ls) > (cond > ((null ls) t) > ((/= 7 (car ls)) NIL) > (t (all-seven (cdr ls))))) > > If you pass the function the empty list, it returns true, even though > no element of the list is equal to 7. What is the logic to fix this > problem? Typically, functions that ensure that every element of a sequence satisfies a given predicate will return true for empty sequences since every element satisfies the predicate (trivially, since there are elements). For instance, this is the behavior of EVERY, SOME, NOTANY, and NOTEVERY [1]. Your all-seven is equivalent to: (notany #'(lambda (x) (/= x 7)) ls) and, a bit more simply, (every #'(lambda (x) (= x 7)) ls) It sounds like what you want is a function that checks whether there is a non-seven in the list and returns false if there is, and return otherwise. The simplest way is probably just: (and (not (endp ls)) (every #'(lambda (x) (= x 7)) ls)) If you want to write your own version without using one of the standard functions, you could modify your all-seven using labels to get: (defun all-seven (ls) (and (not (endp ls)) (labels ((%all-seven (ls) (cond ((null ls) t) ((/= 7 (car ls)) NIL) (t (%all-seven (cdr ls)))))) (%all-seven ls)))) //JT CL-USER> (defun non-empty-all-sevens (list) (and (not (endp list)) (labels ((all-sevens (list) (or (endp list) (and (= 7 (first list)) (all-sevens (rest list)))))) (all-sevens list)))) NON-EMPTY-ALL-SEVENS CL-USER> (non-empty-all-sevens '(7 7 7 7)) T CL-USER> (non-empty-all-sevens '()) NIL Yout can simplify that too by using the standard function EVERY, of course: [1] http://www.lispworks.com/documentation/HyperSpec/Body/f_everyc.htm
From: Zach Beane on 6 Aug 2010 12:18 ccc31807 <cartercc(a)gmail.com> writes: > The usual template for a recursive function recurs down the list > applying some test and returns when the list is null. > > If you are testing each element for some value to see if all values in > the list meet the test, you will return nil if some value fails the > test. If every value meets the test, you return T when the list is > null. > > However, if the input list is null, this function will return T, even > though no element of the list meets the test. For example, to test > whether all the members of the list are equal to 7: > > (defun all-seven (ls) > (cond > ((null ls) t) > ((/= 7 (car ls)) NIL) > (t (all-seven (cdr ls))))) > > If you pass the function the empty list, it returns true, even though > no element of the list is equal to 7. What is the logic to fix this > problem? I don't see the problem. No element of the list fails the test. See the semantics of the standard function EVERY for a similar view: (every #'oddp '(1 3 5)) => T (every #'oddp '()) => T See also zero-argument AND. Zach
From: Ariel Badichi on 6 Aug 2010 12:48 ccc31807 <cartercc(a)gmail.com> writes: > However, if the input list is null, this function will return T, even > though no element of the list meets the test. For example, to test > whether all the members of the list are equal to 7: > > (defun all-seven (ls) > (cond > ((null ls) t) > ((/= 7 (car ls)) NIL) > (t (all-seven (cdr ls))))) > > If you pass the function the empty list, it returns true, even though > no element of the list is equal to 7. What is the logic to fix this > problem? How is this a problem? Are you not aware of the logical concept of Vacuous Truth? It is true that no element in the list is 7. It is also true that all elements in the list are 7. Taking these two statements together does not produce a contradiction, it just entails that the list is empty. Ariel
From: Ariel Badichi on 6 Aug 2010 13:39
Joshua Taylor <tayloj(a)cs.rpi.edu> writes: > On 2010.08.06 11:50 AM, ccc31807 wrote: >> The usual template for a recursive function recurs down the list >> applying some test and returns when the list is null. >> >> If you are testing each element for some value to see if all values in >> the list meet the test, you will return nil if some value fails the >> test. If every value meets the test, you return T when the list is >> null. >> >> However, if the input list is null, this function will return T, even >> though no element of the list meets the test. For example, to test >> whether all the members of the list are equal to 7: >> >> (defun all-seven (ls) >> (cond >> ((null ls) t) >> ((/= 7 (car ls)) NIL) >> (t (all-seven (cdr ls))))) >> >> If you pass the function the empty list, it returns true, even though >> no element of the list is equal to 7. What is the logic to fix this >> problem? > > Typically, functions that ensure that every element of a sequence > satisfies a given predicate will return true for empty sequences since > every element satisfies the predicate (trivially, since there are > elements). For instance, this is the behavior of EVERY, SOME, NOTANY, > and NOTEVERY [1]. Your all-seven is equivalent to: For a given predicate P, and where the universe of discourse is the elements of a sequence: EVERY returns true iff (∀x)Px. NOTANY returns true iff (∀x)¬Px. SOME returns true iff (∃x)Px. NOTEVERY returns true iff (∃x)¬Px. The latter two return false for the empty list, because truth of an existentially qualified statement requires at least one member in the universe of discourse. They do not imply anything about every element of a sequence, only about a particular one, if it exists. > [1] http://www.lispworks.com/documentation/HyperSpec/Body/f_everyc.htm Ariel |