Lisp挿入ソートの問題

Question

insertを使用して整数のリストを昇順にソートする関数sort1を記述します。 [リストが無ければ完了です。 。そうしないと、ソートCDRにリストの車を挿入]

これは私がやって管理してきたものであると私はSORT1と呼ばれる単一機能の両方の機能を定義するためにトラブルを抱えている：

(defun insert (item lst &optional (key #'<)) 
    (if (null lst) 
    (list item) 
    (if (funcall key item (car lst)) 
      (cons item lst) 
      (cons (car lst) (insert item (cdr lst) key))))) 
(defun insertion-sort (lst &optional (key #'<)) 
    (if (null lst) 
    lst 
    (insert (car lst) (insertion-sort (cdr lst) key) key))) 

Answer 1

1つの関数定義にすべてを取り込む最も簡単な方法は、を使用して、insert関数をinsertion-sortのローカル関数として定義することです。

は、しかし、あなたのコードについて言うには、いくつかの他のものがあります。

• あなたが機能listとの衝突の恐れのためlstとして変数を異名同音する必要はありません：Common Lispの関数と変数で異なる名前空間に生きる
• パターン(if (null list) list (...))〜(and list (...))を簡略化するのが一般的です。(null list)がtrueの場合、listはnilである必要があります。
• あなたの引数keyの名前は間違っています：keyは、リスト項目をとり比較のためのキー（see the HyperSpec on sort）を返す関数です。ここにあるもの（2つのアイテムを比較する関数）は「述語」と呼ばれます。
• パターンが(if ... (if ...))の場合は、condを使用すると通常より明瞭になります。
• docstring！
とにかく

、これらすべてのマイナーnigglesを固定し、labelsを使用して、ここでの結果だ：今insertがinsertion-sortに対してローカルであることを、私はpredicate引数を渡す必要はありません

(defun insertion-sort (list &optional (predicate #'<)) 
    "Return a sorted copy of list. Optional argument predicate must be a function 
that takes two items and returns true if they are in order." 
    (labels ((insert (item list) 
        (cond ((null list) (list item)) 
         ((funcall predicate item (car list)) 
          (cons item list)) 
         (t (cons (car list) (insert item (cdr list))))))) 
    (and list (insert (car list) (insertion-sort (cdr list) predicate))))) 

お知らせ内部関数は囲みコンテキストからバインディングを取得するため、