Изменение контракта рекурсивной функции без полного переопределения функции?

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 в привязке let позволяет ссылаться на исходную функцию qsort в переопределенной версии, чтобы избежать бесконечной рекурсии.

Я использовал «количество» вместо «глубина», потому что я не уверен, что «глубина» является правильным термином для использования. Эта функция подсчитывает, сколько раз вызывается qsort, а не насколько глубоко "дерево" на самом деле.

Я не знаю, можно ли сохранить лень при таком подходе.

Пример вывода с prn для отладки:

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

Я предположил, что Clojure 1.3 и что qsort уже определен в том же пространстве имен.