Mergesort with an inversion counter

Question

I'm new to Lisp and I'm yet to wrap my head around the lisp way of writing programs. Any comments regarding approach, style, missed opportunities appreciated:

In particular, please advice if I build results list correctly ((setf merged-list (append merged-list (list a)))).

;;;; Count inversions
(defun small-list (list)
 (or (null list) (null (rest list))))
(defun split-in-half (list)
 (let ((mid (ceiling (length list) 2)))
 (values (subseq list 0 mid)
 (subseq list mid))))
(defun count-inversions (list)
 (if (small-list list) (list list 0)
 (multiple-value-bind (lower upper) (split-in-half list)
 (merge-inversions
 (count-inversions lower)
 (count-inversions upper)))))
(defun merge-inversions (lower-pair upper-pair)
 (let ((lower (first lower-pair))
 (upper (first upper-pair))
 (merged-list '())
 (num-inversions 0))
 (loop while (not (and (null lower) (null upper)))
 do (cond
 ((null lower) (let ((a (first upper)))
 (setf merged-list (append merged-list (list a)))
 (setf upper (rest upper))))
 ((null upper) (let ((a (first lower)))
 (setf merged-list (append merged-list (list a)))
 (setf lower (rest lower))))
 ((< (first lower)
 (first upper)) (let ((a (first lower)))
 (setf merged-list (append merged-list (list a)))
 (setf lower (rest lower))) )
 (t (let ((a (first upper)))
 (setf merged-list (append merged-list (list a)))
 (setf upper (rest upper))
 (incf num-inversions (length lower))))))
 (list merged-list (+ (second lower-pair) (second upper-pair) num-inversions)))

• zzandy: @RTOSkit, As I said, I need advice on how to make my lisp better. The program does what it needs to do, however there is certainly ways to make it more concise, efficient, elegant. I would like to learn them.
• Gareth Rees: No docstrings!!
• Faheem Mitha: An explanation of what this code is doing would be appreciated. Also, I see you don't declare any types.
• zzandy: @FaheemMitha, the code is aimed at counting inversions on a list, that is each situation when an element lower in the list is greater than an element higher in the list. Regarding types, could you please elaborate, as I mentioned I'm new to Lisp, and might easily be missing something obvious.
• Faheem Mitha: @zzandy: I think adding type declarations is used when you want to improve performance and/or when you want to add some typing to improve error checking of your code. (Specifically, for many operations, simple vectors are faster than linked lists.) However, performance considerations may not apply in your case. Most lisp books have sections on this topic. It is in the Common Lisp standard. Could you add a usage example for your code that the reader could run?

Answer 1

1. Use nconc instead of append for speed in

   (setf merged-list (append merged-list (list a)))

   Note that you need setf with nconc only if merged-list is nil.

2. Use pop: instead of

   (let ((a (first lower))) (setf merged-list (append merged-list (list a))) (setf lower (rest lower))))

   you can write

   (setf merged-list (nconc merged-list (list (pop lower))))

3. The combination of let and loop creates extra indentation for no good reason. You can use with clause in loop to create bindings instead, or use the do macro.

4. Usually predicates are named with a -p suffix, so I suggest that you rename your small-list to small-list-p.

5. Please fix line breaks and indentation in the third cond clause.

• zzandy: Thanks, that's a reply I was hoping for. I've changed indentation in third clause, I that what you meant?
• sds: @zzandy: looks good now (I added another small thing, see #3)

Answer 2

Revised version using @sds's suggestions:

(defun small-list-p (list)
 (or (null list) (null (rest list))))
(defun split-in-half (list)
 (let ((mid (ceiling (length list) 2)))
 (values (subseq list 0 mid)
 (subseq list mid))))
(defun count-inversions (list)
 (if (small-list-p list) (list list 0)
 (multiple-value-bind (lower upper) (split-in-half list)
 (merge-inversions
 (count-inversions lower)
 (count-inversions upper)))))
(defmacro move-last (source target)
 `(setf ,target (nconc ,target (list (pop ,source)))))

Function MERGE-INVERSIONS:

(defun merge-inversions (lower-pair upper-pair )
 (loop 
 with lower = (first lower-pair)
 with upper = (first upper-pair)
 with merged-list = '()
 with num-inversions = 0
 while (not (and (null lower) (null upper)))
 do (cond
 ((null lower) (move-last upper merged-list))
 ((null upper) (move-last lower merged-list))
 ((< (first lower) (first upper)) (move-last lower merged-list))
 (t
 (move-last upper merged-list)
 (incf num-inversions (length lower)) ))
 finally (return (list merged-list
 (+ (second lower-pair)
 (second upper-pair)
 num-inversions)))))

Performance went from this

139.740 seconds of real time
80,080,445,136 bytes consed

to this:

26.411 seconds of real time
87,009,536 bytes consed

---

_{This "answer" was extracted from Rev 7 of the question.}

Answer 3

• using multiple values instead of lists for return values
• merge-inversions has four parameters
• using multiple-value-call
• using LOOP functionality to collect items and to sum values
• much less traversal of lists

Try this:

(defun small-list-p (list)
 (not (and list (rest list))))
(defun split-in-half (list)
 (values (loop repeat (ceiling (length list) 2) collect (pop list))
 list))
(defun merge-inversions (lower lower-n upper upper-n &aux (num-inversions 0))
 (values (loop while (or lower upper)
 collect (cond ((null lower) (pop upper))
 ((null upper) (pop lower))
 ((< (first lower) (first upper)) (pop lower))
 (t (incf num-inversions (length lower)) (pop upper))))
 (+ lower-n upper-n num-inversions)))
(defun count-inversions (list)
 (if (small-list-p list)
 (values list 0)
 (multiple-value-bind (lower upper)
 (split-in-half list)
 (multiple-value-call #'merge-inversions
 (count-inversions lower)
 (count-inversions upper)))))