Re: newbie question : summing elements in a list

From: Kent M Pitman (pitman_at_nhplace.com)
Date: 03/18/05 

Date: Fri, 18 Mar 2005 08:58:25 GMT

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

Relevant Pages

  • Re: newbie question : summing elements in a list
    ... > place that recursion is required nor even always encouraged. ... > Recursive solutions can use stack and you can run out of stack. ... > users are taught that recursion is just another syntax for iteration, ... > In my personal view, the right solution for Common Lisp, if anything ...
    (comp.lang.lisp)
  • Re: Lisp article at IBM
    ... you saw my use of 'smart' and 'elegant' and rather than read ... I'm pleased I have lisp to ... the prefix notation. ... If the linear algorithm needs less programmers-hours than optimized ...
    (comp.lang.lisp)
  • Re: calculating fibonacci[was: encryption]
    ... "Elegant" is a bit of an over statement - it is elegant given the ... recursion, using a functional language, and the criterion of ... being created with the proviso that the compiler can be counted ... fib n = hack n 1 1 ...
    (comp.programming)
  • Re: The Hyperspec and portability between Common Lisp compilers (long)
    ... > elegant, maintainable programs. ... CLISP forces me to use a C++-like style of guessing what classes might ... I can only assume that you haven't worked in a Lisp that has ... problems that fit within the model of the standard method combination. ...
    (comp.lang.lisp)
  • Re: Beautiful code
    ... by Edi Weitz. ... library authors for Lisp, right now, IMO. ... Can something be both elegant and crufty? ... I think emacs fits that bill. ...
    (comp.lang.lisp)