Pairwise function
12th October 2016
What's the best way to apply a function to successive pairs of items in a list?
For example, we want to write a function pairwise that can be used as follows:
(pairwise #'- '(1 4 9 16 25 36 49 64 81 100))
This should calculate 4 - 1, 9 - 4, 16 - 9, and so on, and return:
(3 5 7 9 11 13 15 17 19)
One approach
Since we need to access more than just one item at a time from the list the obvious starting point is maplist. We could try writing something as follows:
(defun pairwise (fun lis) (maplist (lambda (a) (funcall fun (cadr a) (car a))) lis))
However this gives an error because with the above example it's trying to calculate (- nil 100) for the last item in the list. We can avoid the error, and then get rid of the nil at the end of the result, with:
(defun pairwise (fun lis) (butlast (maplist (lambda (a) (when (cdr a) (funcall fun (cadr a) (car a)))) lis)))
A simpler answer
In fact there's a much simpler answer, taking advantage of the fact that the mapping functions can take two (or more) lists as their arguments:
(defun pairwise (fun lis) (map 'list fun (cdr lis) lis))
Furthermore we can easily generalise this to apply a function to any number of successive sets of elements.
Differentiating a polynomial
Finally here's a practical application of the pairwise function. We can represent a polynomial as a list of coefficients; for example, the polynomial:
5x4 + 4x3 + 3x2 + 2x + 1
could be represented as:
(1 2 3 4 5)
where the nth element is the coefficient for xn. The definition of a function diff to differentiate a polynomial poly is simply:
(defun diff (poly) (pairwise #'* poly))
For example, to differentiate the polynomial given above:
CL-USER > (diff '(1 2 3 4 5)) (2 6 12 20)
So the answer is: 20x3 + 12x2 + 6x + 2
blog comments powered by Disqus