averaging

hi,
trying to solve this problem:
a function that adds up the numbers at the end of lists and then averages them.
input is like (xxx 1) (yyy 2) (zzz 3)....(nnn n)
=>6 ;(1+2+3+..+n)/n

(defun averaging (lst)
(if (null lst)
0
(+(setq(last lst)?

how does it register the number of lists it has visited, which will be the denominator of the average?
there is some sort of recursion i guess..

thnx

If the input is a list of lists like:

(list ('xxx 1) ('yyy 2) ('zzz 3) ... ('nnn n))

and it's always the same math operation [e.g. addition] and used always with the same element in the lists [e.g. the last element] then I would try to use REDUCE [look at the examples at the bottom of the page] instead of recursion to compute the sum of the numbers.

Hint: with the input list from above, the denominator is equal to the LENGTH of the list.

I'm sure this is bad but:

(defun average-list (lst)
  (/
     (eval (append '(+)
                  (mapcar #'(lambda (x) (first (last x))) lst)))
     (length lst)))

s-imp wrote:I'm sure this is bad ...

Good idea, try apply rather than eval with append:

(defun average-list (lst)
  (/ (apply #'+
            (mapcar #'(lambda (x) (first (last x))) lst))
     (length lst)))

More could be done, but it works nicely. The next step is to use reduce, which would be more concise.

Hint: You'd want to use the same function you passed to mapcar as the :key argument to reduce.

Here's a closure, just for fun:

(defun make-averager ()
           (let ((numbers nil))
             (lambda (lst)
               (setf numbers (nconc numbers lst))
               (/ (apply #'+ numbers) (length numbers)))))
CL-USER> (defvar pants (make-averager))
PANTS
CL-USER> (funcall pants (list 1 2))
3/2
CL-USER> (funcall pants (list 1 2))
3/2
CL-USER> (funcall pants (list 3 4))
13/6

(mapcar #'cadr numbers) can be passed as the argument to APPLY to fit the pair structure.

Just as an experiment, I tried writing a recursive solution that would keep the denominator in an accumulator instead of using LENGTH. My tinkering ended at this...

(defun avg (lst)
           (labels ((rec (numbers acc)
                      (if (null numbers)
                          0
                          (values (+ (car numbers) (rec (cdr numbers)
                                                        (1+ acc))) acc))))
             (multiple-value-bind (sum den) (rec lst 0)
               (/ sum den))))

Of course, the accumulator returns 0 on the last frame, so the function ends with a divide-by-zero no matter what. Other than putting the accumulator outside the scope of LABELS (which is probably why I used LABELS in the first place) I'm not sure how to deal with this, or if it would be in any way better than just using LENGTH.

Thanks Kohath.

reduce worked beautifully. And I knew something was wrong when I used 'eval'.

I like the idea of closures, though it is a bit above my pay-grade at the moment, Duke.

I had another solution that used 'let' and 'dolist', but I didn't want to use setf. It must have been something I read somewhere about minimizing their usage. Is that just for a style of programming using Common Lisp or is there a genuine price for using 'setf'.

(I also should have used cons in my first attempt rather than append, I'm hazarding to guess.)

s-imp wrote:I like the idea of closures, though it is a bit above my pay-grade at the moment, Duke.

I had another solution that used 'let' and 'dolist', but I didn't want to use setf. It must have been something I read somewhere about minimizing their usage. Is that just for a style of programming using Common Lisp or is there a genuine price for using 'setf'.

(I also should have used cons in my first attempt rather than append, I'm hazarding to guess.)

I happened to re-read chapter 3 of Paul Graham's On Lisp this afternoon, and in that very chapter the author opines that programmers should consider non-functional functions (i.e., functions that produce or use side-effects) like SETF to have a "tax" attached to them. You might say the tax is on maintainability and extensibility, which you'll pay in spades when it comes to debugging a larger project, I think.

Incidentally, Graham discusses closures in chapter 5.

Now here is a working 'reduce' example:

(defun average (lst)
  (/ (reduce #'+ lst :key #'(lambda (x) (first (last x))))
     (length lst)))

The :key argument tells 'reduce' to which element from the lists inside 'lst' the '+' function shall be applied. Because 'last' returns the last element as a list, the element itself must be extracted with 'first'.

Also note that '/' often returns ratios, which are more precise than floats, but sometimes the result is not-so obvious:

(average (list '(a 1) '(b 2) '(c 3) '(d 4) '(e 5) '(f 6)))
=> 7/2

Here '7/2' is the simplified version of '21/6'.

Embarrassing but true, I had to verify this with a commandline calculator...

Warning: using too much Common Lisp can make you lazy in your brain.

I didn't use the key argument. Thanks for the example. It was very helpful.

edgar-rft wrote:Now here is a working 'reduce' example:

(defun average (lst)
  (/ (reduce #'+ lst :key #'(lambda (x) (first (last x))))
     (length lst)))

The :key argument tells 'reduce' to which element from the lists inside 'lst' the '+' function shall be applied. Because 'last' returns the last element as a list, the element itself must be extracted with 'first'...

Isn't #'(lambda (x) (first (last x))) the same as #'second in this case?

(defun avg (lst) (/ (reduce #'+ lst :key #'second) (length lst)))

Warren Wilkinson wrote:Isn't #'(lambda (x) (first (last x))) the same as #'second in this case?

Yes, it is.

I'm used to search rather huge trees, so seeing something at the end of a list automatically makes me write (first (last x))...

The #'second solution in this case is clearly better, because no lambda construct is needed at all.

Yeah, I use that too --- Its often inconvenient that last returns a list rather than an item. Maybe I'll just define a utility function

(defun last-item (list) (car (last list)))

and be done with it.