I decided to do an algorithms course (Roughgarden's on Coursera), and am setting out to implement each algorithm as it's introduced, in Lisp. We start with mergesort which is introduced as the canonical example of the divide and conquer paradigm.
The point of the paradigm being a problem is divided (into two), and solved, then the results are combined. Thus two steps are involved - the solution step and the combination step. We use induction such that subproblems are assumed solved, then we just need the base case. The base case here is that lists of length zero and of length 1 are already sorted so can just be returned.
This leaves us with the need to implement two things. First the divide part, then the combination part. In mergesort this means the functions mergesort and merge respectively.
Here's what I came up with for mergesort
(defun mergesort (lst)
"mergesort is the canonical example of the divide & conquer paradigm"
(if (or (null lst) (eq (length lst) 1))
lst
(let* ((len (length lst))
(mid (truncate len 2))
(sorted-lower (mergesort (subseq lst 0 mid)))
(sorted-upper (mergesort (subseq lst mid len))))
(merge. sorted-lower sorted-upper nil))))
And for merge
(defun merge. (x y acc)
"merge two lists by moving lowest car to output list"
(cond
((and (null x) (null y)) (reverse acc))
((null x) (merge. x (cdr y) (cons (car y) acc)))
((null y) (merge. (cdr x) y (cons (car x) acc)))
((<= (car x) (car y)) (merge. (cdr x) y (cons (car x) acc)))
(t (merge. x (cdr y) (cons (car y) acc)))))
These functions work fine.
Now to the problem.
The actual pseudocode given by the instructor, and the subsequent algorithmic analysis we're about to do, presumes that mergesort is done recursively (fine), but that merge is done iteratively.
But I naturally wrote merge recursively as above without really contemplating using a loop.
The instructor offers the following pseudocode
My thinking this morning has been, since in the next lecture we are going to study the theory of how to analyse the running time of divide and conquer, (including recursion tree method, generalising to the master method - i don't know what these are yet), that it might be better if I had an implementation which followed the actual pseudocode the instructor is assuming. (He did say at the beginning that any imperative language would be fine). But I would like more chance to use Lisp.
So, my implementation of the pseudocode give above is follows.
This code also works fine so long as we change the last line of mergesort to call merge- with the appropriate signature, which this time is (merge- len sorted-lower sorted-upper).
(defun merge- (n a b)
(let ((acc nil)
(ca 0)
(cb 0))
(dotimes (i n (reverse acc))
(cond
((null (nth ca a))
(progn
(setf acc (cons (nth cb b) acc))
(setf cb (+ cb 1))))
((or (null (nth cb b))
(<= (nth ca a) (nth cb b)))
(progn
(setf acc (cons (nth ca a) acc))
(setf ca (+ ca 1))))
(t
(progn
(setf acc (cons (nth cb b) acc))
(setf cb (+ cb 1))))))))
But boy, that code isn't half ugly!
I also spent at least half an hour simply not having a clue why it wasn't initially working. The reason was that I'd "forgotten" to use setf on acc, a notion totally at odds to the recursive version where instead of altering state we are defining divisions of the function and variables are irrelevant.
Since Common Lisp is multi-paradigm, I was wondering if the iterative version can be improved upon?
Would it be uncontroversial in the lisp community to observe that the recursive version is simply going to be better & more natural?
(and if that's the case, then why does this apply especially to lisp and less so to other languages? but lets not get into that transcendent question just yet! (maybe the answer is because we're using lists... which is maybe the key thing that makes recursion natural ... (?)))
Update 1: In response to Rainer's comment, here's a version using vectors:
(defun merge- (x y)
"merge sorted lists (or vectors) x & y into sorted array"
(let ((a (make-array (length x) :initial-contents x))
(b (make-array (length y) :initial-contents y))
(c (make-array (+ (length x) (length y))))
(i 0)
(j 0))
(dotimes (k (length c) c)
(cond
((= i (length a))
(setf (svref c k) (svref b j)
j (1+ j)))
((= j (length b))
(setf (svref c k) (svref a i)
i (1+ i)))
((< (svref a i) (svref b j))
(setf (svref c k) (svref a i)
i (1+ i)))
(t
(setf (svref c k) (svref b j)
j (1+ j)))))))
I'm wondering if style in the cond block above can be improved, or if that's how you'd normally do it?
Update 2: In response to Rainer's answer, I've written this new version of mergesort incorporating his suggestions (those I feel I fully understand at this point). Thank you Rainer.
(defun mergesort (lst)
"mergesort is the canonical example of the divide & conquer paradigm"
(flet ((merge- (a b)
"merge sorted arrays a & b into sorted array c"
(let ((c (make-array (+ (length a) (length b))))
(i 0)
(j 0))
(dotimes (k (length c) c)
(when (= i (length a)) ; [1]
(setf (subseq c k) (subseq b j)) ; [2]
(return c)) ; [3]
(when (= j (length b))
(setf (subseq c k) (subseq a i))
(return c))
(setf (aref c k)
(if (< (aref a i) (aref b j)) ; [4]
(prog1 (aref a i) (incf i))
(prog1 (aref b j) (incf j))))))))
(if (= (length lst) 0)
nil
(if (= (length lst) 1)
(make-array 1 :initial-element (first lst)) ; [5]
(let* ((len (length lst))
(mid (truncate len 2)))
(merge- (mergesort (subseq lst 0 mid))
(mergesort (subseq lst mid len))))))))
;; Notes
;; [1] when has an implicit progn
;; [2] use subseq in settable context to fill remaining array
;; [3] return from the implicit nil block created by dotimes
;; [4] the 2nd arg to setf becomes a conditional, with prog1 used to return
;; value of first arg, while tucking in the extra step needed in each case.
;; this is an advance in expressivity compared to c-style languages.
;; you can't do, there, for example:
;; a[3] = if(x < y) 2; else 3;
;; so in c/java you *must* say it this way, which is repetitive:
;; if x < y, a[3] = 2; else a[3] = 3;
;; [5] Base case of mergesort now returns an array, not a list.
;; That meant we can remove conversion of list to array in let.
;; Mergesort now receives list, but generates vector, right from the base case.
I'm very intrigued by the syntactical advance(?) over c-style languages which I mention in Note [4] above.
Any further discussion on that or any other points would be greatly appreciated :) thanks!
