new to lisp (3rd time lucky)

173 views
Skip to first unread message

Natalia

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
Ok this should be my last question for a while, well
at least until next assignment.

this is my code

(DEFUN ADD-EVEN (L)
   (COND ((NULL L) 0 )
         ((typep (FIRST L) 'INTEGER)
          (IF (evenp (FIRST L)) (+ (FIRST L) (ADD-EVEN (REST L)) )
              (+ 0 (ADD-EVEN (REST L)) )
          )
         )
         (T (+ 0 (ADD-EVEN(REST L) )) )
   )
)

What it is supposed to do is to go through a multi level list and
add up all the even numbers so that if the input is
(a b c d 4 5 6 (a b 3 4 ) (2 b g))
it will return 16
my program is only looking at one level in the list
so that with that input it will return only 10
how do i get it to add even numbers on all levels?
lisp is frying my brain, i think i will stick to
subjects that program in c from now on.

thanks for any clues
N. :)

Jon Haugsand

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
* na...@one.net.au

> (DEFUN ADD-EVEN (L)
> (COND ((NULL L) 0 )
> ((typep (FIRST L) 'INTEGER)
> (IF (evenp (FIRST L)) (+ (FIRST L) (ADD-EVEN (REST L)) )
> (+ 0 (ADD-EVEN (REST L)) )
> )
> )
> (T (+ 0 (ADD-EVEN(REST L) )) )
> )
> )
>
> What it is supposed to do is to go through a multi level list and
> add up all the even numbers so that if the input is
> (a b c d 4 5 6 (a b 3 4 ) (2 b g))
> it will return 16

Here is a quick and not-so-dirty solution. Add the following clause to
your COND-list:

((listp (FIRST L)) (+ (ADD-EVEN ..) (ADD-EVEN ..)))

As this looks like an assignment, perhaps you can fill in the ...
yourself? :)

--
Jon Haugsand
Norwegian Computing Center, <http://www.nr.no/engelsk/>
<mailto:Jon.Ha...@nr.no> Pho: +47 22852608 / +47 22852500,
Fax: +47 22697660, Pb 114 Blindern, N-0314 OSLO, Norway

Martti Halminen

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
Natalia wrote:

> (DEFUN ADD-EVEN (L)
> (COND ((NULL L) 0 )
> ((typep (FIRST L) 'INTEGER)
> (IF (evenp (FIRST L)) (+ (FIRST L) (ADD-EVEN (REST
> L)) )
> (+ 0 (ADD-EVEN (REST L)) )
> )
> )
> (T (+ 0 (ADD-EVEN(REST L) )) )
> )
> )
>
> What it is supposed to do is to go through a multi level list
> and
> add up all the even numbers so that if the input is
> (a b c d 4 5 6 (a b 3 4 ) (2 b g))
> it will return 16

> my program is only looking at one level in the list
> so that with that input it will return only 10
> how do i get it to add even numbers on all levels?

how about changing that last branch to

(T (+ (add-even (first L))
(ADD-EVEN(REST L))))

?
- this would require also adding a branch to handle the case
where L isn't a list, or alternately writing this as a separate
branch to handle lists.

Another brute-force approach would be to first flatten the list,
and call your function on that.

> lisp is frying my brain, i think i will stick to
> subjects that program in c from now on.

If you played with lisp a little more, you'd probably notice
that it is usually
easier to program in than C, for most things that you can do in
C, unless you're doing really close-to-the-machine
bit-twiddling.
Whether this would make you any happier is another question.

--

Fernando D. Mato Mira

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
Natalia wrote:

> What it is supposed to do is to go through a multi level list and
> add up all the even numbers so that if the input is
> (a b c d 4 5 6 (a b 3 4 ) (2 b g))
> it will return 16

* (collect-sum (choose-if #'(lambda (x) (and (numberp x) (evenp x)))
(scan-lists-of-lists-fringe '(a b c
d 4 5 6 (a b 3 4 ) (2 b g)))))

16

;->

--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720

www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html


Michael Kappert

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to

Natalia wrote:

> Ok this should be my last question for a while, well
> at least until next assignment.
>
> this is my code
>

> (DEFUN ADD-EVEN (L)
> (COND ((NULL L) 0 )
> ((typep (FIRST L) 'INTEGER)
> (IF (evenp (FIRST L)) (+ (FIRST L) (ADD-EVEN (REST L)) )
> (+ 0 (ADD-EVEN (REST L)) )
> )
> )
> (T (+ 0 (ADD-EVEN(REST L) )) )
> )
> )
>

> What it is supposed to do is to go through a multi level list and
> add up all the even numbers so that if the input is
> (a b c d 4 5 6 (a b 3 4 ) (2 b g))
> it will return 16

> my program is only looking at one level in the list
> so that with that input it will return only 10
> how do i get it to add even numbers on all levels?

> lisp is frying my brain

It's not Lisp, it's recursion ;-)

How do you add the even number of a nested list using recursion?
- If the list is empty we are done, the sum is 0.
- If the list isn't empty, suppose we have a function that adds
the even numbers of the rest of the list. Having computed the
sum of the rest, we need only take care of the head of the list.
[Note that the second element in the current list is the head of
the rest we just took care of. And the third element?]
- if the head is an even number, add it to the rest.
- if it's a list itself (a "new level"),
add the *sum of the even numbers of this list* to the rest.
- otherwise, add nothing.

So for the purpose of showing how the recursion goes, i'd prefer this definition
of add-even:

(defun add-even (l)
(if (null l) 0 ; empty list: we're done.
(let ((rest-sum (add-even (rest l)))) ; list isn't empty. add even numbers
; of the rest...
(+ rest-sum ; and add something to that sum
(cond ;
((and (numberp (first l))
(evenp (first l))) ; head is an even number?
(first l)) ; -> add that number.
((listp (first l)) ; head is a list?
(add-even (first l))) ; -> add sum of even numbers of head.
(T 0)))))) ; otherwise add nothing.


Hope that help

Michael

--
Michael Kappert
Fraunhofer IITB
Fraunhoferstr. 1 Phone: +49(0)721/6091-477
D-76131 Karlsruhe, Germany EMail: k...@iitb.fhg.de

Tim Bradshaw

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
* Natalia wrote:
> lisp is frying my brain, i think i will stick to
> subjects that program in c from now on.

I think *recursion* is frying your brain, not Lisp.

I always like to give impossibly difficult to understand answers to
these questions, and since you've already got a reasonable answer,
I'll give an insane one here. If you understand this you understand
Lisp and recursion reasonably well I think (someone will now point out
it's buggy I expect). Note that although RECURSE-OVER is written in a
deliberately silly way, the idea of a general recurser function is
quite useful.

(defun recurse-over (object node-test node-function child-test mapper)
;; call NODE-FUNCTION on every node of object (including OBJECT)
;; that passes NODE-TEST. CHILD-TEST tests for children, MAPPER maps
;; over a node with children.
(let ((f #'(lambda (o c)
(when (funcall node-test o)
(funcall node-function o))
(when (funcall child-test o)
(funcall mapper #'(lambda (e)
(funcall c e c))
o)))))
(funcall f object f)))


(defun sum-evens (nested-list)
(let ((sum 0))
(recurse-over nested-list
#'(lambda (e)
(and (numberp e) (evenp e)))
#'(lambda (e)
(setf sum (+ sum e)))
#'listp
#'mapc)
sum))

--tim

Thom Goodsell

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
Natalia,

There've been several good code suggestions, but let me outline what
your problem is, maybe that will help. Basically you have three cases
for any input:
1. It's a null list => 0
2. The first is an integer
a. It's even => (+ (first L) (add-even (rest L)))
b. It's odd => (add-even (rest L))
3. None of the above => (add-even (rest L))

What happens when you have the following as the input (it's one of the
calls you'll see if you trace your function on the input you gave)?
((a b 3 4) (2 b g))

It's not case 1, nor case 2, so that means it's case 3. Do you really
want to just call add-even on the rest of the list and ignore the first?

I hope this helps.

Thom


Natalia wrote:
>
> Ok this should be my last question for a while, well
> at least until next assignment.
>
> this is my code
>
> (DEFUN ADD-EVEN (L)
> (COND ((NULL L) 0 )
> ((typep (FIRST L) 'INTEGER)
> (IF (evenp (FIRST L)) (+ (FIRST L) (ADD-EVEN (REST L)) )
> (+ 0 (ADD-EVEN (REST L)) )
> )
> )
> (T (+ 0 (ADD-EVEN(REST L) )) )
> )
> )
>
> What it is supposed to do is to go through a multi level list and
> add up all the even numbers so that if the input is
> (a b c d 4 5 6 (a b 3 4 ) (2 b g))
> it will return 16
> my program is only looking at one level in the list
> so that with that input it will return only 10
> how do i get it to add even numbers on all levels?

> lisp is frying my brain, i think i will stick to
> subjects that program in c from now on.
>

Thom Goodsell

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
Damn, I love Lisp!

Thom


Tim Bradshaw wrote:


>
> * Natalia wrote:
> > lisp is frying my brain, i think i will stick to
> > subjects that program in c from now on.
>

Johan Kullstam

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
Natalia <na...@one.net.au> writes:

> Ok this should be my last question for a while, well
> at least until next assignment.
>
> this is my code
>
> (DEFUN ADD-EVEN (L)
> (COND ((NULL L) 0 )
> ((typep (FIRST L) 'INTEGER)
> (IF (evenp (FIRST L)) (+ (FIRST L) (ADD-EVEN (REST L)) )
> (+ 0 (ADD-EVEN (REST L)) )
> )
> )
> (T (+ 0 (ADD-EVEN(REST L) )) )
> )
> )
>
> What it is supposed to do is to go through a multi level list and
> add up all the even numbers so that if the input is
> (a b c d 4 5 6 (a b 3 4 ) (2 b g))
> it will return 16
> my program is only looking at one level in the list
> so that with that input it will return only 10
> how do i get it to add even numbers on all levels?

if you've had to write that old canard "flatten" in a previous
exercise, it's time to use that. if not, write one now. (damn the
consing; full speed ahead!) this is how people tend to use lisp --
rather than write a long function that does everything, you write a
bunch of simple little functions that do each step. lisp is good at
handling aggregate data (lists, arrays &c). play to the strength of
lisp -- make your functions handle aggregates if possible.

for example (i haven't checked this sketch out for syntax errors but
i hope you get the idea)

(defun add-even-list (lyst)
"return sum of even elements in a flat list."
(let ((sum 0))
(mapcar (lambda (x)
(when (and (typep x 'integer)
(evenp x))
(incf sum x)))
lyst)
sum))

(defun add-even (tree)
"return sum of even elements in a nested list."
(add-even-list (flatten tree)))

now all you need is flatten and mapcar. notice how functions are
doing the work instead of variables. notice how mapcar attacks the
whole list in one shot. a lot of lisp programming consists of
converting your data into a format convenient for applying some
sledge-hammer function which works upon an aggregate rather than
individuals. (for a more interative, C-like, approach, you could also
use dolist instead of mapcar.)

> lisp is frying my brain, i think i will stick to
> subjects that program in c from now on.

lisp fried my brain while learning it too.

this is because

1) lisp works backwards from your "traditional" language like C. lisp
is not unnatural; in fact, it's more intuitive. but it will only
seem so if you've not been exposed to C or after unlearning C ways
of thinking.

at the risk of oversimplification, let me say this. in lisp you
start with functions -- then you start defining a few variables.
in C you start by defining variables and assigning types -- then
you create some functions. this new way of thinking takes a little
bit (or a lot in my case) of getting used to.

2) the lisp which your professor is allowing is horribly truncated,
crippled and limited. all you get to experience are the painful
aspects of lisp. no one does much recursive list consing by hand
since there are useful functions and macros like mapcar, push and
loop. i mean really, what kind of lisp doesn't have mapcar?

> thanks for any clues
> N. :)

--
johan kullstam l72t00052

Donald Fisk

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to

Natalia wrote:

> Ok this should be my last question for a while, well
> at least until next assignment.
>
> this is my code
>
> (DEFUN ADD-EVEN (L)
> (COND ((NULL L) 0 )
> ((typep (FIRST L) 'INTEGER)
> (IF (evenp (FIRST L)) (+ (FIRST L) (ADD-EVEN (REST L)) )
> (+ 0 (ADD-EVEN (REST L)) )
> )
> )
> (T (+ 0 (ADD-EVEN(REST L) )) )
> )
> )
>
> What it is supposed to do is to go through a multi level list and
> add up all the even numbers so that if the input is
> (a b c d 4 5 6 (a b 3 4 ) (2 b g))
> it will return 16
> my program is only looking at one level in the list
> so that with that input it will return only 10
> how do i get it to add even numbers on all levels?

> lisp is frying my brain, i think i will stick to
> subjects that program in c from now on.

That is perhaps because you're still thinking in C.
You're formatting ( and ) as if they're { and }

Let's tidy up your code. No right parens on their
own lines, all lower case, redundant (+ 0 x) removed:

(defun add-even (l)
(cond ((null l) 0)
((and (typep (first l) 'integer)
(evenp (first l)))
(+ (first l) (add-even (rest l))))
(t (add-even (rest l)))))

It's not a bad first attempt. Now that it's properly
formatted, it's a bit easier to see where you're going
wrong.

You have to recurse on both the tail *and the head*
of the list. This is straightforward because in
Lisp, lists are really binary trees.

To do this, handle cases where l is an atom.

You also need to add (add-even (first l)) to
(add-even (rest l)) when l is a list.

One more thing, you say you find things easier in C.
Could this be because the problems you have been
getting to do in C have been simpler? Try writing
the same algorithm in C and see whether it's still
easier than Lisp.

Le Hibou (ma propre opinion)

--
"There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies and the
other way is to make it so complicated that there are no obvious
deficiencies." -- CAR Hoare

Erik Naggum

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
* Natalia <na...@one.net.au>

| lisp is frying my brain, i think i will stick to
| subjects that program in c from now on.

well, take it from an old hand: the only reason it would be easier to
program in C is that you can't easily express complex problems in C, so
you don't. I have 17 years of C programming experience, and I'm damn
good at it, but that's also _why_ I program in Common Lisp. but perhaps
you need a few years of C programming to appreciate better languages -- I
have repeatedly said that programmers graduate into Common Lisp as they
tire of inferior languages. however, getting too good at something that
is not good for you is _really_ bad for you, as it means you'll have to
accept a temporary reduction in living standards if you switch, and lots
of hard work on the side with little or no pay if you decide to combine
the two. therefore, another saying: life is too long to be good at C/C++.

it is probably C that _has_ fried your brain, by the way. not that this
will comfort you or anything, but note that if you are used to C, the
utter pointlessness of most of the exercises in recursion that Lisp and
Scheme teachers tend to push on unsuspecting students become so glaringly
visible that you would never even think of recursion again, even when it
is clearly the best solution. this doesn't mean that recursion is bad,
it only means that iteration is better in a lot of cases where recursion
adds nothing to the understanding of the task at hand. the lesson to be
learned from this is that giving exercises in the proper use of recursion
is much harder than giving lessons in the proper use of iteration, and
indeed requires a much deeper understanding of the problems for which
recursion is the optimal solution, both in terms of what you describe to
the intelligent programmer and what you execute on the hardware.

e.g., in your current problem, it is obviously a lot smarter to iterate
over a list than to recurse over it (despite what your teachers may tell
you about the "instructiveness" of such endeavors), yet you must recurse
if and when the element in the list is itself a list, and that's the
valuable part of the exercise.

#:Erik

dlin...@my-deja.com

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to

That one is definitely going into the utilities file!!
Very nice.
Dave Linenberg
In article <ey3d7ok...@cley.com>,


Tim Bradshaw <t...@cley.com> wrote:
> I always like to give impossibly difficult to understand answers to
> these questions, and since you've already got a reasonable answer,

> I'll give an insane one here......


Sent via Deja.com http://www.deja.com/
Before you buy.

Tom Breton

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
Johan Kullstam <kull...@ne.mediaone.net> writes:

>
> lisp fried my brain while learning it too.
>
> this is because
>
> 1) lisp works backwards from your "traditional" language like C. lisp
> is not unnatural; in fact, it's more intuitive. but it will only
> seem so if you've not been exposed to C or after unlearning C ways
> of thinking.

Not always. I came to Lisp after mostly doing C/C++, and I fell in
love with Lisp almost immediately.

--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Rethink some Lisp features, http://world.std.com/~tob/rethink-lisp/index.html

Janos Blazi

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
> the lesson to be
> learned from this is that giving exercises in the proper use of
recursion
> is much harder than giving lessons in the proper use of iteration, and
> indeed requires a much deeper understanding of the problems for which
> recursion is the optimal solution, both in terms of what you describe to

Though I agree with that, I'd like to point out that it is hardly possible
in practical teaching to give exercises in which recursion is used properly.
Even if I had the understanding: the examples that come to my mind
(manipulating trees, quick sort, or even parsers) are to complicated. I
teach at a high school but the situation ist not very different at
university level either: I saw this when I studied CS. Many people need a
long time to reach the level where such 'real life' execises can be given
and many pupils or students never reach that level. Many students study CS
and Economy for example. And they have to learn about recursion. It seems at
the moment that they can only get a glimpse of what recursion is and have to
do those wrtificial execises.

So I do not see any solution for this problem.
J.B.


-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----

Christopher R. Barry

unread,
Mar 24, 2000, 3:00:00 AM3/24/00
to
"Janos Blazi" <jbl...@netsurf.de> writes:

[...]

> Though I agree with that, I'd like to point out that it is hardly possible
> in practical teaching to give exercises in which recursion is used properly.
> Even if I had the understanding: the examples that come to my mind
> (manipulating trees, quick sort, or even parsers)

[...]

I think quicksort is just at the right level for someone ready to be
introduced to recursion. I also think you underestimate CS students.
CS students--majors at least--should be smart, have much better than
average problem solving skills, and be able to understand something
like quicksort and recursion very early on in their education;
certainly during their first CS course.

When defining quicksort for them, don't use pseudo-code or actual code
or anything, just give them a definition like this:

1. Begin to partition the set to be sorted into two subsets by choosing
an element in the set. Everything less than this element will
be grouped in one subset, and everything greater than or equal to
this element will be grouped in the other subset.

2. After applying (1) to the set, if either subset has more than one
element, then apply (1) and (2) to that subset.

Then make them take out a pencil and sheet of paper and put some sets
on the board using the math notation they are familiar with like
{9 4 3 7 8 8 1} and make them work a few out. That should do it.

Christopher

Janos Blazi

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
> I think quicksort is just at the right level for someone ready to be
> introduced to recursion. I also think you underestimate CS students.
> CS students--majors at least--should be smart, have much better than
> average problem solving skills, and be able to understand something
> like quicksort and recursion very early on in their education;
> certainly during their first CS course.

That would be very unusual in Germany. I do not quite understand, what
'major' means, I think it is a degree and you mean students whos main
subject is CS. But there are other students who study CS too and no
university can afford to offer different courses for CS majors and students
whos main subject is Economy (for example). So the level is low.

>
> When defining quicksort for them, don't use pseudo-code or actual code
> or anything, just give them a definition like this:
>
> 1. Begin to partition the set to be sorted into two subsets by choosing
> an element in the set. Everything less than this element will
> be grouped in one subset, and everything greater than or equal to
> this element will be grouped in the other subset.
>
> 2. After applying (1) to the set, if either subset has more than one
> element, then apply (1) and (2) to that subset.
>
> Then make them take out a pencil and sheet of paper and put some sets
> on the board using the math notation they are familiar with like
> {9 4 3 7 8 8 1} and make them work a few out. That should do it.
>

Maybe that would do on the best US universities but it would not do in
Germany. (But of course there a brillant students and I am not talking about
these.)
A few years ago at a German university the students had to write a Pascal
program at home (maybe 300-400 lines). This was consodered as they final
topnotch excersie. When they handed in the programs, half of them had
compile time errors in them!

Jon Haugsand

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
* Janos Blazi

> Though I agree with that, I'd like to point out that it is hardly possible
> in practical teaching to give exercises in which recursion is used properly.
> Even if I had the understanding: the examples that come to my mind
> (manipulating trees, quick sort, or even parsers) are to complicated. I
> teach at a high school but the situation ist not very different at
> university level either: I saw this when I studied CS. Many people need a
> long time to reach the level where such 'real life' execises can be given
> and many pupils or students never reach that level. Many students study CS
> and Economy for example. And they have to learn about recursion. It seems at
> the moment that they can only get a glimpse of what recursion is and have to
> do those wrtificial execises.

I have always thought that the Tower of Hanoi is the best recursion
problem ever, for the following reasons:

1. It is easy to understand the problem.
2. It is quite easy to understand the recursive solution.
3. Students at graduate school level can play with the problem with
plastic/wood pieces.
4. Non-recursive solutions are obscure.
5. It has this ancient mystique linking our civilazation to the old
ones that we in the west love to be reminded on...

However, this may turn into a "What is the most pedagogic recursion
problem?" discussion. :)

Reini Urban

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
Tim Bradshaw wrote:
>I always like to give impossibly difficult to understand answers to
>these questions, and since you've already got a reasonable answer,
>I'll give an insane one here. If you understand this you understand
>Lisp and recursion reasonably well I think (someone will now point out
>it's buggy I expect). Note that although RECURSE-OVER is written in a
>deliberately silly way, the idea of a general recurser function is
>quite useful.
>
> (defun recurse-over (object node-test node-function child-test mapper)
> ;; call NODE-FUNCTION on every node of object (including OBJECT)
> ;; that passes NODE-TEST. CHILD-TEST tests for children, MAPPER maps
> ;; over a node with children.
> (let ((f #'(lambda (o c)
> (when (funcall node-test o)
> (funcall node-function o))
> (when (funcall child-test o)
> (funcall mapper #'(lambda (e)
> (funcall c e c))
> o)))))
> (funcall f object f)))

Now where did I see this before?
Is it "On Lisp", "SICP" or Tim alone. My tip is On Lisp

(without the test functions of course and for nested lists only.)
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html

Reini Urban

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
Janos Blazi wrote:
>> I think quicksort is just at the right level for someone ready to be
>> introduced to recursion. I also think you underestimate CS students.
>> CS students--majors at least--should be smart, have much better than
>> average problem solving skills, and be able to understand something
>> like quicksort and recursion very early on in their education;
>> certainly during their first CS course.
>
>That would be very unusual in Germany. I do not quite understand, what
>'major' means, I think it is a degree and you mean students whos main
>subject is CS. But there are other students who study CS too and no
>university can afford to offer different courses for CS majors and students
>whos main subject is Economy (for example). So the level is low.

>[quicksort snipped]

>Maybe that would do on the best US universities but it would not do in
>Germany. (But of course there a brillant students and I am not talking about
>these.)
>A few years ago at a German university the students had to write a Pascal
>program at home (maybe 300-400 lines). This was consodered as they final
>topnotch excersie. When they handed in the programs, half of them had
>compile time errors in them!

sorry to say that, but stupid austrian students seem to grasp it also.
not only the top US universities. Italy and others will force the same I
guess.

every CS student here has to write some sorts of bugfree and functional
programs which has offers some kind of classical problems, if recursion
ala quick sort or divide and conquer for geometry or such, plus some
advanved data structures. lately even lambda calculus.
also the whole crowd of non-CS students from electronics, economy and
physics, just without the lambda.

but maybe germany is now different. (sorry for the obvious rant). it
could also be just a "fachhochschule" where you learn how to take care
of dusty keyboards, monitors and mouses and do some webdesign
("bunticlicki"), so that german software industry don't have to import
thousands of low-cost indians. (H1B alikes)

Tim Bradshaw

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
* dlinenbe wrote:
> That one is definitely going into the utilities file!!
> Very nice.

I hope not, but just in case, you should at least use the even more
obscure:

(defun recurse-over (object node-test node-function child-test mapper)
;; call NODE-FUNCTION on every node of object (including OBJECT)
;; that passes NODE-TEST. CHILD-TEST tests for children, MAPPER maps
;; over a node with children.

((lambda (f)
(funcall f object f))
#'(lambda (o c)
(and (or (and (funcall node-test o)
(or (funcall node-function o)
t))
t)


(funcall child-test o)
(funcall mapper #'(lambda (e)
(funcall c e c))
o)))))

(I admit this is just gratuitous, and it might even be wrong).

--tim

Tim Bradshaw

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
* Reini Urban wrote:

> Now where did I see this before?
> Is it "On Lisp", "SICP" or Tim alone. My tip is On Lisp

I wouldn't be surprised if it was in on lisp, although I'd hope he
wrote it less weirdly.

--tim

Rolf-Thomas Happe

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
Janos Blazi:

> > the lesson to be
> > learned from this is that giving exercises in the proper use of
> recursion
> > is much harder than giving lessons in the proper use of iteration, and
> > indeed requires a much deeper understanding of the problems for which
> > recursion is the optimal solution, both in terms of what you describe to
>

> Though I agree with that, I'd like to point out that it is hardly possible
> in practical teaching to give exercises in which recursion is used properly.
> Even if I had the understanding: the examples that come to my mind
> (manipulating trees, quick sort, or even parsers) are to complicated. I

Recursively structured data calls for recursive processing, and
there are quite familiar examples of such data, e. g. hierarchical
file systems. Thus, data analysis can motivate recursion. Can it
do this in education, too? Go ask the book

Felleisen/Findler/Flatt/Krishnamurti: How to Design Programs
http://www.cs.rice.edu/CS/PLT/Teaching/Lectures/Released/curriculum/.

There were some related posts around New Year 1999/2000 that you may
want to search in Deja News:

~g comp.lang.scheme ~a shriram ~subject (teaching & recursion)

Or go directly to http://x26.deja.com/getdoc.xp?AN=564933341 .

rthappe

Rolf-Thomas Happe

unread,
Mar 25, 2000, 3:00:00 AM3/25/00
to
I wrote:
> There were some related posts around New Year 1999/2000 that you may
> want to search in Deja News:
>
> ~g comp.lang.scheme ~a shriram ~subject (teaching & recursion)

This should have been ~s ..., sorry.

rthappe

Rahul Jain

unread,
Mar 26, 2000, 3:00:00 AM3/26/00
to
In article <m38zz8n...@world.std.com> posted on Friday, March 24,
2000 1:16 PM, Tom Breton <t...@world.std.com> wrote:

> Johan Kullstam <kull...@ne.mediaone.net> writes:
> Not always. I came to Lisp after mostly doing C/C++, and I fell in
> love with Lisp almost immediately.
>

I experienced a similar situation, going from mostly Java and a bit of C
before college to a class where they taught us in Scheme. While I didn't
really like Scheme, Lisp was exactly the language I had been looking for
to fix all the problems I had with C and Java. I think the difference
between our situations and Natalia's is that we had been programming
in C-like languages long enough to have experienced sufficient
frustration at their deficiencies, while Natalia, I presume, only has had
classroom experience with programming, which is mostly less diverse
in the types of algorithms that you have to use. Specifically, recursion
is not what made me like Lisp, since that's easy enough in C, it was the
powerful typing/OO system and the macro processing system that
wasn't a simple search-and-replace function.

--
-> -\-=-=-=-=-=-=-=-=-=-/^\-=-=-=<*><*>=-=-=-/^\-=-=-=-=-=-=-=-=-=-/- <-
-> -/-=-=-=-=-=-=-=-=-=/ { Rahul -<>- Jain } \=-=-=-=-=-=-=-=-=-\- <-
-> -\- "I never could get the hang of Thursdays." - HHGTTG by DNA -/- <-
-> -/- http://photino.sid.rice.edu/ -=- mailto:rahul...@usa.net -\- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
Version 11.423.999.210020101.23.50110101.042
(c)1996-2000, All rights reserved. Disclaimer available upon request.


William Deakin

unread,
Mar 27, 2000, 3:00:00 AM3/27/00
to
Janos Blazi wrote:

> ...I do not quite understand, what 'major' means...

It is a senior officer rank in the British and American Army and a surname such
as of the last Prime Minister of the previous UK government. As an example, both
of these are used to good effect in the name Major Major, an important
character in the book `Catch 22.'

Best Regards,

;) will


Kragen Sitaker

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to
In article <31629015...@naggum.no>, Erik Naggum <er...@naggum.no> wrote:
> however, getting too good at something that
> is not good for you is _really_ bad for you, as it means you'll have to
> accept a temporary reduction in living standards if you switch, and lots
> of hard work on the side with little or no pay if you decide to combine
> the two.

This is why I am typing this on a QWERTY keyboard.

> it is probably C that _has_ fried your brain, by the way. not that this
> will comfort you or anything, but note that if you are used to C, the
> utter pointlessness of most of the exercises in recursion that Lisp and
> Scheme teachers tend to push on unsuspecting students become so glaringly
> visible that you would never even think of recursion again, even when it
> is clearly the best solution.

What do you think of the use of recursion in Friedman et al.'s
_Essentials of Programming Languages_? I'm not sure if this book is
really intended to teach recursion to people who don't understand it,
but some of the wording does seem to imply that it is.

The exercises in using recursion to e.g. produce a normal-order
lambda-calculus expression evaluator seemed much more compelling to me
than SICP's exercises in using recursion to do arithmetic.
--
<kra...@pobox.com> Kragen Sitaker <http://www.pobox.com/~kragen/>
The Internet stock bubble didn't burst on 1999-11-08. Hurrah!
<URL:http://www.pobox.com/~kragen/bubble.html>
The power didn't go out on 2000-01-01 either. :)

Peter Norvig

unread,
Mar 31, 2000, 3:00:00 AM3/31/00
to
In my experience, recursions with tests like (if (evenp (first l))) are
usually not the right way to do it. Instead of thinking about the input
being a list, and about what the components of the list might be, think
about all the possible inputs, both list and non-list. Then you get:

* If the input is an even number, then the sum is that number
* If the input is a list,
then the sum is the sum of the first plus the sum of the rest
* Otherwise (either an odd number or anything else) the sum is zero

So you end up with

(defun add-even (x)
(cond ((and (integerp x) (evenp x)) x)
((consp x) (+ (add-even (first x)) (add-even (rest x))))
(t 0)))

Reply all
Reply to author
Forward
0 new messages