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: Joshua Taylor on 6 Aug 2010 13:48 On 2010.08.06 1:39 PM, Ariel Badichi wrote: > Joshua Taylor <tayloj(a)cs.rpi.edu> writes: >> 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 Good catch! I'd revised a time or two but missed removing SOME and NOTEVERY from that list of functions. //JT
From: Thomas A. Russ on 6 Aug 2010 12:17 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? Well, it depends on whether you think this is really a problem. Mathematicians (and others) often choose the definition of the correct behavior as one that makes things work out elegantly. For example, the definition of the empty argument list values of AND and OR in Common Lisp are based on this sort of argument. (and) ==> T (or) ==> NIL So, the definition of the empty argument case is up to the implementor of the function. If you consider that "all arguments are 7" can be considered equivalent to "there is no argument that is not 7" through standard logic transformations of universal and existential quantifiers, you can be quite happy with the result (all-seven nil) ==> T If you insist on treating the empty list differently if it is the first call to the function, then you really need to have two function. A top-level function and then a helper function that is the recursive call. An example would be (defun all-seven (ls) (labels ((all-seven-helper (ls) (cond ((null ls) t) ((/= 7 (car ls)) NIL) (t (all-seven-helper (cdr ls)))))) (and ls (all-seven-helper ls)))) -- Thomas A. Russ, USC/Information Sciences Institute
From: Thomas A. Russ on 6 Aug 2010 15:00 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? After coming up with my auxiliary function helper, I also figured out a slightly different solution. It involves deciding to interrupt the recursion befor calling the function with a NIL rather than afterwards. It can be done by adding a clause to the cond list: (defun all-seven (ls) (cond ((null ls) t) ((/= 7 (car ls)) NIL) ((cdr ls) (all-seven (cdr ls))) (t t))) ;; Because (car ls) = 7 and (cdr ls) is NIL. I still think this is the wrong semantics, but it will do what you ask. What the additional clause does is insure that you never call the function recursively with an empty list. Instead, you handle that case specially to terminate the recursion one call higher than the original function. That allows you to treat a NIL input and exhausing the list of values differently. -- Thomas A. Russ, USC/Information Sciences Institute
From: Rob Warnock on 6 Aug 2010 22:03 Zach Beane <xach(a)xach.com> wrote: +--------------- | ccc31807 <cartercc(a)gmail.com> writes: | > 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 +--------------- I think "cartercc" doesn't want the standard semantics, he wants: (defun one-or-more-sevens-p (list) (flet ((seven-p (x) (= x 7))) (and (every #'seven-p list) ; Could reverse EVERY & SOME (some #'seven-p list)))) ; but this order fails faster. ;-} -Rob ----- Rob Warnock <rpw3(a)rpw3.org> 627 26th Avenue <URL:http://rpw3.org/> San Mateo, CA 94403 (650)572-2607
From: Barry Margolin on 6 Aug 2010 22:05
In article <i3hcju$obd$1(a)news.eternal-september.org>, Joshua Taylor <tayloj(a)cs.rpi.edu> wrote: > 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). The reason it's done this way is that it supports the following tautology: (and (every pred list1) (every pred list2)) == (every pred (append list1 list2)) -- Barry Margolin, barmar(a)alum.mit.edu Arlington, MA *** PLEASE post questions in newsgroups, not directly to me *** *** PLEASE don't copy me on replies, I'll read them in the group *** |