Почему программа работает бесконечно?

Question

Почему программа работает бесконечно?

(defn lazycombine
([s] (lazycombine s []))
([s v] (let [a (take 1 s)
             b (drop 1 s)]
            (if (= a :start)
                (lazy-seq (lazycombine b v))
                (if (= a :end)
                    (lazy-seq (cons v (lazycombine b [])))
                    (lazy-seq (lazycombine b (conj v a))))))))

(def w '(:start 1 2 3 :end :start 7 7 :end))

(lazycombine w)

Мне нужна функция, которая возвращает ленивую последовательность элементов, беря элементы из другой последовательности в форме [: start 1 2: end: start: 5: конец] и объединение всех элементов между: начало и: конец в вектор

Answer 1

Вам необходимо обработать условие завершения - то есть, что должно возвращаться, когда вход s пуст?

А также при обнаружении :start и :end следует использовать first вместо (take 1 s). И вы можете упростить это с помощью деструктурирования.

(defn lazycombine
  ([s] (lazycombine s []))
  ([[a & b :as s] v]
   (if (empty? s)
     v
     (if (= a :start)
       (lazy-seq (lazycombine b v))
       (if (= a :end)
         (lazy-seq (cons v (lazycombine b [])))
         (lazy-seq (lazycombine b (conj v a))))))))


(def w '(:start 1 2 3 :end :start 7 7 :end))

(lazycombine w)
;; => ([1 2 3] [7 7])

Чтобы немного уменьшить сложность цикломати c, вы можете использовать condp для замены пары if:

(defn lazycombine
  ([s] (lazycombine s []))
  ([[a & b :as s] v]
   (if (empty? s)
     v
     (lazy-seq
      (condp = a
        :start (lazycombine b v)
        :end   (cons v (lazycombine b []))
        (lazycombine b (conj v a)))))))

Answer 2

Я бы сделал это так, используя take-while:

(ns tst.demo.core
  (:use tupelo.core tupelo.test))

(def data
  [:start 1 2 3 :end :start 7 7 :end])

(defn end-tag? [it] (= it :end))
(defn start-tag? [it] (= it :start))

(defn lazy-segments
  [data]
  (when-not (empty? data)
    (let [next-segment   (take-while #(not (end-tag? %)) data)
          data-next      (drop (inc (count next-segment)) data)
          segment-result (vec (remove #(start-tag? %) next-segment))]
      (cons segment-result
        (lazy-seq (lazy-segments data-next))))))

(dotest
  (println "result: " (lazy-segments data)))

Запустив, мы получим:

result:  ([1 2 3] [7 7])

Обратите внимание на контракт при рекурсивном построении последовательности с использованием cons ( ленивый или нет). Вы должны вернуть либо следующее значение в последовательности, либо nil. Предоставление от nil до cons аналогично предоставлению пустой последовательности:

 (cons 5 nil) => (5)
 (cons 5 [])  => (5)

Поэтому удобно использовать форму when для проверки условия завершения (вместо использования if и возвращает пустой вектор, когда последовательность должна заканчиваться).

Предположим, мы записали cons как простую рекурсию:

  (cons segment-result
    (lazy-segments data-next))

Это прекрасно работает и дает тот же результат. Единственное, что делает lazy-seq, - это задержка, когда происходит рекурсивный вызов . Поскольку lazy-seq является встроенным Clojure (специальная форма), он похож на loop/recur и не не использует стек , как обычная рекурсия. Таким образом, мы можем генерировать миллионы (или больше) значений в ленивой последовательности, не создавая StackOverflowError (на моем компьютере максимальный размер стека по умолчанию составляет ~ 4000). Рассмотрим бесконечную ленивую последовательность целых чисел, начинающуюся с 0:

(defn intrange
  [n]
  (cons n (lazy-seq (intrange (inc n)))))

(dotest
  (time
    (spyx (first (drop 1e6 (intrange 0))))))

Удаление первого миллиона целых чисел и взятие следующего - успешно и требует всего несколько миллисекунд:

(first (drop 1000000.0 (intrange 0))) => 1000000
"Elapsed time: 49.5 msecs"