3
\$\begingroup\$

I'm working through Paul Graham's "ANSI Common Lisp". In Chapter 6 (p105), he introduces the idea of utility functions. He points out these are core to bottom-up programming and reusability. He observes that for such utility functions in lisp and fp "it's easier to abstract out the general when you can pass the specific as a function argument".

The example below is given in the book (my own code for discussion will follow after this example).


 (defun most (fn lst)      

 "What's the el of a list with highest score, according to provided
scoring fn?"

   (if (null lst)

      (values nil nil)    
      (let* ((wins (car lst))           ; 'wins' is 'winning element'
             (max (funcall fn wins)))   ; 'max' is 'winning score'
        (dolist (obj (cdr lst))         
          (let ((score (funcall fn obj)))
            (when (> score max)
              (setf wins obj
                    max score))))
        (values wins max))))

which runs as

> (most #'length '((a b) (a b c) (a)))
(A B C) ;
3

So, most above is effectively mapping the given list using the function argument then simply applying an arithmetic max to find the winner (though it does it in a slightly more efficient way than I just described).

I recalled a previous example where a comparator function was passed as an argument, allowing choice between > or <, for example. So, I added an second function argument to the above function as below (the only change is that the function arg has been added and then the single line where I've added a new comment).

(defun utmost (> fn lst)                ; note '>' is name of a variable!
  "Same as most above but with extra function argument allowing e.g. < or >"
  (if (null lst)
      (values nil nil)    
      (let* ((wins (car lst))           ; 'wins' is 'winning element'
             (max (funcall fn wins)))   ; 'max' is 'winning score'
        (dolist (obj (cdr lst))          
          (let ((score (funcall fn obj)))
            (when (funcall > score max) ; <- I replaced '>' with 'funcall >'
              (setf wins obj
                    max score))))
        (values wins max))))

which can be run as:

> (utmost #'< #'length '((a b) (a b c) (a))) 
(A) ;
1

Above, we passed < as the new fn param, so 'utmost' has taken the form of returning the element of the given list of 'least' ('length') this time.

Questions

Given that this is my first attempt at 'designing' a function that takes more than one function parameter, I'm wondering if I'm on the right track at all.

Obviously the name 'utmost' is not very good ('extremal', 'outlier'? - don't like the latter).

I wonder if the more you abstract out and so the more general a function becomes, the harder it becomes to name it? :)

If I wanted to parameterise 'lowest' or 'highest' I feel there should be a better way to do it, because passing > or < doesn't seem as intuitive as being able to state you want the lowest or highest.

Are there any design errors or misconceptions worth pointing out in the above?

Are there some better examples of functions which use multiple function arguments worth making a part of ones toolkit?

\$\endgroup\$
2
\$\begingroup\$

I agree that this generalization is not particularly useful: to abstract a part of a program to a functional parameter is meaningful when you can reuse that program with a class of different functions, not with two operators like < and >. For this, it is sufficient to define a boolean parameter:

(defun most (fn lst &key lowest)      
 "What's the el of a list with highest or lowest score, according to provided
scoring fn?"
  (if (null lst)
      (values nil nil)    
      (let* ((wins (car lst))                   ; 'wins' is 'winning element'
             (val (funcall fn wins))            ; 'max' is 'winning score'
             (comparison (if lowest #'< #'>))) ; highest or lowest ?
        (dolist (obj (cdr lst))         
          (let ((score (funcall fn obj)))
            (when (funcall comparison score val)
              (setf wins obj
                    val score))))
        (values wins val))))

CL-USER> (most #'length '((a b) (a b a c) (a)))
(A B A C)
4
CL-USER> (most #'length '((a b) (a b a c) (a)) :lowest t)
(A)
1

More, I think that in this case one possibility of generalization could be not on the comparison itself, but on the functional parameter applied to the results, that it the maximum (for which the comparison is used). In fact the Paul Graham's function is the optimization of the following simpler (and less efficient!) function:

(defun most (fn lst)
  (let ((val (reduce #'max lst :key fn)))
    (values (find val lst :key fn) val)))

Abstracting on the function #'max:

(defun most (fn op lst)
  (let ((val (reduce op lst :key fn)))
    (values (find val lst :key fn) val)))

Making it a little more efficient:

(defun most (fn op lst)
  (let* ((vals (mapcar fn lst))
         (val (reduce op vals))
         (wins (position val vals)))
    (values (when wins (nth wins lst)) val)))

But I think that even this generalization is not particularly useful, even if it could have a little more sense:

CL-USER> (most #'length #'max '((a b) (a b a c) (a)))
(A B A C)
4
CL-USER> (most #'length #'min '((a b) (a b a c) (a)))
(A)
1
CL-USER> (defun avg (a b) (/ (+ a b) 2))
AVG
CL-USER> (most #'length #'avg '((a b) (a b a c) (a)))
(A B)
2
CL-USER> (most #'length #'+ '((a b) (a b a c) (a)))
NIL
7
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.