current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

This is my first bit of significant code in Common Lisp, an implementation of insertion sort. Being new to Lisp in general, I'm wondering if this code follows best Lisp practices in regards to program design.

;;; Return a portion of a list
(defun slice (elements from-index to-index)
  (cond
    ((= from-index to-index) nil)
    (t (cons (nth from-index elements) (slice elements (+ from-index 1) to-index)))))

;;; Return a list omitting a portion
(defun splice (elements from-index to-index)
  (append (slice elements 0 from-index) (slice elements to-index (length elements))))

;;; Move element in list to new index, return new list
(defun move (elements from-index to-index)
  (let ((spliced (splice elements from-index (+ from-index 1))))
    (append (slice spliced 0 to-index) (list (nth from-index elements)) (slice spliced to-index (length spliced)))))

;;; Find the determined (via predicate) correct index for an element in a list
(defun find-ordered-index (elements predicate index &optional (key index))
  (cond
    ((or (= index 0) (= key 0)) 0)
    ((funcall predicate (nth (- key 1) elements) (nth index elements)) (find-ordered-index elements predicate index (- key 1)))
    (t key)))

;;; Return sorted list
(defun insertion-sort (elements predicate &optional (index 0))
  (cond
    ((= index (length elements)) elements)
    (t (insertion-sort (move elements index (find-ordered-index elements predicate index)) predicate (+ index 1)))))
share|improve this question
up vote 5 down vote accepted

Trivial

Use 1- instead of (- ... 1).

Avoid very long lines (Emacs will indent for you).

Do not use cond when a single if without progn would do.

Memory

Use nconc instead of append when possible to avoid unnecessary consing (in your case, splice allocates a fresh list, so its result can be passed to nconc).

Catastrophic

Whenever you use nth, you are using the wrong algorithm.

Optimal search is linearithmic: O(n*log(n)).

Insert search is quadratic: O(n^2).

Your implementation is O(n^3):

  1. nth is O(n)
  2. slice is O(n^2) (calls nth * recursion).
  3. splice and move are also O(n^2) (call slice).
  4. find-ordered-index is O(n).
  5. insertion-sort is O(n^3) (calls move * recursion).
share|improve this answer
    
In places where recursing (like in slice) were quadratic, would iteration using the loop macro be better? – Jking Jul 22 '15 at 19:34
    
recursion and iteration are algorithmically equivalent. – sds Jul 22 '15 at 19:34
    
Well, slice is implemented using linear recursion, so it is called n times itself. If I were to implement slice using iteration, wouldn't the list only be traversed once? – Jking Jul 22 '15 at 19:36
    
whenever you call nth you are traversing the list. – sds Jul 22 '15 at 19:37
    
So if instead of accumulating values by accessing them with nth, using a loop and collecting values from from-index to to-index should take one order of n less time for the whole slice function – Jking Jul 22 '15 at 19:41
up vote 0 down vote

If you're interested in using what the language provides...

..you don't have to implement slice yourself, look at SUBSEQ.

..for find-ordered-index you could use POSITION-IF

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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