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)))
#5

Here is a functional style solution that makes only one pass over the list. We also avoid dividing by zero when there are no even numbers in the list.

(defun mean-even (list)
  "Return the mean of the even numbers in list"
  (destructuring-bind (sum . count)
      (reduce
       (lambda (a b)
         (if (evenp b)
             (cons (+ (car a) b) (incf (cdr a)))
             a))
       list :initial-value (cons 0 0))
    (unless (zerop count) (/ sum count))))
#6

Good to see this thread revived, and thank you @mac for your nice solution to the problem using reduce.

As reduce isn’t provided in uLisp, to run your solution on uLisp you need to define it, one way of which is recursively as follows:

(defun reduce* (fn lst &optional (initial 0))
  (if (null lst) initial
    (reduce* fn (cdr lst) (funcall fn initial (car lst)))))

For example, to add together the numbers 1 to 6:

> (reduce* #'+ '(1 2 3 4 5 6))
21

You also need to replace destructuring-bind with car and cdr, to give:

(defun mean-even (lst)
  "Return the mean of the even numbers in lst"
  (let* ((r (reduce*
             (lambda (a b)
               (if (evenp b)
                   (cons (+ (car a) b) (incf (cdr a)))
                 a))
             lst (cons 0 0)))
         (sum (car r))
         (count (cdr r)))
    (unless (zerop count) (/ sum count))))

For example:

> (mean-even '(1 2 3 4 6 7 8 10))
6

The test for no even numbers is a good idea, and should be added to the other solutions.

#7

Take the Functional First Approach leading to smaller tighter code with fewer bugs.

…and I’ll be the first to go off-road whenever it “makes sense”, mostly in regards to efficiency which is common with a tiny amount of working memory.

Although uLisp is a kick’in subset of CL, CL does have more FP options so sometimes it doesn’t makes sense to go fully functional with uLisp’s smaller-leaner toolbox.

  • h