Greetings,
I have a list of n*n numbers and I was wondering what is the most
elegant way to get a new list out of this with n numbers, 1st number
beeing the sum of numbers on positions 0, n, ..., n*(n-1), 2nd number
beeing the sum of numbers on positions 1, n+1, ..., n*(n-2) and so
forth.
I am beginner at lisp and I can do it in the classical way with do...
and indices in a loop but was wondering if there is a smarter approach
in lisp.
Thanks,
Andrei
From: Kent M Pitman
Subject: Re: newbie question : summing elements in a list
Date:
Message-ID: <uhdj9ba9o.fsf@nhplace.com>
·······@mail.dntis.ro writes:
> Greetings,
>
> I have a list of n*n numbers and I was wondering what is the most
> elegant way to get a new list out of this with n numbers, 1st number
> beeing the sum of numbers on positions 0, n, ..., n*(n-1), 2nd number
> beeing the sum of numbers on positions 1, n+1, ..., n*(n-2) and so
> forth.
>
> I am beginner at lisp and I can do it in the classical way with do...
> and indices in a loop but was wondering if there is a smarter approach
> in lisp.
Sounds like more than just a newbie question. Is this homework? Homework
MUST be identified as such up front so that we don't accidentally do what
someone should do for themselves. The right thing is to tell us what is
assigned and then what you have tried and where you fell short, and then we
can help nudge you along...
I mention this because it's a subjective judgment that 'do' is not elegant.
If you want to sum the elements of a[j] for j from 1 to 10, I don't see
why
(loop for i below 10 sum (aref a i))
is not the most elegant way to describe the answer. If you found in a
math book with a nice sigma and subscripts and all, it would look quite
elegant. The notion that do loops are inelegant is an idea you should
unlearn immediately.
That's not to say that it's not useful to know multiple ways to do something,
but please understand that 'recursion' and 'elegance' are not synonymous,
nor are 'iteration' and 'ugliness'.
Moreover, while Lisp is a language that allows recursion, it is not a
place that recursion is required nor even always encouraged.
Recursive solutions can use stack and you can run out of stack. Note
that the Scheme language defines that tail recursion will not create
extra stack, but Common Lisp makes no such provision. As such, Scheme
users are taught that recursion is just another syntax for iteration,
and often erroneously taught that the iteration constructs are to be
eschewed. Not so in CL, where recursion and iteration are
technologically different. Thinking falsely that using up stack in
Lisp and risking a stack overflow is somehow either 'macho' or 'elegant'
is just plain silly, therefore.
In my personal view, the right solution for Common Lisp, if anything
can ever be reduced tto a simple rule of thumb, is "iterate into the
cdr and recurse on the car". It's a statistical accident of typical
data structure layout that 'length' to the cdr side [the side toward
which lists are biased in structure to grow unboundedly] is deeper
than the 'length' to the car side (usually called 'depth'). Depth
rarely grows unbounded, in part because Lisp programmers [in contrast
to the myth about them] don't like all the parentheses that result
from such a layout... In practice, depth usually grows (if "usually"
can be said to have any meaning in such a broad generalization as I'm
making) in something that feels more logarithmic a way, and rarely tempts
the stack to overflow.
Thank you for replying to my question.
I didn't know the homework rule, sorry for not mentioning this detail.
The story goes like this : I have to write as homework for a lisp
course a program that verifies that a list of nxn elements is a magic
square or not and as a 2nd part generate all unique magic squares of
dimension nxn. Now : the biggest problem I have is that we have been
introduced only to a limited number of lisp functions (like dotimes,
dolist for loops let and a few more others, but nothing close to 'loop
for i below...' code above which I find extremly nice) and using only
those shown will produce neanderthal-looking code. What I was looking
really was hints on how to write simple lisp code, I wasn't necessarily
looking for recursion in my original question but for more efficient
things like that array expression - we haven't even been introduced to
arrays btw - and this is frustrating.
Thanks again,
Andrei
·······@mail.dntis.ro writes:
> Thank you for replying to my question.
>
> I didn't know the homework rule, sorry for not mentioning this detail.
> The story goes like this : I have to write as homework for a lisp
> course a program that verifies that a list of nxn elements is a magic
> square or not and as a 2nd part generate all unique magic squares of
> dimension nxn. Now : the biggest problem I have is that we have been
> introduced only to a limited number of lisp functions (like dotimes,
> dolist for loops let and a few more others, but nothing close to 'loop
> for i below...' code above which I find extremly nice) and using only
> those shown will produce neanderthal-looking code. What I was looking
> really was hints on how to write simple lisp code, I wasn't necessarily
> looking for recursion in my original question but for more efficient
> things like that array expression - we haven't even been introduced to
> arrays btw - and this is frustrating.
This is one problem with learning Lisp in a CS class, they'll often
restrict your knowledge to force you to think about how to implement
things that you should get for free. As long as you know this up
front, if you develop a grudge, hopefully it will be against your
professor, not Lisp :-)
If you're looking for elegant ways to implement something in Lisp, try
just writing what you mean in an s-expression syntax. Using macros
and higher-order functions, you can generally build the language up to
what you want to do. For example, you might want to write:
(iterate-across-list (elt list :start 0 :end n)
(summing elt))
You could do that by writing a with-summing macro, and an
iterate-across-list macro, giving you code in the end like:
(with-summing
(iterate-across-list (elt list :start 0 :end n)
(summing elt)))
Given how little of the language you've covered, though, you might not
be able to write your own macros yet. Be sure to learn this yourself,
if your course doesn't cover it! But, you could do something similar
with closures:
(sum (list-iterator list :start 0 :end n))
I would consider both of these elegant, because they express what you
want to do, not how to do it, which is clunky whether it's how to do
something iteratively or how to do something recursively. Now, it's
up to you to write the functions or macros that enable this, which
probably won't look quite so pretty.
This is exactly the kind of information I was looking for, I know now
where to direct my searches.
Rest assured that I don't have any grudge against Lisp, my goal is to
understand why it is so much praised and I approach this with an open
mind :)
Thanks!
Andrei
·······@mail.dntis.ro writes:
> This is exactly the kind of information I was looking for, I know now
> where to direct my searches.
>
> Rest assured that I don't have any grudge against Lisp, my goal is to
> understand why it is so much praised and I approach this with an open
> mind :)
>
How are you using Lisp?
If you haven't already, I suggest taking a look at
www.cliki.net/slime, the standard free IDE for Lisp these days. It'll
help, to say the least.
You might also want to take a look at gigamonkeys.com/book, and
possibly purchase it once it's actually available - should be any day
now. Meanwhile, you have the online version to look at; it's the best
introduction to Lisp I've ever seen.
From: Kent M Pitman
Subject: Re: newbie question : summing elements in a list
Date:
Message-ID: <uvf7oeswv.fsf@nhplace.com>
·······@mail.dntis.ro writes:
> This is exactly the kind of information I was looking for, I know now
> where to direct my searches.
>
> Rest assured that I don't have any grudge against Lisp, my goal is to
> understand why it is so much praised and I approach this with an open
> mind :)
Oh, we don't doubt that YOUR goal is this. Don't worry. But it's often
the unstated and sometimes unconscious goal of teachers to marginalize Lisp
by doing the following:
1. Start with Programming Language X.
2. Teach widely used concepts like vanilla straight-line programming,
block structure, etc. that occur in most languages in a way that
makes you think X owns these concepts.
3. Get to a point where X falls short.
4. Teach some obscure points about Lisp. Don't mention Lisp can do all
those things taught in 2, since
(a) [the "kind" explanation] they aren't needed for this problem
and don't want to distract you, and it simply doesn't occur to
them that you might be left thinking Lisp is absent these.
and/or
(b) [the "sinister/paranoid" explanation] they don't want you to
know that Lisp has ordinary ways of doing things
and/or
(c) [the "sad state of the world" explanation] they don't know
that Lisp has these features as an inductive consequence of
the fact that they were, themselves, taught by this same bogus
algorithm i'm explaining now, and never had their eyes opened.
and/or
(d) [the "failure of imagination" explanation] someone told them that
Lisp didn't have these features and they believed it without
checking, even though they were told 20 years ago and the world
has changed since then.
The reason that we tend to worry about case (b) is that, well, if you had
a choice of teaching programming in language X, which has most but not all
of the language capabilities you want [since why are they skipping to LISP
to teach some?] or else just using LISP, which largely has all the
capabilities of X + some others that are fun, wouldn't you just start with
LISP?
There are, in fact, some things that Lisp doesn't have, but those things
are not "capabilities", they are "styles". Lisp is not statically typed,
for example. This doesn't result in diminished power, but does result in
a difference in style.
And I suppose there's some sad truth to the fact that if LISP is not used
a lot in the commercial world, they have to expose you to what is used, so
that you'll be prepared for it when you get stuck with it at work.
But if you take nothing else away from this newsgroup, at least know
that Lisp is rich with expressive capabilities and does NOT support
just one paradigm for doing things. If you don't see a capability in the
language that you think is important in another, this is the place to ask.
People here would love to explain to you how LISP does things differently or
better in the many cases where that's so. And they're pretty honest about
the places that LISP falls short. But the language has been around a LONG
time (as long as FORTRAN) and has been beaten on by a lot of people intent
on killing it, and it has not died. All of that need to compete for its
very life has only made the language stronger.
Kent M Pitman <······@nhplace.com> writes:
> [...]
> Moreover, while Lisp is a language that allows recursion, it is not a
> place that recursion is required nor even always encouraged.
> Recursive solutions can use stack and you can run out of stack. Note
> that the Scheme language defines that tail recursion will not create
> extra stack,
ONLY FOR TAIL CALLS! Usually to process lists, it'll be ok, but to
process trees and other multidimensional structures, you'll still use
up stack.
> but Common Lisp makes no such provision. As such, Scheme
> users are taught that recursion is just another syntax for iteration,
> and often erroneously taught that the iteration constructs are to be
> eschewed. Not so in CL, where recursion and iteration are
> technologically different. Thinking falsely that using up stack in
> Lisp and risking a stack overflow is somehow either 'macho' or 'elegant'
> is just plain silly, therefore.
>
> In my personal view, the right solution for Common Lisp, if anything
> can ever be reduced tto a simple rule of thumb, is "iterate into the
> cdr and recurse on the car". It's a statistical accident of typical
> data structure layout that 'length' to the cdr side [the side toward
> which lists are biased in structure to grow unboundedly] is deeper
> than the 'length' to the car side (usually called 'depth'). Depth
> rarely grows unbounded, in part because Lisp programmers [in contrast
> to the myth about them] don't like all the parentheses that result
> from such a layout... In practice, depth usually grows (if "usually"
> can be said to have any meaning in such a broad generalization as I'm
> making) in something that feels more logarithmic a way, and rarely tempts
> the stack to overflow.
--
__Pascal Bourguignon__ http://www.informatimago.com/
In a World without Walls and Fences,
who needs Windows and Gates?
From: Kent M Pitman
Subject: Re: newbie question : summing elements in a list
Date:
Message-ID: <ur7icesnk.fsf@nhplace.com>
Pascal Bourguignon <····@mouse-potato.com> writes:
> Kent M Pitman <······@nhplace.com> writes:
> > [...]
> > Moreover, while Lisp is a language that allows recursion, it is not a
> > place that recursion is required nor even always encouraged.
> > Recursive solutions can use stack and you can run out of stack. Note
> > that the Scheme language defines that tail recursion will not create
> > extra stack,
>
> ONLY FOR TAIL CALLS! Usually to process lists, it'll be ok, but to
> process trees and other multidimensional structures, you'll still use
> up stack.
Didn't I say that? This is not terminology that I dirty myself with on a
day-to-day basis, so maybe I'm using the wrong term, but my understanding
is that "tail calls" are a superset of "tail recursion", not a subset.
I didn't grovel the net for a good definition of tail recursion, but I
thought it to refer to tail calls to the same function as contains the
call, as happens in iterations. My understanding is that Scheme also
defines that tail calls to other, often but not necessarily even
mutually-recursive functions, don't push stack.
General recursion (recursive calls in a non-tail position) are what push
stack, and I don't think I botched that. In processing a list,
car-recursion is usually in the non-tail position and cdr-recursion usually
is not. Although there are places you can uselessly push stack going into the
car of the last element of a list if you don't arrange things cleverly...
If my terminology doesn't match the mainstream on this, I'd appreciate having
it dusted off by someone who purports to know better.
Kent M Pitman <······@nhplace.com> writes:
> Pascal Bourguignon <····@mouse-potato.com> writes:
>
> > Kent M Pitman <······@nhplace.com> writes:
> > > [...]
> > > Moreover, while Lisp is a language that allows recursion, it is not a
> > > place that recursion is required nor even always encouraged.
> > > Recursive solutions can use stack and you can run out of stack. Note
> > > that the Scheme language defines that tail recursion will not create
> > > extra stack,
> >
> > ONLY FOR TAIL CALLS! Usually to process lists, it'll be ok, but to
> > process trees and other multidimensional structures, you'll still use
> > up stack.
>
> Didn't I say that? This is not terminology that I dirty myself with on a
> day-to-day basis, so maybe I'm using the wrong term, but my understanding
> is that "tail calls" are a superset of "tail recursion", not a subset.
Yes. I wanted to insist that not all recursion is tail recursion.
Perhaps I should have written "Only for TAIL calls!".
--
__Pascal Bourguignon__ http://www.informatimago.com/
The rule for today:
Touch my tail, I shred your hand.
New rule tomorrow.
·······@mail.dntis.ro writes:
> Greetings,
>
> I have a list of n*n numbers and I was wondering what is the most
> elegant way to get a new list out of this with n numbers, 1st number
> beeing the sum of numbers on positions 0, n, ..., n*(n-1), 2nd number
> beeing the sum of numbers on positions 1, n+1, ..., n*(n-2) and so
> forth.
>
> I am beginner at lisp and I can do it in the classical way with do...
> and indices in a loop but was wondering if there is a smarter approach
> in lisp.
By "smarter" I assume you mean walking the list a minimal number of
times. It's possible to walk it only once, but here is a simplier
solution that walks it twice.
Using the fact that mapcar returns a results as long as the shortest
argument list, we sum blocs of N items at once into a result list,
then advance further N items:
(defun n-sums (list)
(let* ((n (isqrt (length list)))
(cursor list)
(result (make-list n :initial-element 0)))
(dotimes (i n result)
(setf result (mapcar (function +) result cursor)
cursor (nthcdr n cursor)))))
(n-sums '(1 2 3 4 5 6 7 8 9)) --> (12 15 18)
Now, we could walk the list only once if we kept a cursor to each
element instead of the elements k*N, but we need to know when to
revert to the first sum. This could be done by a test:
(when (= i n) (setf result-cursor result))
but it can be avoided if the result is a circular list. We only need
to make it circular at the beginning and to break the circle at the end:
(defun make-circular-list (length &key (initial-element nil))
(let ((result (make-list length :initial-element initial-element)))
(setf (cdr (last result)) result)))
(defun break-circular-list (clist)
(when clist
(do ((cursor clist (cdr cursor)))
((or (eq (cdr cursor) clist) (null (cdr cursor)))
(when (cdr cursor) (setf (cdr cursor) nil))
clist))))
(defun n-sums (list)
(let ((result (make-circular-list (isqrt (length list)) :initial-element 0)))
(dolist (item list (break-circular-list result))
(incf (car result) item)
(setf result (cdr result)))))
Which you can write as:
(defun n-sums (list)
(let ((result (make-circular-list (isqrt (length list)) :initial-element 0)))
(break-circular-list (map-into result (function +) result list))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
The rule for today:
Touch my tail, I shred your hand.
New rule tomorrow.