Как определить разбиения (факторизации относительно конкатенации) последовательности как ленивую последовательность ленивых последовательностей в Clojure - PullRequest
Новая
       47

Как определить разбиения (факторизации относительно конкатенации) последовательности как ленивую последовательность ленивых последовательностей в Clojure

0 голосов
/ 27 апреля 2019

Я новичок в Clojure и хочу определить функцию pt, принимающую в качестве аргументов число n и последовательность s и возвращающую все разделы s в n частях, то есть ее факторизации в отношении n -конкатенации. например, (pt 3 [0 1 2]) должно выдать: 

(([] [] [0 1 2]) ([] [0] [1 2]) ([] [0 1] [2]) ([] [0 1 2] []) ([0] [] [1 2]) ([0] [1] [2]) ([0] [1 2] []) ([0 1] [] [2]) ([0 1] [2] []) ([0 1 2] [] []))

с неважным порядком. В частности, я хочу, чтобы результат был ленивой последовательностью ленивых последовательностей векторов.

Моя первая попытка использования такой функции была следующей: 

(defn pt [n s]
  (lazy-seq
    (if (zero? n)
      (when (empty? s) [nil])
      ((fn split [a b]
         (concat
           (map (partial cons a) (pt (dec n) b))
           (when-let [[bf & br] (seq b)] (split (conj a bf) br))))
       [] s))))

После этого я написал несколько менее лаконичную версию, которая уменьшает временную сложность, избегая бесполезных сравнений для разделов из 1 части, приведенных ниже: 

(defn pt [n s]
  (lazy-seq
    (if (zero? n)
      (when (empty? s) [nil])
      ((fn pt>0 [n s]
         (lazy-seq
           (if (= 1 n)
             [(cons (vec s) nil)]
             ((fn split [a b]
                (concat
                  (map (partial cons a) (pt>0 (dec n) b))
                  (when-let [[bf & br] (seq b)] (split (conj a bf) br))))
              [] s))))
       n s))))

Проблема с этими решениями состоит в том, что, хотя они работают, они производят ленивую последовательность (не ленивых) минусов, и я подозреваю, что для достижения «внутренней лени» должен быть применен совершенно другой подход. Так что любые исправления, предложения, объяснения приветствуются!

EDIT : Прочитав ответ l0st3d, я подумал, что должен пояснить, что я хочу, чтобы раздел не был просто LazySeq, а был «действительно ленивым», в том смысле, что часть вычисляется и хранится в памяти только при запросе. Например, обе функции, приведенные ниже, генерируют LazySeq, но только первая из них создает «действительно ленивую» последовательность. 

(defn f [n]
  (if (neg? n)
    (lazy-seq nil)
    (lazy-seq (cons n (f (dec n))))))

(defn f [n]
  (if (neg? n)
    (lazy-seq nil)
    (#(lazy-seq (cons n %)) (f (dec n)))))

Таким образом, отображение (partial concat [a]) или #(lazy-seq (cons a %)) вместо (partial cons a) не решает проблему.

1 Ответ

0 голосов
/ 29 апреля 2019

Звонок cons в вашем split inline fn - единственное место, где проявляется рвение. Вы можете заменить это чем-то, что лениво создает список, например concat: 

(defn pt [n s]
  (lazy-seq
   (if (zero? n)
     (when (empty? s) [nil])
     ((fn split [a b]
        (concat
         (map (partial concat [a]) (pt (dec n) b))
         (when-let [[bf & br] (seq b)] (split (conj a bf) br))))
      [] s))))

(every? #(= clojure.lang.LazySeq (class %)) (pt 3 [0 1 2 3])) ;; => true

Но, читая код, я чувствую, что это довольно нелепо, и я думаю, что это связано с использованием рекурсии. Часто вы используете такие вещи, как reductions, partition-by, split-at и так далее, чтобы делать подобные вещи. Я чувствую, что также должен быть способ сделать это преобразователем и отделить лень от обработки (так что вы можете использовать sequence, чтобы сказать, что вы хотите лениво), но у меня нет времени, чтобы решить это правильно сейчас. Я постараюсь вернуться с более полным ответом в ближайшее время.

...