Using different programming styles in Lisp

#1

One of the things I especially like about Lisp is that it gives you a choice of being able to program in a variety of different programming styles.

As an example, suppose we want to find the mean of the even numbers in a list of numbers. For example:

> (mean-even '(2 3 4 5 6 7 8 9 11))
5

Here are solutions in six different styles, for uLisp or Common Lisp:

C iterative style

(defun mean-even (lst)
  (let ((l (length lst))
        (sum 0) (n 0) d)
    (dotimes (i l)
      (setq d (nth i lst))
      (when (evenp d)
        (setq sum (+ sum d))
        (setq n (1+ n))))
    (/ sum n)))

Lisp list iteration

(defun mean-even (lst)
  (let ((sum 0) (n 0))
    (dolist (d lst (/ sum n))
      (when (evenp d)
        (incf sum d)
        (incf n)))))

Recursive

(defun count-even (lst)
  (cond
   ((null lst) 0)
   (t (+ (if (evenp (car lst)) 1 0) (count-even (cdr lst))))))

(defun mean-even (lst)
  (cond
   ((null lst) 0)
   ((evenp (car lst))
    (let ((n (count-even lst)))
      (/ (+ (car lst)
            (* (mean-even (cdr lst)) (1- n)))
       n)))
   (t (mean-even (cdr lst)))))

Recursive 2

(defun count-even (lst)
  (cond
   ((null lst) 0)
   (t (+ (if (evenp (car lst)) 1 0) (count-even (cdr lst))))))

(defun sum-even (lst)
  (cond
   ((null lst) 0)
   (t (+ (if (evenp (car lst)) (car lst) 0) (sum-even (cdr lst))))))

(defun mean-even (lst) (/ (sum-even lst) (count-even lst)))

Mapping with variables

(defun mean-even (lst)
  (let ((sum 0) (neven 0))
    (mapc #'(lambda (x) (when (evenp x) (incf sum x) (incf neven))) lst)
    (/ sum neven)))

Functional style (like Haskell)

If you’re using uLisp you’ll need to define these Common Lisp functions first, as they’re not built in:

(defun remove-if-not (test lst)
  (mapcan #'(lambda (x) (when (funcall test x) (list x))) lst))

(defun reduce (fn lst) (apply fn lst))

(defun count-if (test lst) (length (remove-if-not #'evenp lst)))

Here’s the function:

(defun mean-even (lst)
  (/ (reduce #'+ (remove-if-not #'evenp lst)) (count-if #'evenp lst)))

Can anyone suggest any others?

#2

How about a tail recursive helper function with accumulator variables:

(defun mean-even-helper (lst sum count)
  (cond ((null lst) (/ sum count))
        ((evenp (car lst)) (mean-even-helper (cdr lst) (+ sum (car lst)) (1+ count)))
        (t (mean-even-helper (cdr lst) sum count))))

(defun mean-even (lst) (mean-even-helper lst 0 0))

? At one time I believe this would have been a common way to implement this.

#3

Declarative, as in Prolog. I believe there used to be something like miniKanren which gave you “something like that”.

#4

I like Recursion #3 keeping the helper function within the defined function.

(defun mean-even (start-list)
  (let ((mean-even-helper
	  (lambda (lst sum count)
	    (cond
	      ((null lst) (/ sum count))
	      ((evenp (car lst))
	       (mean-even-helper (cdr lst) (+ sum (car lst)) (1+ count)))
	      (t (mean-even-helper (cdr lst) sum count))))))
    (mean-even-helper start-list 0 0)))