在不完全重新实现函数的情况下更改递归函数合同？

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在同一命名空间已经定义。