在没有完全重新实现函数的情况下更改递归函数契约？

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

我想要做的是实现一个counted-qsort内部使用上面的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最终调用次数的计数.在qs在让装订允许原始qsort功能,在重新定义的版本被引用,以避免无限递归.

我使用"计数"代替"深度",因为我不确定"深度"是否正确使用.此函数计算qsort调用的次数,而不是"树"的实际深度.

我不知道这种方法是否可以保持懒惰.

prn用于调试的示例输出:

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

我假设Clojure 1.3 qsort已经在同一名称空间中定义了.