Received: by 10.68.213.71 with SMTP id nq7mr1791040pbc.2.1323870408018;
        Wed, 14 Dec 2011 05:46:48 -0800 (PST)
Path: lh20ni21639pbb.0!nntp.google.com!news1.google.com!goblin2!goblin.stu.neva.ru!aioe.org!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Tamas Papp <tkp...@gmail.com>
Newsgroups: comp.lang.lisp
Subject: Re: ACL - Chpater 2, Exercise 9
Date: Wed, 14 Dec 2011 13:46:47 +0000 (UTC)
Organization: A noiseless patient Spider
Lines: 62
Message-ID: <jca9c7$nif$1@dont-email.me>
References: <4ee897c4$0$288$14726298@news.sunsite.dk>
Mime-Version: 1.0
Injection-Date: Wed, 14 Dec 2011 13:46:47 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="CYIzv6tOEv3dKK0QDry1SQ";
	logging-data="24143"; mail-complaints-to="ab...@eternal-september.org";	posting-account="U2FsdGVkX18x3oKzdtfUqS0CzCbOkirq"
User-Agent: Pan/0.133 (House of Butterflies)
Cancel-Lock: sha1:3Vcd2vzCt2zW5ozvSeO4Fhdd4rM=
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

On Wed, 14 Dec 2011 12:34:12 +0000, arnuld wrote:

> EXERCISE STATEMENT: A friend is trying to write a function that returns
> the sum of all non-nil elements in the given list. He has written  two
> versions of this function, and neither of them works. Explain what is
> wrong with each and give a correct version:
> 
> 1. (defun summit (lst)
>     (remove nil lst)
>     (apply #'+ lst))
> 
> 2. (defun summit (lst)
>     (let ((x (car lst)))
>      (if (null x)
>          (summit  (cdr lst))
>          (+ x (summit (cdr lst)))))
> 
> 
> 1st version has problem that (remove) never modifies the original list.
> Hence the correct version will be one-liner:  (apply #'+ (remove nil
> lst))
> 
> 
> 2. CLISP says "*** Program Stack Overflow . RESET" . Oh.. let me see,
> Recursion never bottoms out and hence it hits the stack limit. But then
> how to write a correct version which take care of nil atoms and bottoms
> out too ?
> 
> IDEA: rather than setting x to (car lst) and checking for null, we can
> keep on doing cdr till the end and when we will hit nil it means we have
> reached the last atom of list, from there onwards we can add values,
> tail- recursion. I am unable to implement it though
> 
> Is it correct way ?

I don't know what correct means in this context, but perhaps a more
idiomatic way would be to use REDUCE, treating NIL as 0.  Eg

(defun summit (sequence)
  "Sum non-nil elements of SEQUENCE."
  (reduce #'+ sequence :key (lambda (element)
                              (if (null element)
                                  0
                                  element))))

(summit '(1 2 3)) ; 6
(summit '(1 nil 2 3)) ; 6

This has the extra advantage that it works for all kinds of sequences:

(summit #(1 nil 2 3)) ; 6

Graham's ACL follows the pedagogical tradition of emphasizing
recursion, especially tail recursion.  It is certainly valuable to
learn about these things, and recursion can be a very nice idiom for
some problems, but I wonder if you would be better off learning from
Seibel's Practical Common Lisp book (you can find it on the net),
which (IMO) teaches a more idiomatic Common Lisp style.

Best,

Tamas