Рекурсия запаха (в идиоматическом Clojure) из-за молнии и HOF?

Question

Классическая книга The Little Lisper (The Little Schemer) основан на два больших идеях

1. Вы можете решить большинство проблем рекурсивным образом (вместо использования петель) (если у вас есть хвост вызов Optimization)
2. Lisp является большим потому что он легко реализуется сам по себе.

Теперь можно подумать, что это относится ко всем языкам Lispy (включая Clojure). Беда в том, что книга является артефактом ее времени (1989), вероятно, до Functional Programming с Higher Order Functions (HOFs) была тем, что у нас есть сегодня (или, по крайней мере, считалось приемлемым для студентов).

Преимущество рекурсии (по крайней мере частично) заключается в простоте обхода вложенных структур данных, таких как ('a 'b ('c ('d 'e))).

Для example:

(def leftmost 
    (fn [l] 
    (println "(leftmost " l) 
    (println (non-atom? l)) 
    (cond 
     (null? l) '() 
     (non-atom? (first l)) (leftmost (first l)) 
     true (first l)))) 

Теперь Functional Zippers - мы имеем нерекурсивный подход к пересекающему вложенным структурам данных, и можем пересекать их, как мы бы любые ленивые структуры данных. Для example:

(defn map-zipper [m] 
    (zip/zipper 
    (fn [x] (or (map? x) (map? (nth x 1)))) 
    (fn [x] (seq (if (map? x) x (nth x 1)))) 
    (fn [x children] 
     (if (map? x) 
     (into {} children) 
     (assoc x 1 (into {} children)))) 
    m)) 

(def m {:a 3 :b {:x true :y false} :c 4}) 

(-> (map-zipper m) zip/down zip/right zip/node) 
;;=> [:b {:y false, :x true}] 

Теперь, кажется, можно решить любую вложенную список обхода проблемы либо с:

• zipper, как указано выше, или
• zipper ходящий структуру и возвращает набор ключи, которые позволят вам изменить структуру, используя assoc.

Предположения:

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

Мой вопрос: Является рекурсивным запахом (в идиоматическом Clojure) из-за молнии и HOF?

Answer 1

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

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

Answer 2

Идиомы Clojure препятствуют явной рекурсии, потому что стек вызовов ограничен: обычно до глубины около 10K. внесение изменений и дополнения первых из Halloway & Bedra в Шесть Правила Clojure функционального программирования (Programming Clojure (стр 89)),

Избегайте неограниченной рекурсии. JVM не может оптимизировать рекурсивные вызовы и Программы Clojure, которые рекурсируют без привязки будут взорвать их стек.

Есть несколько паллиативных:

• recur сделок с хвостом рекурсии.
• Ленивые последовательности могут превращать глубокий стек вызовов в стопку неглубоких вызовов
  через разворачивающуюся структуру данных. Многие HOF в последовательности
  библиотеки, такие как map и filter, сделайте это.