0

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

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!

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

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

peter pun
  • 384
  • 1
  • 8
  • Why do you need the inner seq to be lazy, especially? Just out of interest... – pete23 Apr 27 '19 at 15:13
  • See this answer if you're concerned about cons laziness: https://stackoverflow.com/a/12390331 – Taylor Wood Apr 27 '19 at 16:28
  • Be sure to see `clojure.math.combinatorics`: https://github.com/clojure/math.combinatorics – Alan Thompson Apr 27 '19 at 22:44
  • @pete23: Sorry for the late response. The short answer is "mostly out of curiosity" (as I consider it an interesting problem regardless of its use). This being said, the inner laziness offers some minor space/time optimization. In my situation (simplifying a bit), for each part of a partition, a corresponding predicate is called (which recursively does similar computations) and a short-circuiting and/or is applied to the results. Although the calls are made lazily the parts are computed eagerly and occupy space ... – peter pun Apr 29 '19 at 18:52
  • 1
    ... Also notice that the fact that a partition of a sequence occupies almost the same space as the sequence is just a coincidence, valid for the monoid of sequences with concatenation. As a counterexample, think of natural numbers with addition. Indeed, my solution can be generalized for some class of monoids in a way that I can sketch if you are interested. – peter pun Apr 29 '19 at 18:54
  • @Taylor Wood: Thanks, but that answer contains mostly known facts and does not help me so much. @Alan Thompson: Thanks for the interesting suggestion. Although it does not immediately solve my problem, if I dig in the code I may come up with a solution. It seems that the most relevant function is `partitions`, which still does quite a different job. However, (a) from the tests I did I am not sure it achieves inner laziness and (b) its implementation is far from the simplicity/elegance I am looking for, containing some monstrous functions taking 11 arguments with 1-letter names!! – peter pun Apr 29 '19 at 18:59

1 Answers1

1

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

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.

l0st3d
  • 2,860
  • 1
  • 27
  • 29
  • Although you get inner laziness this way, it is not that "effective". (Before asking I had made a similar attempt by mapping `#(lazy-seq (cons a %))`.) The problem is that no matter if you request the first part of a partition or all of it, the same amount of calls to pt and split is made and the same space is occupied. As I said in the question, I think that a different algorithmic scheme is needed ... – peter pun Apr 29 '19 at 19:03
  • ... As for the unclojureiness, having a relatively generic, mathematically clear and concise solution, not tied onto much of Clojure's specific machinery, but using its lazy sequences, is of some value for me. (See also my response to pete23's comment, mentioning generalizations.) – peter pun Apr 29 '19 at 19:04