lisp中的非破壞性排序？

我的任務是創建一個程序，在其中我需要一個函數來返回一個排序列表（按字母順序）。但是，我無法使用和「非功能性」功能，例如「set，setq」等......並且包括內置的排序功能（因爲它具有破壞性）。所以，我想知道是否有辦法在lisp中構建一個非破壞性的排序？lisp中的非破壞性排序？

來源

2015-12-01 Danny S

這功課嗎？否則，這種限制聽起來像純粹的蠱惑。不，你在Common Lisp中沒有非破壞性的排序。要務實，只需創建一個複製序列的函數，在副本上運行'sort'並返回'sort'的結果。然後你可以假設或假裝這個新功能是非破壞性的。不要誤解我的意思，只要功能與非功能性方法一樣快，我就會喜歡純粹的功能性代碼，並且不會強迫我跳過。如果你被要求跳躍，你必須自己實現功能排序。 – acelent

我認爲在通常的lisp中，這樣做的典型方式就是在列表的新副本上使用破壞性排序。這符合「功能」api，因爲調用者可以觀察到任何副作用，並且相同的輸入始終獲得相同的輸出。 –

最簡單的方法是在排序前進行復制：

(sort (copy-seq input) predicate)

或者你自己寫一個排序函數，例如快速排序：

(defun qsort (input predicate) 
    (if input 
    (let* ((pivot (first input)) 
      (rest (rest input)) 
      (lesser (remove-if-not #'(lambda (x) 
             (funcall predicate x pivot)) 
            rest)) 
      (greater (remove-if-not #'(lambda (x) 
             (not (funcall predicate x pivot))) 
            rest))) 
     (append (qsort lesser predicate) 
       (list pivot) 
       (qsort greater predicate))) 
    nil))

(Demo)

注意，人們可以優化這個檢測列表已經排序休息，使無序和有序列表之間的結構共享。

來源

2015-12-02 00:56:06

如果您的破壞性排序交換了兩個相鄰元素，這些元素被完整保留的元素所包圍，那麼非破壞性的方法是創建一個由兩個交換元素組成的新列表，其中包含其他元素。然後，使用該新列表作爲後續排序操作的基礎。

破壞性地說，你的工作列表從開始到結束都是一樣的，你可以通過在另一個「地方」替換一個「地方」中的值來修改它。無損地在每一步創建一個新的列表，成爲工作列表。

我會將實施留給您。

來源

2015-12-02 00:58:43

lisp中的非破壞性排序？

回答

相關問題