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:
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
arnuld <sunr...@invalid.address> writes:
> 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:
> 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'll answer this by showing another version of #'summit:
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:
> 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.
arnuld <sunr...@invalid.address> wrote on 14 Dec 2011 12:3:
> EXERCISE STATEMENT: A friend is trying to write a function that returns > the sum of all non-nil elements in the given list.
> 2. (defun summit (lst)
> (let ((x (car lst)))
> (if (null x) > (summit (cdr lst))
> (+ x (summit (cdr 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 ?
Your problem is that at the very end of the list, (CDR LST) = NIL, so
SUMMIT gets called again with (SUMMIT NIL). Which, in your version,
recurses again. (Note the (CDR NIL) also = NIL, forever.)
So what you need is a check for this final special case:
(defun summit (lst)
(if (null lst)
0
... ))
> 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 ?
You need both. The check for (NULL LST) is to see if you're at the end
of the recursion. The check for (NULL X) is to see whether the current
element is a number (in which case you add it to the sum), or else a NIL
(in which case you ignore it).
Speaking of which, (NOT (NUMBERP X)) might be a better test, in your
original function, than the (NULL X) you have there...
-- Don
___________________________________________________________________________ ____
Don Geddis http://don.geddis.org/ d...@geddis.org
Happiness is having a chitinous exoskeleton.
arnuld <sunr...@invalid.address> 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:
> 1st version has problem that (remove) never modifies the original list. > Hence the correct version will be one-liner: (apply #'+ (remove nil > lst))
Correct.
> 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 ?
What should be the result if it gets an empty list? That's the "bottom out" case.
> 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 ?
That's one way, but it's not the simple way. The code above is almost correct, it's just missing the bottom case. Add that and it should work fine.
-- Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
> On Wed, 14 Dec 2011 13:46:47 +0000, Tamas Papp wrote:
> 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:
>> 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 ?
> 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
That seems more like production/industrial/real-life code as compared to ACL exercise which looks more like academic code to me.
> 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.
I thought recursion was CL's basic paradigm (ACL says its functional programming). I searched a lot on CLL archives but I couldn't find anyone claiming that PCL teaches more idiomatic Lidp style as compared to ACL.
Myself, as I have finished 2 chapters of ACL, I found it little but academic and at the same time quite terse.
arnuld writes:
> > On Wed, 14 Dec 2011 13:46:47 +0000, Tamas Papp wrote:
> > 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
> > 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.
> I thought recursion was CL's basic paradigm (ACL says its functional
> programming). I searched a lot on CLL archives but I couldn't find
> anyone claiming that PCL teaches more idiomatic Lidp style as
> compared to ACL.
If you want to know functional programming, you want to be able not
only to use reduce, sometimes called fold, but also to define similar
"higher order" functions for yourself.
They package patterns of recursion in a reusable form. It's called
abstraction. It's good.
arnuld <sunr...@invalid.address> writes:
> I thought recursion was CL's basic paradigm (ACL says its functional > programming). I searched a lot on CLL archives but I couldn't find anyone > claiming that PCL teaches more idiomatic Lidp style as compared to ACL.
I will claim that. PCL is about Common Lisp, and ANSI Common Lisp is
about a Platonic Lisp, (reluctantly) using Common Lisp as the
implementation language. Paul Graham is not a fan of Common Lisp, and I
think it shows in ACL.
> I will claim that. PCL is about Common Lisp, and ANSI Common Lisp is
> about a Platonic Lisp, (reluctantly) using Common Lisp as the
> implementation language. Paul Graham is not a fan of Common Lisp, and I
> think it shows in ACL.
I agree with that, however I do think ACL is a lovely book to read in the way SICP or AMOP or K&R are lovely books to read, for instance (I don't want to make some claim of which one is better or anything silly): there's a lot of understanding to be had from them. PCL may be the same: I have not read it so carefully, though it did not make the impression on me that ACL did, which may solely be because I'm more jaded now of course, in any case please don't take this as implying I don't like PCL or think ACL is better or anything.
> 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 ?
No. You need TWO tests here:
one for CAR (contents of list)
another for CDR (list structure)
This would give you four cases to implement, but you can simplify this by checking whether list itself is empty, then there are only three cases.
In general, I think you should have picked an idiom of checking empty list case first.
> That seems more like production/industrial/real-life code as compared to
> ACL exercise which looks more like academic code to me.
Arguably even more industrial:
(loop for x in list
when x
summing x)
> I thought recursion was CL's basic paradigm
Recursion is widely used to implement list processing algorithms because it's quite natural for this task. List processing, however, is a tiny part of CL, and CL isn't better at recursion than pretty much any other language. But it's worse than functional languages like Scheme and Haskell because they guarantee tail-call optimization while CL does not.
So it's not a 'CL's basic paradigm'.
> (ACL says its functional programming).
Modern functional programming is mostly about higher-order functions.
CL is somewhat better than, say, C as it supports lexical closures, but it doesn't provide much more features than, say, Python or JavaScript.
If you're into functional programming it's better to check Scheme (SICP) and Haskell. Maybe something like Ocaml.
CL which differentiate CL from other languages are CLOS, macros, non-local control transfers with signal, restart etc.
> I searched a lot on CLL archives but I couldn't find anyone
> claiming that PCL teaches more idiomatic Lidp style as compared to ACL.
It's hard to say what is idiomatic Lisp style because it's a freaking old language and there are many styles. But PCL definitely shows you more of a modern CL style just because it's written much later and it's not a textbook but a book about writing practical applications.
You can also find some good CL style in PAIP -- it's rather old, but Peter Norvig is a freaking genius.
On 2011-12-16, arnuld <sunr...@invalid.address> wrote:
>> On Wed, 14 Dec 2011 13:46:47 +0000, Tamas Papp wrote:
>> This [reduce-based summit function] 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.
> I thought recursion was CL's basic paradigm (ACL says its functional > programming).
Note that REDUCE is still purely functional, and it appears in purely
functional languges, under different names like "fold", "left-fold",
"fold-left", "inject", etc, or denoted by some cryptic operator glyph.
It might not be implemented recursively, but you can't tell.
You don't have to write explicit recursion to do functional programming.
Recursion over basic building blocks like CAR and CDR is very low-level
functional programming.
In Common Lisp, you can throw away functional purity if it's inconvenient or
inefficient in the implementation, yet write a module which has a functional
API.
Uses of loop are not necessarily imperative. For instance:
(loop for x below 10 summing x)
This is purely functional, to me. The imperative-ness will reveal itself if
you create lexical closures in the loop body.
;; collect 10 functions that return x, then pass
;; through mapcar #'funcall to call them all
(mapcar #'funcall (loop for x below 10 collecting (lambda () x)))
-> (10 10 10 10 10 10 10 10 10 10)
Oops! This tells us something we already know: that there is actually only one
X. We made ten lexical closures in different iterations of the loop, but they
all captured the same X, which means that loop works by instantiating a single
variable X and incrementing it.
> I do think ACL is a lovely book to read in the way SICP or AMOP or K&R > are lovely books to read
Agreed entirely. I found it very enjoyable in exactly the same way. I wouldn't recommend it as a tutorial to anyone who didn't already have a good grounding in programming - I read it after reading SICP and K&R for example.
For a beginner's intro to the lisp family of languages it's hard to beat _The Little Schemer_ & _The Seasoned Schemer_ imho. For a practical, hands-on, nuts and bolts approach to *common lisp* PCL is excellent. For something a bit more entertaining and engaging, _Land of Lisp_ is great.
Tamas Papp wrote:
> 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:
> > 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
Disclaimer:
This version does repeat the (car list) form, but it makes the intent clearer. Besides, a reasonable compiler should be able to handle the common expression. In the worst case, CAR is always pretty fast...
> Disclaimer:
> This version does repeat the (car list) form, but it makes the intent > clearer. Besides, a reasonable compiler should be able to handle the > common expression. In the worst case, CAR is always pretty fast...
That's not it's only problem.
(defun summit3 (l)
(labels ((s3a (ll a)
(cond ((null ll)
a)
((numberp (first l))
(s3a (rest ll) (+ a (first ll))))
(t
(s3a (rest ll) a)))))
(s3a l 0)))
Or, if you want to go mad
(defun summit4 (l)
(labels ((s4a (ll a)
(if (null ll)
a
(destructuring-bind (f . r) ll
(s4a r (if (numberp f) (+ a f) a))))))
(s4a l 0)))
Tamas Papp wrote:
> 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:
> > 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
Tamas Papp wrote:
> 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:
> > 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
Tamas Papp wrote:
> 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:
> > 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
