Аккумуляторы, conj и рекурсия

Я думаю, что здесь есть чему поучиться.

во-первых, своего рода общее правило: рекурсивные функции обычно имеют естественный порядок, и добавление аккумулятора меняет его на противоположный. вы можете видеть это, потому что, когда запускается "нормальная" (без аккумуляторная) рекурсивная функция, она выполняет некоторую работу по вычислению значения, затем рекурсивно генерирует конец списка, в конечном итоге заканчивая пустым списком . напротив, с аккумулятором вы начинаете с пустого списка и добавляете элементы в начало — он растет в другом направлении.

поэтому обычно, когда вы добавляете аккумулятор, вы получаете обратный порядок.

теперь часто это не имеет значения. например, если вы генерируете не последовательность, а значение, являющееся повторным применением коммутативного оператора (например, сложения или умножения). то вы получите тот же ответ в любом случае.

но в вашем случае это будет иметь значение. вы собираетесь получить список в обратном порядке:

(defn my-range-0 [lo hi] ; normal recursive solution
  (if (= lo hi)
    nil
    (cons lo (my-range-0 (inc lo) hi))))

(deftest test-my-range-1
  (is (= '(0 1 2) (my-range-0 0 3))))

(defn my-range-1 ; with an accumulator
  ([lo hi] (my-range-1 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (cons lo acc)))))

(deftest test-my-range-1
  (is (= '(2 1 0) (my-range-1 0 3)))) ; oops!  backwards!

и часто лучшее, что вы можете сделать, чтобы исправить это, — это просто перевернуть этот список в конце.

но здесь есть альтернатива - мы можем выполнить работу в обратном порядке. вместо увеличения нижнего предела вы можете уменьшить верхний предел:

(defn my-range-2
  ([lo hi] (my-range-2 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (let [hi (dec hi)]
        (recur lo hi (cons hi acc))))))

(deftest test-my-range-2
  (is (= '(0 1 2) (my-range-2 0 3)))) ; back to the original order

[примечание - есть еще один способ изменить ситуацию ниже; я не очень хорошо структурировал свой аргумент]

во-вторых, как вы можете видеть на примерах my-range-1 и my-range-2, хороший способ написать функцию с аккумулятором — это функция с двумя разными наборами аргументов. это дает вам очень чистую (imho) реализацию без необходимости использования вложенных функций.

также у вас есть более общие вопросы о последовательностях, conj и тому подобном. здесь clojure немного грязный, но тоже полезный. выше я дал очень традиционное представление со списками, основанными на недостатках. но clojure рекомендует вам использовать другие последовательности. и в отличие от списков минусов, векторы растут вправо, а не влево. поэтому другой способ обратить этот результат — использовать вектор:

(defn my-range-3 ; this looks like my-range-1
  ([lo hi] (my-range-3 lo hi []))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (conj acc lo)))))

(deftest test-my-range-3 ; except that it works right!
  (is (= [0 1 2] (my-range-3 0 3))))

здесь conj добавляется вправо. я не использовал conj в my-range-1, так что здесь это переписано, чтобы было понятнее:

(defn my-range-4 ; my-range-1 written using conj instead of cons
  ([lo hi] (my-range-4 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (conj acc lo)))))

(deftest test-my-range-4
  (is (= '(2 1 0) (my-range-4 0 3))))

обратите внимание, что этот код выглядит очень похожим на my-range-3, но результат обратный, потому что мы начинаем с пустого списка, а не с пустого вектора. в обоих случаях conj добавляет новый элемент в «естественную» позицию. для вектора справа, а для списка слева.

и мне только что пришло в голову, что вы, возможно, не совсем понимаете, что такое список. в основном cons создает поле, содержащее две вещи (его аргументы). первый - это содержимое, а второй - остальная часть списка. так что список (1 2 3) в основном (cons 1 (cons 2 (cons 3 nil))). Напротив, вектор [1 2 3] работает больше как массив (хотя я думаю, что он реализован с использованием дерева).

поэтому conj немного сбивает с толку, потому что его работа зависит от первого аргумента. для списка он вызывает cons и таким образом добавляет элементы слева. но для вектора он расширяет массив (подобную вещь) вправо. также обратите внимание, что conj принимает существующую последовательность в качестве первого аргумента, а то, что нужно добавить, в качестве второго, а cons является обратным (то, что нужно добавить, идет первым).

весь приведенный выше код доступен по адресу https://github.com/andrewcooke/clojure-lab.

обновление: я переписал тесты так, чтобы ожидаемым результатом был список в кавычках в тех случаях, когда код генерирует список. = будет сравнивать списки и векторы и возвращать true, если содержимое одинаковое, но явное отображение более четко показывает, что вы на самом деле получаете в каждом случае. обратите внимание, что '(0 1 2) с ' впереди точно так же, как (list 0 1 2) - ' останавливает оценку списка (без него 0 будет рассматриваться как команда).

Прочитав все это, я все еще не уверен, зачем вам нужен аккумулятор.

((fn r [a b]
    (if (<= a b) 
       (cons a (r (inc a) b)))) 
  2 4)
=> (2 3 4)

кажется довольно интуитивным рекурсивным решением. единственное, что я бы изменил в «реальном» коде, - это использовать ленивую последовательность, чтобы у вас не исчерпался стек для больших диапазонов.

как я пришел к этому решению:

Когда вы думаете об использовании рекурсии, я считаю, что полезно попытаться сформулировать проблему с наименьшим количеством возможных терминов, которые вы можете придумать, и попытаться передать как можно больше «работы» самой рекурсии.

В частности, если вы подозреваете, что можете отбросить один или несколько аргументов/переменных, обычно так и поступают, по крайней мере, если вы хотите, чтобы код был простым для понимания и отладки; иногда вы в конечном итоге жертвуете простотой в пользу скорости выполнения или сокращения использования памяти.

В данном случае я подумал, когда начал писать: «первый аргумент функции также является начальным элементом диапазона, а последний аргумент — последним элементом». Рекурсивное мышление — это то, чему вам нужно научиться, но довольно очевидное решение — это сказать: диапазон [a, b] — это последовательность, начинающаяся с элемента a, за которым следует диапазон из [a + 1, b]. Таким образом, диапазоны действительно могут быть описаны рекурсивно. Код, который я написал, в значительной степени является прямой реализацией этой идеи.

дополнение:

Я обнаружил, что при написании функционального кода лучше избегать аккумуляторов (и индексов). Некоторые проблемы требуют их, но если вы можете найти способ избавиться от них, вам, как правило, будет лучше, если вы это сделаете.

дополнение 2:

Что касается рекурсивных функций и списков/последовательностей, самый полезный способ мышления при написании такого рода кода – формулировать проблему в терминах "первый элемент (голова) списка" и "остальные списка (хвоста)».