From ...
Path: archiver1.google.com!newsfeed.google.com!newsfeed.stanford.edu!newsfeed.gamma.ru!Gamma.RU!skynet.be!newsfeeds.belnet.be!news.belnet.be!npeer.kpnqwest.net!nreader1.kpnqwest.net.POSTED!not-for-mail
Newsgroups: comp.lang.lisp
Subject: Re: sum over list?
References: <3B0FDCB8.41FDB9CB@mindspring.com>
Mail-Copies-To: never
From: Erik Naggum <erik@naggum.net>
Message-ID: <3200048369259034@naggum.net>
Organization: Naggum Software, Oslo, Norway
Lines: 176
User-Agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/20.7
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Date: Mon, 28 May 2001 14:19:38 GMT
X-Complaints-To: newsmaster@Norway.EU.net
X-Trace: nreader1.kpnqwest.net 991059578 193.71.66.150 (Mon, 28 May 2001 16:19:38 MET DST)
NNTP-Posting-Date: Mon, 28 May 2001 16:19:38 MET DST
Xref: archiver1.google.com comp.lang.lisp:10826

* Drew Krause <drkrause@mindspring.com>
> Boy is this a dumb question, but ....
> 
> I need to create a function which sums all members of a variable-length
> list, e.g.
> 
> (sum '(2 3 4)) => 9
> (sum '(5 6)) => 11
> 
> I'm having trouble doing this for variable lengths, as using '+'
> directly on the list of course won't work.

  There are a number of reasonably obvious answers to your question, but
  the reasons for choosing one among them might be worth investigating.

(apply <function> [<arg>...] <arglist>)

  calls <function> with the arguments that first include all the
  <args>... and then those that results from "spreading" <arglist> into
  separate arguments.  This function is most applicable in combination with
  the &rest lambda list keyword, which does the reverse operation: it makes
  a bunch of arguments into a list.  apply is a good function use when the
  arguments originate under complete program control.  Otherwise, you may
  run into the system limit on the number of arguments in argument lists,
  you may get run-time errors reflecting unexpected types of arguments, and
  you may in pathological cases come across a circular or dotted list,
  which may have rather severe consequences on your Common Lisp system.
  (Surprisingly, Allegro CL just drops dead if apply gets a circular list.)

(reduce <function> <sequence>)

  calls <function> with the first two elements from the sequence, then uses
  that value as the first argument in the next call, which takes the next
  element from the sequence, and thus it walks through the entire sequence,
  yielding the value of the final call to <function>.  (You can cause it to
  start with an initial value or to walk from the end with keyword args.)
  This is good when the sequence is not a list, and when it is really long,
  as it does not use more than two arguments to <function>.  Mind you, +
  would have to be called (1- n) times for a sequence of length n, anyway,
  so if you can avoid the overhead of calling + with all the arguments at
  once, that is a winner.  However, it will fail with unknown argument
  types, circular lists and dotted lists.

(let ((sum 0)) (dolist (elt <list> sum) (when (numberp elt) (incf sum elt))))

  is an inlined, iterative version that checks for numberness of each
  element before summing them.  This version also dies with circular lists
  and dotted lists.

(loop for elt in <list> when (numberp element) sum elt)

  is a specialized version for summation, which in this case may be the
  most appropriate.  It ensure that non-number elements are excluded from
  the process.  This avoid argument type errors.  The loop will still fail
  with an error if the list is dotted, and will never terminate if the list
  is circular.  One problem here is that it might be an error if there is a
  non-number in the list, and you would never detect that.  This could
  happen if you read numbers from a file that had gotten corrupted or were
  written by another program that, say, had a different floating-point
  format that turned into symbols for some of the not-quite-numbers.

(and (list-length <list>)
     ...)

  using any of the above forms in place of the ellipsis, will ensure that
  circular lists are detected and dotted lists cause an error before
  anything else happens.

(cond ((not (ignore-errors (list-length <list>)))
       ...)
      ((not (every #'numberp <list>))
       ...)
      (t (loop ...)))

  will test the primary conditions for success before trying to do the real
  work.  However, this is a rather expensive approach, so what if we do it
  all in one fell swoop?

(defun list-sum (list)
  (unless (and (listp list)
	       (listp (cdr list)))
    (error "~S is not a proper list." list))
  (do ((accum 0)
       (tortoise list (cdr tortoise))
       (hare (cdr list) (cddr hare)))
      ((null tortoise)
       accum)
    (when (eq tortoise hare)
      (error "~S is a circular list." list))
    (unless (and (consp tortoise)
		 (listp hare)
		 (listp (cdr hare)))
      (error "~S is a dotted list." list))
    (unless (numberp (first tortoise))
      (error "~S is not a number." (first tortoise)))
    (incf accum (first tortoise))))

  Of course, this is suitable for a program that can bitch at the user, but
  what if you want to bitch in a way tha that the _program_ can handle, and
  want to make this idiomatic expression into a standard tool?

(defmacro do-proper-list ((var listform &optional resultform &key if-circular if-dotted)
			  &body body)
  "Traverse the value of listform, binding var to each element over body.
Returns the value of resultform (default nil), upon completion.  If the list is
a circular list and if-circular is not a form that causes a non-local exit,
return nil.  Similarly with dotted lists and if-dotted.  The form establishes a
block named nil, like dolist."
  (let ((list (make-symbol "list"))
	(tortoise (make-symbol "tortoise"))
	(hare (make-symbol "hare")))
    `(do* ((,var nil)
	   (,list ,listform)
	   (,tortoise ,list (cdr ,tortoise))
	   (,hare (cdr ,list) (cddr ,hare)))
	 ((null ,tortoise)
	  ,resultform)
       ;; circular list?
       (when (eq ,tortoise ,hare)
	 ,if-circular
	 (return nil))
       ;; dotted list?
       (unless (and (listp ,tortoise)
		    (listp ,hare)
		    (listp (cdr ,hare)))
	 ,if-dotted
	 (return nil))
       ;; proper list, use element
       (setq ,var (car ,tortoise))
       ,@body)))

(defun proper-list-p (list)
  "If <list> is a proper list, return the number of elements, otherwise nil."
  (and (listp list)
       (listp (cdr list))
       (do-proper-list (ignore list t))))

(deftype proper-list ()
  `(and list (satisfies proper-list-p)))

(defun list-sum (list &key junk-allowed)
  "Return the sum of the elements of list, which must be numbers unless
junk-allowed is true, in which case non-numbers are ignored."
  (let ((sum 0))
    (if (do-proper-list (elt list t)
	  (if (numberp elt)
	      (incf sum elt)
	    (unless junk-allowed
	      (error 'type-error :datum elt :expected-type 'number))))
	sum
      (error 'type-error :datum list :expected-type 'proper-list))))

  Unfortunately, Allegro CL discourages the use of typed conditions by
  lacking any useful default :report method for most of them, but I believe
  the above is in the spirit of the language as specified, so those who
  want this to be more user-friendly may decide to use the internal
  function excl::.type-error with the datum and the exected-type as
  ordinary (not keyword) arguments, or the _non-standard_ arguments
  :format-control and :format-arguments that should only have been in
  simple-type-error.  If you dare to mess with the system internals, this
  also works well:

#+allegro
(defmethod print-object ((condition type-error) stream)
  (if (or *print-readably* *print-escape*)
      (call-next-method)
      (format stream "~1@<~@<~S is not of the expected type ~S~:@>~:@>"
	      (type-error-datum condition)
	      (type-error-expected-type condition))))

  This is one of those small things that make using the excellent condition
  system in Common Lisp properly less than enticing.

#:Erik
-- 
  Travel is a meat thing.