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

Question

Классическая книга "Маленький лиспер" ( The Little Schemer) основана на двух больших идеях.

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

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

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

Например:

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

Теперь с функциональными застежками-молниями - у нас есть нерекурсивный подход к обходу вложенных структур данных, и мы можем обходить их, как и любые ленивые структуры данных. Например:

(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 глубиной. Внесение поправок в первое из шести правил функционального программирования Clojure компании Halloway & Bedra ( Программирование Clojure (стр. 89)),

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

Есть пара паллиативов:

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