Идиоматический способ рекурсии через коллекции в Clojure

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

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

(defn length
  ([xs]
     (if (nil? (seq xs))
       0
       (+ 1 (length (rest xs))))))

Теперь в схеме или CL все примеры только делают это над списками, поэтому идиотский базовый тест на этих языках будет (nil? xs). В Clojure мы хотели бы, чтобы эта функция работала над всеми типами коллекций, так же как идиоматический тест (nil? (seq xs)), или, может быть, (empty? xs), или что-то совершенно другое?

Другим случаем, который я хотел бы рассмотреть, является обход дерева, т.е. перемещение по списку или вектору, который представляет дерево, например. [1 2 [3 4].

Например, подсчет узлов в дереве:

(defn node-count [tree]
  (cond (not (coll? tree)) 1
        (nil? (seq tree)) 0
        :else (+ (node-count (first tree)) (node-count (rest tree)))))

Здесь мы используем (not (coll? tree)) для проверки атомов, тогда как в Схеме /CL мы будем использовать atom?. Мы также используем (nil? (seq tree)) для проверки пустой коллекции. И, наконец, мы используем first и rest для разрушения текущего дерева левой ветки и остальной части дерева.

Итак, чтобы суммировать, следующие формы идиоматичны в Clojure:

  • (nil? (seq xs)) для проверки пустой коллекции
  • (first xs) и (rest xs) для поиска в коллекции
  • (not (coll? xs)) для проверки атомов

Ответы

Ответ 1

Идиоматический тест для непустого выделения равен (seq coll):

(if (seq coll)
  ...
  )

nil? не требуется, так как возвращаемое значение не nil из seq гарантируется как seq и, следовательно, ни nil, ни false и, следовательно, правдиво.

Если вы хотите сначала разобраться с случаем nil, вы можете изменить if на if-not или seq на empty?; последний реализуется как композиция seq с not (поэтому не следует писать букву (not (empty? xs)), cf.docstring of empty?).

Что касается first/rest - полезно запомнить строгий вариант rest, next, использование которого более идиоматично, чем обертка rest в seq.

Наконец, coll? проверяет, является ли его аргумент постоянной коллекцией Clojure (экземпляр clojure.lang.IPersistentCollection). Является ли это подходящей проверкой для "неатомов", зависит от того, должен ли код обрабатывать структуры данных Java как не-атомы (через interop): например, (coll? (java.util.HashSet.)) false, как и (coll? (into-array [])), но вы можете называть seq для обоих. Существует функция seqable? в core.incubator в новом модульном вкладе, который promises определяет, будет ли (seq x) успешным для задан x.

Ответ 2

Мне лично нравится следующий подход к рекурсии через коллекцию:

(defn length
  "Calculate the length of a collection or sequence"
  ([coll]
     (if-let [[x & xs] (seq coll)]
       (+ 1 (length xs))
       0)))

Особенности:

  • (seq coll) является идиоматическим для проверки того, является ли коллекция пустой (в соответствии с замечательным замечанием Михала)
  • if-let с (seq coll) автоматически обрабатывает как нулевой, так и пустой случай коллекции
  • Вы можете использовать деструктурирование, чтобы называть первый и следующий элементы, которые вам нравятся для использования в вашем теле тела

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

(defn length
  "Calculate the length of a collection or sequence"
  ([coll]
    (length coll 0))
  ([coll accumulator]
    (if-let [[x & xs] (seq coll)]
      (recur xs (inc accumulator))
      accumulator)))

(length (range 1000000))
=> 1000000