ACL - Chpater 2, Exercise 9

[arnuld]

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 ?








--
arnuld
http://LispMachine.Wordpress.com

[Frank DG1SBG]

I'll answer this by showing another version of #'summit:

(defun summit (list)
(apply #'+ (remove nil list)))

Q: Which of the problems you stated are solved by this version?

This version still has some disadvantages which the following version
avoids:

(defun summit (list)
(apply #'+ (remove-if-not #'numberp list)))

Q: Which disadvantages have been cleared by this version ?

Q: Which problems are still present in this last version ?

Hth!

Frank

[Tamas Papp]

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

[Don Geddis]

arnuld <sun...@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.

[Barry Margolin]

In article <4ee897c4$0$288$1472...@news.sunsite.dk>,

arnuld <sun...@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:
>
> 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))

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 ***

[arnuld]

> 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:
>>
>> 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 ?
>>

> 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

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
http://LispMachine.Wordpress.com

[Jussi Piitulainen]

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
> >
> > (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
>
> That seems more like production/industrial/real-life code as
> compared to ACL exercise which looks more like academic code to me.

Nothing un-academic in it.

> > 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.

[Zach Beane]

arnuld <sun...@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.

Zach

[Tim Bradshaw]

On 2011-12-16 14:25:13 +0000, Zach Beane said:

> 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.

[Alex Mizrahi]

> 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.

[Alex Mizrahi]

> 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.

Also check some good modern libraries.

[Kaz Kylheku]

On 2011-12-16, arnuld <sun...@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.

However, it's not obvious in many uses of loop.

[Raffael Cavallaro]

On 2011-12-16 15:34:06 +0000, Tim Bradshaw said:

> 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.

warmest regards,

Ralph

--
Raffael Cavallaro

[WJ]

MatzLisp:

summit = lambda{|list| list.compact.reduce( :+ )}

summit[ [1,nil,3,5,7,9,11] ]

===> 36

[Kaz Kylheku]

On 2012-02-17, WJ <w_a_...@yahoo.com> wrote:
> MatzLisp:
>
> summit = lambda{|list| list.compact.reduce( :+ )}
>
> summit[ [1,nil,3,5,7,9,11] ]

TXR Lisp:

[apply + (flatten '(1 nil 3 5 7 9 11))]

Ruby is designed by fucking imbeciles.

[tar...@google.com]

Agreed.
I think for ease of seeing the algorithm and incorporating all of the suggestions, a good version would be

(defun summit2 (list)
(cond ((null list) 0)
((numberp (car list)) (+ (car list) (summit2 (cdr list))))
(t (summit2 (cdr list)))))


(summit2 '(1 2 nil 3 a 4)) ==> 10

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...

[Tim Bradshaw]

On 2012-02-17 18:50:17 +0000, tar...@google.com said:

> (defun summit2 (list)
> (cond ((null list) 0)
> ((numberp (car list)) (+ (car list) (summit2 (cdr list))))
> (t (summit2 (cdr list)))))
>
>
> (summit2 '(1 2 nil 3 a 4)) ==> 10
>
> 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)))

[Tim Bradshaw]

On 2012-02-18 13:57:24 +0000, Tim Bradshaw said:

> That's not it's only problem.

Argh.

[WJ]

NewLisp:

(define (summit lst)
(apply + (replace nil lst)))

[WJ]

Clojure:

user=> (reduce #(if %2 (+ %1 %2) %1) 0 '(1 nil 2 3))
6

[WJ]

Racket:

(for/sum ([i '(1 nil 2 3)] #:when (number? i)) i) ; 6

(for/sum ([i #(1 nil 2 3)] #:when (number? i)) i) ; 6

[WJ]

Gauche Scheme:

(define (summit seq)
(fold (^(x sum) (+ sum (if x x 0))) 0 seq))

(summit '(1 3 5 7 #f 9))
===>
25

[WJ]

MatzLisp (Ruby):

def summit seq
seq.reduce(0){|sum,x| sum + (x or 0)}
end

summit []
==>0
summit [nil]
==>0
summit [nil,1,3,5,7,9]
==>25
summit (0..22)
==>253

--
From the New York Times of October 11, 1991, ... we learn that ... researchers
at Boston University admitted that, "There is no question but that Dr. King
plagiarized in the dissertation." ... "Dr. Martin Luther King, Jr." [Michael
King] spent his last night on Earth having sexual intercourse with two women at
the motel and physically beating and abusing a third. -- K. A. Strom