Аккумуляторы, конъюнкция и рекурсия

Question

Я решил 45 проблем с 4clojure.com, и я заметил повторяющуюся проблему в том, как я пытаюсь решить некоторые проблемы с помощью рекурсии и аккумуляторов.

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

Например, проблема 34 просит написать функцию (без использования диапазон), беря два целых числа в качестве аргументов и создавая диапазон (без использования диапазона). Проще говоря, вы делаете (... 1 7) и получаете (1 2 3 4 5 6).

Теперь этот вопрос не касается решения этой конкретной проблемы.

Что делать, если я хочу решить это с помощью рекурсии и аккумулятора?

Моего мыслительный процесс выглядит следующим образом:

• Мне нужно написать функцию, принимающую два аргумента, я начинаю с (Fn [х])

• мне придется рекурсивным и мне нужно будет отслеживать список, я буду использовать накопитель, поэтому я напишу 2-ю функцию внутри первой с дополнительным аргументом:

  (fn [xy]
  ((п г [ху акк] ...) х у «())

(по-видимому, я не могу правильно форматировать, что Clojure код на SO !?)

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

Тогда я хочу Conj, но я не могу сделать:

(conj 0 1) 

так что я странные вещи, чтобы убедиться, что у меня есть последовательность первых, и я в конечном итоге с этим:

(fn 
    [x y] 
    ((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x))) 
    x 
    y 
    '())) 

Но тогда это производит это:

(1 (2 (3 4))) 

Вместо этого:

(1 2 3 4) 

Так что я в конечном итоге делает дополнительный расплющить и она работает, но это совершенно некрасиво.

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

К примеру здесь я решил:

• использовать аккумулятор
• для рекурсии приращением х до тех пор, пока не достигнет у

Но я в конечном итоге с уродством выше ,

Есть проблема , чтобы решить эту проблему, и еще раз это не то, что мне нужно.

То, что я после того, как, как, после того, как я решил минусы/CONJ, используйте аккумулятор и рекурсию, я могу закончить с этим (не написано мной):

#(loop [i %1 
     acc nil] 
    (if (<= %2 i) 
    (reverse acc) 
    (recur (inc i) (cons i acc)))) 

Вместо этого :

((fn 
    f 
    [x y] 
    (flatten 
    ((fn 
    g 
    [x y acc] 
    (if (= x y) acc (conj (conj acc (g (inc x) y acc)) x))) 
    x 
    y 
    '()))) 
1 
4) 

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

Answer 1

Я думаю, есть несколько вещей, чтобы узнать здесь.

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

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

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

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

(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 очень грязный, но полезный. выше, я давал очень традиционный вид с списками на основе cons. но 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 берет существующую последовательность как первый arg, а вещь добавляется как вторая, а cons - обратная (вещь сначала добавляется).

---

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

---

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

Answer 2

После прочтения всего, что я я все еще не знаю, почему вам понадобится n аккумулятора.

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

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

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

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

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

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

Приложение:

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

добавление 2:

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

Answer 3

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

user=> (defn my-range [lb up c] 
     (if (= lb up) 
      c 
      (recur (inc lb) up (conj c lb)))) 
#'user/my-range 

затем вызвать его с

#(my-range % %2 []) 

Конечно, я хотел бы использовать letfn или что-то, чтобы обойти, не имея defn.

Итак, вам нужна внутренняя функция для использования подхода к аккумулятору.

Мой мыслительный процесс заключается в том, что как только я закончу ответ, я хочу вернуться, будет в аккумуляторе. (Это контрастирует с вашим решением, где вы много работаете над поиском конечного условия.) Поэтому я ищу свое конечное условие, и если я достиг этого, я возвращаю аккумулятор. В противном случае я привяжусь к следующему элементу к аккумулятору и повторюсь для меньшего размера. Таким образом, есть только 2 вещи, чтобы выяснить, что такое конечное условие, и что я хочу добавить в аккумулятор.

Использование вектора помогает, потому что conj добавит к нему, и нет необходимости использовать reverse.

I'm on 4clojure too, кстати. Я был занят, поэтому я отстал в последнее время.

Answer 4

Похоже, что ваш вопрос скорее о том, «как учиться», а затем о технической/кодовой проблеме. В конечном итоге вы пишете такой код, потому что каким бы то ни было способом или источником, который вы изучили в целом в программировании, или Clojure в конкретном стиле создало «нейронную магистраль» в вашем мозгу, что заставляет вас думать о решениях именно таким образом, и вы в конечном итоге пишете код как это. В основном, когда вы сталкиваетесь с какой-либо проблемой (в данном конкретном случае рекурсия и/или накопление), вы в конечном итоге используете эту «нейронную магистраль» и всегда придумываете такой код.

Решение для избавления от этой «нейронной магистрали» - это прекратить написание кода на данный момент, отложить эту клавиатуру и начать читать много существующего кода clojure (из существующих решений проблемы 4clojure для проектов с открытым исходным кодом на github) и подумайте об этом глубоко (даже прочитайте функцию 2-3 раза, чтобы действительно позволить ей успокоиться в вашем мозгу). Таким образом, вы в конечном итоге уничтожаете существующую «нейронную магистраль» (которая создает код, который вы сейчас пишете), и создаст новую «нейронную магистраль», которая создаст красивый и идиоматический код Clojure. Кроме того, постарайтесь не переходить к набору кода, как только вы заметили проблему, скорее дайте себе время подумать четко и глубоко о проблеме и решениях.

Answer 5

Я не могу добавить к уже хорошим ответам, которые вы получили, но я отвечу в целом. Когда вы проходите процесс обучения Clojure, вы можете обнаружить, что многие, но не все решения могут быть решены с использованием встроенных модулей Clojure, таких как карта, а также мышления о проблемах в терминах последовательностей. Это не означает, что вы не должны рекурсивно решать вещи, но вы услышите - и я считаю, что это разумный совет - рекурсия Clojure предназначена для решения проблем с низким уровнем, которые вы не можете решить другим способом.

Я, случается, много обрабатываю файлы .csv и недавно получил комментарий, который nth создает зависимости.Это так, и использование карт позволяет мне получить элементы для сравнения по имени, а не положению.

Я не собираюсь выкидывать код, который использует nth с анализируемыми данными clojure-csv в двух небольших приложениях, уже находящихся в производстве. Но я буду думать о вещах в более последовательном порядке в следующий раз.

Трудно узнать из книг, которые рассказывают о векторах и nth, loop .. recur и т. Д., А затем осознать, что Clojure развивает вас вперед.

Одна из вещей, которые я нашел, которая хороша в изучении Clojure, является сообщество уважительным и полезным. В конце концов, они помогают кому-то, чей первый язык обучения был Fortran IV на CDC Cyber ​​с перфокартами, а первым коммерческим языком программирования был PL/I.