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

StackOverflow https://stackoverflow.com//questions/10666228

Вопрос

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

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

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

Сейчас вопрос не в решении этой конкретной проблемы.

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

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

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

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

    (fn [xy
    ((fn g [xy acc] ...) x 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)

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

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

Например здесь я решил:

  • использовать аккумулятор
  • рекурсивно увеличивать Икс пока не достигнет й

Но в итоге я получаю чудовище, описанное выше.

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

Что мне нужно, так это то, как после того, как я решил использовать 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)

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

Это было полезно?

Решение

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

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

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

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

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

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

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

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

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

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

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

дополнение:

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

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

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

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

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

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

Трудно учиться по книгам, в которых говорится о векторах и n-ном, цикле..повторяться и так далее, а затем осознавать, что изучение Clojure поможет вам продвинуться вперед.

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

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

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 или что-то, чтобы обойти не имеющую доступных генеракодицетагкода.

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top