Lispコードの冗長性を削除するには？

Question

私はCommon Lispではクイックソートの実装を思い付くしようとしましたが、これは私がこれまで持っているものです：

(defun quick-sort (list) 
    (if (cdr list) 
    (let ((pivot (car list))) 
     (append (quick-sort (remove-if-not (lambda (n) (< n pivot)) list)) 
       (remove-if-not (lambda (n) (= n pivot)) list) 
       (quick-sort (remove-if-not (lambda (n) (> n pivot)) list)))) 
    list)) 

どうやらそれは動作しますが、私はそれであまりにも多くの繰り返しがあると思いますコード。 >対<対=によって

(remove-if-not (lambda (n) (< n pivot)) list) 

3つの呼び出しが異なる唯一の方法は次のとおりです。基本的に、我々は3回を持っています。

私はこの冗長性を取り除き、コードをより読みやすくコンパクトにする方法を教えてください。もちろん

私は、次のような、関数に物事を抽出できます。

(defun which (operator pivot list) 
    (remove-if-not (lambda (n) (funcall operator n pivot)) list)) 

(defun quick-sort (list) 
    (if (cdr list) 
    (let ((pivot (car list))) 
     (append (quick-sort (which #'< pivot list)) 
       (which #'= pivot list) 
       (quick-sort (which #'> pivot list)))) 
    list)) 

しかし、どういうわけか、私はこれが最善のアプローチであるかどうかを本当に確信していません。 pivotとlistを何度も何度も引き渡す必要があるのは、やはり不器用だと感じています。

私もアイデアは、関数の実際のボディがより読みやすくなりfletを、使用していたが、唯一の他のどこかに複雑に移動：

(defun quick-sort (list) 
    (if (cdr list) 
    (let ((pivot (car list))) 
     (flet ((left() (remove-if-not (lambda (n) (< n pivot)) list)) 
      (middle() (remove-if-not (lambda (n) (= n pivot)) list)) 
      (right() (remove-if-not (lambda (n) (> n pivot)) list))) 
     (append (quick-sort (left)) 
       (middle) 
       (quick-sort (right))))) 
    list)) 

任意の他のアプローチ？

Answer 1

ローカル関数として記述すると、余分な引数はスコープ内にあるため、渡す必要はありません。

(defun quick-sort (list) 
    (if (rest list) 
     (let ((pivot (first list))) 
     (flet ((filter (operator) 
       (remove-if-not (lambda (n) (funcall operator n pivot)) list))) 
      (append (quick-sort (filter #'<)) 
        (filter #'=) 
        (quick-sort (filter #'>))))) 
    list)) 

Aもう少しコンパクト版：

(defun quick-sort (list &aux (pivot (first list))) 
    (flet ((filter (operator) 
      (remove-if-not (lambda (n) (funcall operator n pivot)) list))) 
    (and list 
     (nconc (quick-sort (filter #'<)) 
       (filter #'=) 
       (quick-sort (filter #'>)))))) 

Common Lispには複数の値をサポートしているので、あなたも一度に1つの関数にリストを分割し、値としてリストを返すことができます。

(defun partition (list pivot) 
    (loop for e in list 
     when (< e pivot) collect e into smaller else 
     when (> e pivot) collect e into larger else 
     when (= e pivot) collect e into same 
     finally (return (values smaller same larger)))) 

(defun quick-sort (list) 
    (if (rest list) 
     (multiple-value-bind (smaller same larger) 
      (partition list (first list)) 
     (append (quick-sort smaller) same (quick-sort larger))) 
    list)) 

リストを新しく割り当てた場合、NCONCが可能です。 REMOVE-IF-NOTは非破壊であるため（DELETE-IF-NOTと比較）、NCONCは問題ありません。 LOOPは新しいリストを収集するので、NCONCはもう一度いいです。

これは実際の単純なインプレースクイックソートベクターです。クイックソートは実際にそのように意味されていることに注意してください。リストを使用しているバージョンは実際にQuicksortではありません。

(defun partition (array left right &aux (i (1- left)) 
             (j right) 
             (v (aref array right))) 
    (loop do (loop do (incf i) until (>= (aref array i) v)) 
      (loop do (decf j) until (or (zerop j) 
             (<= (aref array j) v))) 
      (rotatef (aref array i) (aref array j)) 
     until (<= j i)) 
    (rotatef (aref array j) (aref array i) (aref array right)) 
    i) 

(defun quicksort (array &optional (left 0) (right (1- (length array)))) 
    (if (> right left) 
    (let ((i (partition array left right))) 
     (quicksort array left (1- i)) 
     (quicksort array (1+ i) right)) 
    array)) 

このバージョンはSedgewickのコードに基づいています。