As Graham put it in the p.30 of his "ANSI Common Lisp":
"A friend is trying to write a function that returns the
sum of all non-nil elements in a list. He has written
two versions of this function and neither of them work.
Explain what's wrong with each, and give a correct
version:"
Now, I solved the first one, it is a simple matter
of not copying (setf'ing) the modified version of list.
However I have trouble with the second one, here's the original
version (with my slight variable name modification):
(defun summit (a-list)
(let ((x (car a-list)))
(if (null x)
(summit (cdr a-list))
(+ x (summit (cdr a-list))))))
OK, the first problem is that it enters an infinite
loop; to prevent it I propose this version:
(defun summit (a-list)
(if (not (null a-list))
(let ((x (car a-list)))
(if (null x)
(summit (cdr a-list))
(+ x (summit (cdr a-list)))))))
Now it doesn't enter infinite loop, however it doesn't work even
for the lists that doesn't contain any nil elements:
CL-USER> (summit (list 1 2))
And the SBCL debugger complains:
Argument Y is not a NUMBER: NIL
[Condition of type SIMPLE-TYPE-ERROR]
It seems like I'm trying to do addition using some number
and something that is not a number (a nil?).
I just couldn't find how to correct it? Can somebody enlighten me?
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc wrote:
> I just couldn't find how to correct it? Can somebody enlighten me?
You have to identify all of the possible input cases to the function
and ensure that for each case, it returns a sensible result which
stands on its own as correct, and also forms a foundation for recursion
too.
A good way to structure the function is to test for the cases in
succession, in order from strongest to weakest, using COND rather than
nested IF's.
If the list is empty, what should the return value be? Since the
function returns a sum, it should be some number. Zero would be a good
choice!
Otherwise if the first element of the list is nil, then the sum should
be just the sum of the rest of the list.
Otherwise the first element of the list can be assumed to be a number,
and the sum should be that number plus the sum of the rest of the list.
(Let the + function blow up if the element is not a number; that's an
input problem).
In these last two cases, notice that ``rest of the list'' can be empty,
if the input is a one-element list. Our definition of the function
saves us in these cases, because we decided that the sum over an empty
list is zero. That definition holds up our recursion for us and makes
arithmetic sense---or we could say, /because/ it makes arithmetic
sense.
Of course, the ``right'' way to do this (without resorting to even
better ways that take advantage of some nice library functions) is:
(let ((sum 0))
(dolist (item input-list sum)
(when item
(incf sum item))))
Recursion doesn't always make computation more beautiful.
What else could we recruit? The REDUCE function. To sum up a list,
without eliminating NIL values:
(reduce #'+ some-list :initial-value 0)
Now how about those pesky NIL's? One way would be to pre-process the
list to remove them:
(reduce #'+ (remove-if #'null some-list) :initial-value 0)
Another would be to replace #'+ with a function that handles NIL. The
function only has to handle NIL in its right operand. That right
operand should be optional.
(reduce #'(lambda (x y) (if y (+ x y) x))
some-list
:initial-value 0)
Why does only the right operand have to be checked for NIL? Because the
reduction is left-associative, and the list is padded on the left with
the :INITIAL-VALUE, so that even the first element of the list appears
as a right operand.
Well, good luck fixing up the recursive version.
> (reduce #'+ (remove-if #'null some-list) :initial-value 0)
You don't actually need the :initial-value since + handles no
arguments just fine.
(defun summit (a-list)
(reduce #'+ (remove-if-not #'numberp (mapcar #'car a-list))))
It seems like the map functions were very popular a few decades ago
when I first learned Lisp. A couple decades ago everyone got
obsessive about speed and efficiency and loop was born. Personally I
think a careless attitude towards garbage is what Lisp is all about.
Don Wells
Don Wells wrote:
>> (reduce #'+ (remove-if #'null some-list) :initial-value 0)
>
>
> You don't actually need the :initial-value since + handles no
> arguments just fine.
>
> (defun summit (a-list)
> (reduce #'+ (remove-if-not #'numberp (mapcar #'car a-list))))
(defun summit (a-list)
(reduce #'+ (remove-if-not #'numberp a-list :key #'car)))
You can also use REMOVE-IF and COMPLEMENT to avoid REMOVE-IF.
Cheers
--
Marco
>
> It seems like the map functions were very popular a few decades ago
> when I first learned Lisp. A couple decades ago everyone got
> obsessive about speed and efficiency and loop was born. Personally I
> think a careless attitude towards garbage is what Lisp is all about.
>
> Don Wells
>> (defun summit (a-list)
>> (reduce #'+ (remove-if-not #'numberp (mapcar #'car a-list))))
>
>(defun summit (a-list)
> (reduce #'+ (remove-if-not #'numberp a-list :key #'car)))
These two are not the same. The second makes the mistake of adding
together the associations instead of the car of the associations.
Don Wells
I went back and looked and I had thought the argument was an
association list but it wasn't stated as such. So neither of these
are right.
(defun summit (l)
(reduce #'+ (remove-if-not #'numberp l))
would be right. Something about the argument being called a-list sent
me off the path I suppose.
Don Wells
On Tue, 15 Feb 2005 17:45:57 -0500, Don Wells
<···········@comcast.net> wrote:
>
>>> (defun summit (a-list)
>>> (reduce #'+ (remove-if-not #'numberp (mapcar #'car a-list))))
>>
>>(defun summit (a-list)
>> (reduce #'+ (remove-if-not #'numberp a-list :key #'car)))
>
>These two are not the same. The second makes the mistake of adding
>together the associations instead of the car of the associations.
>
>Don Wells
Don Wells wrote:
>>>(defun summit (a-list)
>>> (reduce #'+ (remove-if-not #'numberp (mapcar #'car a-list))))
>>
>>(defun summit (a-list)
>> (reduce #'+ (remove-if-not #'numberp a-list :key #'car)))
>
>
> These two are not the same. The second makes the mistake of adding
> together the associations instead of the car of the associations.
>
Ooops
(defun summit (a-list)
(reduce #'+ (remove-if-not #'numberp a-list :key #'car) :key #'car))
The point is that you do not cons up a new list with MAPCAR.
Cheers
--
marco
On Wed, 16 Feb 2005 11:18:36 -0500, Marco Antoniotti
<·······@cs.nyu.edu> wrote:
>The point is that you do not cons up a new list with MAPCAR.
remove-if-not creates some conses too. In the example with mapcar I
could have coupled that with delete-if-not and saved some garbage. The
tail recusive version is probably the best since it is optimized into
a loop by the compiler. Or of course it could be coded as a loop
directly. If we were worried about performance.
But this brings me to a point I touched on earlier. I think that Lisp
programmers as a group are way too focused on micro optimized
performance when it is often not an issue. I have seen way too much
code run 10 times slower because of micro optimizations over macro
optimizations. Code readability should come first and then
optimization proceeds after you profile the code to identify the
bottle necks.
It reminds me of when I was at Carnegie Group and we were creating a
diagnostic system for a car company that hates to be named since a
couple of its products flipped over. It was a 3.5 million dollar per
year project, about half our little company's gross revenue. The
people writing the inference engine were so into optimization they
created an inference engine that didn't create a single cons of
garbage. Not one! They were so proud. Unfortunately in order to get
to zero garbage they had to eliminate some of the functionality that
was needed by the client. The result was the contract was lost and
the company was bought by Logica.
Don't let that happen to you too.
Don Wells
Don Wells wrote:
> On Wed, 16 Feb 2005 11:18:36 -0500, Marco Antoniotti
> <·······@cs.nyu.edu> wrote:
>
>
>>The point is that you do not cons up a new list with MAPCAR.
>
>
> remove-if-not creates some conses too.
Yes, of course.
In the example with mapcar I
> could have coupled that with delete-if-not and saved some garbage.
Yes, but in the process you could have destroyed the argument.
The
> tail recusive version is probably the best since it is optimized into
> a loop by the compiler. Or of course it could be coded as a loop
> directly. If we were worried about performance.
Not necessarily. I have at least the same expectations about REDUCE
being implemented on a isolinear chip, as having a very intelligent
compiler.
> But this brings me to a point I touched on earlier. I think that Lisp
> programmers as a group are way too focused on micro optimized
> performance when it is often not an issue. I have seen way too much
> code run 10 times slower because of micro optimizations over macro
> optimizations. Code readability should come first and then
> optimization proceeds after you profile the code to identify the
> bottle necks.
>
> It reminds me of when I was at Carnegie Group and we were creating a
> diagnostic system for a car company that hates to be named since a
> couple of its products flipped over. It was a 3.5 million dollar per
> year project, about half our little company's gross revenue. The
> people writing the inference engine were so into optimization they
> created an inference engine that didn't create a single cons of
> garbage. Not one! They were so proud. Unfortunately in order to get
> to zero garbage they had to eliminate some of the functionality that
> was needed by the client. The result was the contract was lost and
> the company was bought by Logica.
>
> Don't let that happen to you too.
I fully agree with this. I was just quibbling over a code snippet.
But that is what happened to me two months ago. I wrote some code under
LW that made a heavy use of UNION, INTERSECTION and friends. Turns out
that the LW implementations appear to use the simple quadratic
algorithm. After noticing that my code was running too slow I went in
and replaced the operations (using the same, re-packaged, name). I
always try to follow the "first get it right, then get it fast" philosophy.
Cheers
--
Marco
On 2005-02-15 07:41:23 -0500, Don Wells <···········@comcast.net> said:
>
>> (reduce #'+ (remove-if #'null some-list) :initial-value 0)
>
> (defun summit (a-list)
> (reduce #'+ (remove-if-not #'numberp (mapcar #'car a-list))))
>
> Personally I think a careless attitude towards garbage is what Lisp is
> all about.
>
In this case, something that is simpler doesn't cons:
(defun number-or-zero (x)
(if (numberp x) x 0))
(defun summit (l)
(reduce #'+ l :key #'number-or-zero))
(Note that in the original problem, the input isn't really an alist.)
^L
Kaz Kylheku uses reduce:
>
> (reduce #'(lambda (x y) (if y (+ x y) x))
> some-list
> :initial-value 0)
>
Using a key function has a certain charm
(defun summit (list)
(reduce (function +) list
:key (lambda(n)
(typecase n
(number n)
(t 0)))))
--
Alan Crowe
Lisp is not dead, it can eternal lie,
And with strange aeons even death may die.
- Abdul Alhazred
Emre Sevinc <·····@bilgi.edu.tr> wrote:
> "A friend is trying to write a function that returns the sum
> of all non-nil elements in a list."
Maybe the following hint helps without spoiling the fun:
what should your function return for an empty list?
--
Arthur Lemmens
"Arthur Lemmens" <········@xs4all.nl> wrote in message
·····················@news.xs4all.nl...
> Emre Sevinc <·····@bilgi.edu.tr> wrote:
>
> > "A friend is trying to write a function that returns the sum
> > of all non-nil elements in a list."
>
> Maybe the following hint helps without spoiling the fun:
> what should your function return for an empty list?
>
You might want to know that on page 42 Paul explains the two things you have
to think about when dealing with recursion.
Also there is the function numberp that you might want to use in order to
make your summit robust to non numerical lists (i.e. lists like (list 1 2 'a
3 'b 'c))
Arthur Lemmens <········@xs4all.nl> writes:
> Emre Sevinc <·····@bilgi.edu.tr> wrote:
>
>> "A friend is trying to write a function that returns the sum
>> of all non-nil elements in a list."
>
> Maybe the following hint helps without spoiling the fun:
> what should your function return for an empty list?
After reading p.42 (3.2 Understanding Recursion) and seeing
that your advice is along the similar line I propose this solution:
(defun summit (a-list)
(if (null a-list)
0
(let ((x (car a-list)))
(if (null x)
(summit (cdr a-list))
(+ x (summit (cdr a-list)))))))
Tried it with a couple of lists, with and without "nil"s,
seems to work. There may be a shorter version but this
is what I can do for now.
BTW, thanks for not spoiling the fun ;-)
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc wrote:
>
> (defun summit (a-list)
> (if (not (null a-list))
> (let ((x (car a-list)))
> (if (null x)
> (summit (cdr a-list))
> (+ x (summit (cdr a-list)))))))
>
>
> Now it doesn't enter infinite loop, however it doesn't work even
> for the lists that doesn't contain any nil elements:
>
> CL-USER> (summit (list 1 2))
>
> And the SBCL debugger complains:
>
> Argument Y is not a NUMBER: NIL
> [Condition of type SIMPLE-TYPE-ERROR]
>
> It seems like I'm trying to do addition using some number
> and something that is not a number (a nil?).
>
> I just couldn't find how to correct it? Can somebody enlighten me?
>
Your second post shows that you've solved the problem, so maybe you've
already figured this out. But notice in your solution above that the
outer IF does not supply an explicit "else" value. The default is for IF
to return NIL when the test fails and no "else" clause is provided. This
is what happens when your first version reaches the end of the list:
(summit (list 1 2))
1. Trace: (SUMMIT '(1 2))
2. Trace: (SUMMIT '(2))
3. Trace: (SUMMIT 'NIL)
3. Trace: SUMMIT ==> NIL
*** - argument to + should be a number: NIL
The 2nd call to SUMMIT is waiting to add 2 to the result of the 3rd
call, which returns NIL by default.
In case you're interested, here are a few ways to solve Graham's problem:
;;;
;;; Ex. 9
;;;
(defun summit-1 (l)
(apply #'+ (remove nil l)))
(defun summit-2 (l)
(reduce #'+ (remove nil l)))
(defun summit-3 (l)
(if (endp l)
0
(let ((x (first l)))
(if (null x)
(summit-3 (rest l))
(+ x (summit-3 (rest l)))) )))
(defun summit-4 (l)
(cond ((endp l) 0)
((null (first l)) (summit-4 (rest l)))
(t (+ (first l) (summit-4 (rest l)))) ))
(defun summit-5 (l)
(loop for elt in l
when elt
sum elt))
SUMMIT-3 is essentially the same as your second version. The last two
are not really fair since Graham doesn't introduce COND in chapter 2,
and he is allergic to LOOP.
David Sletten
From: Thomas A. Russ
Subject: Re: Simple recursive list processing question
Date:
Message-ID: <ymill9p1d0f.fsf@sevak.isi.edu>
Emre Sevinc <·····@bilgi.edu.tr> writes:
> CL-USER> (summit (list 1 2))
>
> And the SBCL debugger complains:
>
> Argument Y is not a NUMBER: NIL
> [Condition of type SIMPLE-TYPE-ERROR]
>
> It seems like I'm trying to do addition using some number
> and something that is not a number (a nil?).
Good job on the debugging.
This is, in fact, exactly what the problem is.
> I just couldn't find how to correct it? Can somebody enlighten me?
Well, for starters, it often helps to take simple case like
the one you have and then do it by hand. In other words, instead
of feeding it to the machine, try to see what would happen by
stepping through the code:
(Code reindented for better readability. It helps a lot).
> (defun summit (a-list)
> (if (not (null a-list))
> (let ((x (car a-list)))
> (if (null x)
> (summit (cdr a-list))
> (+ x (summit (cdr a-list)))))))
>
>
> Now it doesn't enter infinite loop, however it doesn't work even
> for the lists that doesn't contain any nil elements:
So, you initially call
(summit (1 2))
.. (1 2) is not null, so
x=1
.... x is not null, so
.... (+ 1 (summit (2)))
........... (2) is not null, so
x=2
........... x is not null, so
........... (+ 2 (summit ()))
.................. () is null, so the false branch of the first
IF statement is executed. Since there is no
such branch, NIL is returned.
[Remember that (if p x) == (if p x NIL)
NOW we unwinde the call stack:
............(+ 2 NIL)
Aha! We found the bug.
Just as an aside, I don't like to write IF statements that don't
have a false or else clause in them. If there isn't one, then
I prefer to use WHEN to make this clear. But in this case, I
think you want to make use of that other return value for something
besides NIL.
--
Thomas A. Russ, USC/Information Sciences Institute