在不完全重新實現函數的情況下更改遞歸函數合同？

Question

我想更改以下Quicksort實現的合同，以返回執行排序操作所需的遞歸調用數的計數。

來源：http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Clojure

(defn qsort [[pivot & xs]] 
    (when pivot 
    (let [smaller #(< % pivot)] 
     (lazy-cat (qsort (filter smaller xs)) 
       [pivot] 
     (qsort (remove smaller xs)))))) 

我想要做的是落實在內部使用了上述的qsort實施counted-qsort。

我正在尋找一個如何做到這一點的例子。我懷疑(bind ...)可能會涉及。

Answer 1

我這個問題發揮各地一小會兒，這裏就是我想出了：

(defn counted-qsort [coll] 
    (let [count (atom 0) qs qsort] 
    (with-redefs [qsort (fn [coll] 
          (swap! count inc) 
          (prn coll) 
          (qs coll))] 
     (dorun (qsort coll))) 
    (deref count))) 

此功能暫時重新定義qsort，以便它可以管理持有計數數的原子時間qsort最終被調用。 let綁定中的qs允許在重新定義的版本中引用原始qsort函數以避免無限遞歸。

我用「count」而不是「depth」，因爲我不確定「depth」是不是正確的用語。此函數計算調用次數爲qsort的次數，而不是「樹」的真正深度。

我不知道這種方法是否可以保留懶惰。

實施例輸出與prn用於調試：

[1 2 3] 
() 
(2 3) 
() 
(3) 
() 
() 
7 ;return value 

我假定的Clojure 1.3和qsort在同一命名空間已經定義。