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

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

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

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

Теперь речь идет не о решении этой конкретной проблемы.

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

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

Мне нужно написать функцию, принимающую два аргумента, я начинаю с (fn [x y])
Мне нужно будет записаться, и мне нужно будет отслеживать список, я буду использовать накопитель, поэтому я пишу 2-ю функцию внутри первой, которая принимает дополнительный аргумент:

(п [x y]
((fn g [x y acc]...) Икс Y "())

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

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

Затем я хочу соединить, но я не могу:

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

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

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

Например, я решил:

использовать накопитель
для рекурсии путем увеличения x до достижения y

Но я в конечном итоге с монстрами выше.

Есть много способов решить эту проблему, и, опять же, это не то, что мне нужно.

То, что я за то, как после того, как я решил cons/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)

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

Ответ 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 добавляет новый элемент в "естественную" позицию. для вектора, который справа, но для списка он слева.

и мне просто пришло в голову, что вы не можете понять, что такое список. в основном a 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

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

Ответ 2

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

((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:

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

Ответ 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.

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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