About me

About me


RSS feed

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)
   (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