Page 1 of 2
averaging
Posted: Tue Aug 31, 2010 4:32 pm
by burton
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
Re: averaging
Posted: Tue Aug 31, 2010 5:44 pm
by edgar-rft
If the input is a list of lists like:
Code: Select all
(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.
Re: averaging
Posted: Tue Aug 31, 2010 6:48 pm
by s-imp
I'm sure this is bad but:
Code: Select all
(defun average-list (lst)
(/
(eval (append '(+)
(mapcar #'(lambda (x) (first (last x))) lst)))
(length lst)))
Re: averaging
Posted: Tue Aug 31, 2010 7:26 pm
by Kohath
s-imp wrote:I'm sure this is bad ...
Good idea, try apply rather than eval with append:
Code: Select all
(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.
Re: averaging
Posted: Tue Aug 31, 2010 8:05 pm
by Duke
Here's a closure, just for fun:
Code: Select all
(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...
Code: Select all
(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.
Re: averaging
Posted: Tue Aug 31, 2010 9:05 pm
by s-imp
Thanks Kohath.
reduce worked beautifully. And I knew something was wrong when I used 'eval'.
Re: averaging
Posted: Tue Aug 31, 2010 9:19 pm
by s-imp
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.)
Re: averaging
Posted: Tue Aug 31, 2010 9:52 pm
by Duke
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.
Re: averaging
Posted: Wed Sep 01, 2010 3:37 am
by edgar-rft
Now here is a working 'reduce' example:
Code: Select all
(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:
Code: Select all
(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.
Re: averaging
Posted: Wed Sep 01, 2010 5:27 am
by s-imp
I didn't use the key argument. Thanks for the example. It was very helpful.