Как мы делаем левую и правую складки в Clojure?

Ответ 1

Причина, по которой стандартная библиотека clojure имеет только fold-left (уменьшение), на самом деле очень тонкая, и потому, что clojure недостаточно ленив, чтобы получить главное преимущество fold-right.

Основное преимущество fold-right в таких языках, как haskell, состоит в том, что он может на самом деле коротко замыкаться. Если мы делаем foldr (&&) True [False, True, True, True, True], то способ, которым он фактически оценивается, очень просвещен. Единственное, что нужно оценить, это функция and с 1 аргументом (первая False). Как только он туда доберется, он знает ответ и не нуждается в оценке ЛЮБОГО из True s.

Если вы посмотрите очень внимательно на изображение:

вы увидите, что хотя концептуально fold-right начинается и заканчивается список и перемещается в направлении вперед, на самом деле он начинает оценивать FRONT списка.

Это пример того, где функции lazy/curried и tail recursion могут давать преимущества, которые clojure не могут.

Раздел бонусов (для заинтересованных)

Основываясь на рекомендации vemv, я хотел бы упомянуть, что clojure добавила новую функцию в пространство имен ядра, чтобы обойти это ограничение, которое clojure не может иметь ленивую правую сгиб. В основном пространстве имен есть функция reduced, которая позволяет вам сделать clojure reduce lazier. Его можно использовать для короткого замыкания reduce, говоря ему, чтобы он не смотрел остальную часть списка. Например, если вы хотели бы умножить списки чисел, но имели основания подозревать, что список иногда будет содержать нуль и хотел бы обработать это как особый случай, не глядя на оставшуюся часть списка после того, как вы столкнулись с нулем, вы могли бы написать следующую функцию multiply-all (обратите внимание на использование reduced, чтобы указать, что окончательный ответ 0, вне зависимости от того, что остальная часть списка).

(defn multiply-all [coll]
  (reduce
   (fn [accumulator next-value]
     (if (zero? next-value)
       (reduced 0)
       (* accumulator next-value)))
   1
   coll))

И затем, чтобы доказать, что это короткое замыкание, вы можете умножить бесконечный список чисел, который содержит нуль, и увидеть, что он действительно заканчивается с ответом 0

(multiply-all
 (cycle [1 2 3 4 0]))

Ответ 2

Посмотрим на возможное определение каждого из них:

(defn foldl [f val coll]
  (if (empty? coll) val
    (foldl f (f val (first coll)) (rest coll))))

(defn foldr [f val coll]
  (if (empty? coll) val
    (f (foldr f val (rest coll)) (first coll))))

Обратите внимание, что только foldl находится в хвостовом положении, а рекурсивный вызов может быть заменен на recur. Таким образом, с recur, foldl не будет занимать пространство стека, а foldr -. Вот почему reduce похоже на foldl. Теперь попробуйте:

(foldl + 0 [1 2 3]) ;6
(foldl - 0 [1 2 3]) ;-6
(foldl conj  [] [1 2 3]) ;[1 2 3]
(foldl conj '() [1 2 3]) ;(3 2 1)

(foldr + 0 [1 2 3]) ;6
(foldr - 0 [1 2 3]) ;-6
(foldr conj  [] [1 2 3]) ;[3 2 1]
(foldr conj '() [1 2 3]) ;(1 2 3)

Есть ли причина, по которой вы хотите свернуть? Я думаю, что наиболее распространенным использованием foldr является объединение списка спереди назад. В Clojure нам это не нужно, потому что мы можем просто использовать вектор. Другим вариантом избежать является использование ленивой последовательности:

(defn make-list [coll]
  (lazy-seq
    (cons (first coll) (rest coll))))

Итак, если вы хотите сбросить карты, некоторые эффективные альтернативы -

• Используйте вместо этого вектор.
• Используйте ленивую последовательность.
• Используйте reduced для короткого замыкания reduce.
• Если вы действительно хотите погрузиться в отверстие кролика, используйте датчик.