2011-07-18 168 views
2

使用插入來編寫一個函數sort1,它將整數列表按遞增順序排序。 [如果列表爲零,我們就完成了。否則,插入目錄的車開進了一個排序CDR]Lisp插入排序問題

這是我能夠做到的,我有麻煩,在一個單一的功能定義這兩個函數調用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))) 
+3

哇,這是我們的第一個遞歸問題標題嗎? – Chuck

+0

@Chuck::) :-) :) :-) – woliveirajr

回答

3

將其全部納入一個函數定義的最簡單方法是使用labels將函數insert定義爲insertion-sort內的本地函數。

還有一些其他的東西,說你的代碼,但是:

  • 你不需要respell變量作爲lst生怕與功能list碰撞:在Common Lisp的函數和變量生活在不同的命名空間。
  • 通常的做法是將(if (null list) list (...))的模式簡化爲(and list (...)),因爲如果(null list)爲true,那麼list必須爲nil
  • 您的論點key是錯誤的:key功能是一個需要列表項並返回一個用於比較的鍵(see the HyperSpec on sort)。你在這裏(一個比較兩個項目的函數)被稱爲「謂詞」。如果您使用cond,則通常會更清晰。
  • 沒有文檔字符串!

反正,修復所有那些次要的niggles,並使用labels,這裏的結果:

(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))))) 

注意,現在insert是本地insertion-sort,我沒有給predicate參數傳遞給它作爲內部函數從封閉的上下文中獲取綁定。