Простейшая функция Lazy в Clojure - PullRequest
Новая
       11

Простейшая функция Lazy в Clojure

4 голосов
/ 20 февраля 2012

Мне нелегко понять лень.

Может кто-нибудь помочь мне понять, почему моя функция ниже не ленива 

(defn my-red
    ([f coll] (my-red f (first coll) (rest coll) ))
    ([f init coll] 
      (let [mr (fn [g i c d] 
            (if (empty? c) d 
        (recur  g (g  i (first c)) (rest c)  (conj d (g  i (first c)) ))))] 
    (lazy-seq (mr f init coll [])))))

тогда как этот пример приведен на clojure.org/lazy

1007 *

Ответы [ 3 ]

8 голосов
/ 20 февраля 2012

Лень в filter возникает из-за вызова filter в if ветви рекурсивного цикла.Вот где код достигает другого lazy-seq и останавливает оценку seq до тех пор, пока не будет запрошен другой элемент.

Ваша реализация my-red вызывает вызов lazy-seq один и только один раз, что означает, что ваш seqлибо вообще не оценены, либо полностью оценены.

2 голосов
/ 21 февраля 2012

Все, что lazy-seq делает, это принимает его аргумент и задерживает его выполнение.Чтобы создать истинно ленивую последовательность, каждая ссылка должна быть заключена в вызов lazy-seq.«Гранулярность» ленивости - это то, сколько работы выполняется между вызовами на lazy-seq.Единственный способ обойти это - использовать функции более высокого уровня, которые возвращают ленивый seq.

Кроме того, рекурсия хвоста и лень являются взаимоисключающими.Это не вызывает переполнения стека, потому что на каждом шаге рекурсивный вызов помещается в ленивый seq и возвращается.Если вызывающая сторона затем пытается вычислить ленивый seq, вызывается рекурсивный вызов, но он вызывается исходным вызывающим объектом функции sequence, а не самой функцией sequence, что означает, что стек не увеличивается.Это несколько похоже на идею реализации оптимизированной хвостовой рекурсии через батуты (см. Функцию trampoline Clojure).

Вот версия, которая ленива: 

(defn my-red
  ([f coll] (my-red f (first coll) (rest coll) ))
  ([f init coll] 
   (let [mr (fn mr [g i c] 
              (if (empty? c)
                nil
                (let [gi (g  i (first c))]
                  (lazy-seq (cons gi (mr g gi (rest c)))))))] 
     (lazy-seq (mr f init coll)))))

Обратите внимание, как каждый прогонmr немедленно возвращает либо ноль, либо ленивый seq, и рекурсивный вызов происходит из вызова lazy-seq.

2 голосов
/ 20 февраля 2012

Функция mr будет повторяться через весь цикл. Возможно, ваш отступник вводит вас в заблуждение. с правильным отступом и удалением некоторых ненужных параметров, функция выглядит примерно так: 

(defn my-red
  ([f coll] (my-red f (first coll) (rest coll) ))
  ([f init coll] 
     (let [mr (fn [i c d] 
                (if (empty? c)
                  d 
                  (recur (f i (first c))
                         (rest c)
                         (conj d (f i (first c))))))] 
       (lazy-seq (mr init coll [])))))

По сути, вы оборачиваете (lazy-seq) функцию mr, которая выполняет всю работу в одном большом цикле повторения.

...