如何在Clojure中将序列的分区(分解并置分解)定义为惰性序列的惰性序列 [英] How to define the partitions (factorizations w.r.t. concatenation) of a sequence as a lazy sequence of lazy sequences in Clojure

问题描述

我是Clojure的新手，我想定义一个函数pt，将一个数字n和一个序列s作为参数，并返回n部分中的所有s分区，即其因式分解关于n-串联.例如(pt 3 [0 1 2])应该产生:

I am new to Clojure and I want to define a function pt taking as arguments a number n and a sequence s and returning all the partitions of s in n parts, i.e. its factorizations with respect to n-concatenation. for example (pt 3 [0 1 2]) should produce:

(([] [] [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] [] []))

，顺序不重要. 具体来说，我希望结果是向量的惰性序列的惰性序列.

with the order being unimportant. Specifically, I want the result to be a lazy sequence of lazy sequences of vectors.

我对这种功能的第一次尝试是:

My first attempt for such a function was the following:

(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部分分区的无用比较来降低时间复杂度，如下所示:

After that, I wrote a somewhat less concise version which reduces the time complexity by avoiding useless comparisons for 1-part partitions, given below:

(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))))

这些解决方案的问题在于，尽管它们有效，但它们会产生(非懒惰)缺点的懒惰序列，我怀疑必须采取完全不同的方法来实现内部懒惰".因此，欢迎任何更正，建议，解释！

The problem with these solutions is that, although they work, they produce a lazy sequence of (non-lazy) cons's and I suspect that quite a different approach must be taken to achieve the "inner laziness". So any corrections, suggestions, explanations are welcome!

编辑:在阅读l0st3d的答案后，我想我应该明确一点，我不希望分区只是LazySeq而是真正的懒惰"，就意味着要计算一部分并且仅在需要时才保留在内存中. 例如，下面给出的两个函数都产生LazySeq，但是只有第一个产生真正的惰性"序列.

EDIT: After reading l0st3d's answer I thought I should make clear that I do not want a partition just to be a LazySeq but to be "really lazy", in the sense that a part is computed and held in memory only when it is requested. For example, both of the functions given below produce LazySeq's but only the first one produces a "really lazy" sequence.

(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)不能解决问题.

So mapping (partial concat [a]) or #(lazy-seq (cons a %)) instead of (partial cons a) does not solve the problem.

推荐答案

split内联fn中的cons调用是唯一引入渴望的地方.您可以将其替换为懒散地构造列表的内容，例如concat:

The cons call in your split inline fn is the only place where eagerness is being introduced. You could replace that with something that lazily constructs a list, like 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

但是，阅读代码后，我感觉这完全不是克洛瑞(Clojurey)，我认为这与递归的使用有关.通常，您会使用诸如reductions，partition-by，split-at之类的东西来执行此类操作.我觉得也应该有一种方法可以使它成为换能器，并从处理过程中分离出惰性(因此您可以使用sequence表示您懒惰地想要它)，但是我没有时间来解决这个问题现在.我将尽力尽快提供更完整的答案.

But, reading the code I feel like it's fairly unClojurey, and I think that's to do with the use of recursion. Often you'd use things like reductions, partition-by, split-at and so to do this sort of thing. I feel like there should also be a way to make this a transducer and separate out the lazyness from the processing (so you can use sequence to say you want it lazily), but I haven't got time to work that out right now. I'll try and come back with a more complete answer soon.

这篇关于如何在Clojure中将序列的分区(分解并置分解)定义为惰性序列的惰性序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！