Writing a lazy-as-possible unfoldr-like function to generate arbitrary factorizations

Question

problem formulation

Informally speaking, I want to write a function which, taking as input a function that generates binary factorizations and an element (usually neutral), creates an arbitrary length factorization generator. To be more specific, let us first define the function nfoldr in Clojure.

(defn nfoldr [f e]
  (fn rec [n]
    (fn [s]
      (if (zero? n)
        (if (empty? s) e)
        (if (seq s)
          (if-some [x ((rec (dec n)) (rest s))]
            (f (list (first s) x))))))))

Here nil is used with the meaning "undefined output, input not in function's domain". Additionally, let us view the inverse relation of a function f as a set-valued function defining inv(f)(y) = {x | f(x) = y}.

I want to define a function nunfoldr such that inv(nfoldr(f , e)(n)) = nunfoldr(inv(f) , e)(n) when for every element y inv(f)(y) is finite, for each binary function f, element e and natural number n.

Moreover, I want the factorizations to be generated as lazily as possible, in a 2-dimensional sense of laziness. My goal is that, when getting some part of a factorization for the first time, there does not happen (much) computation needed for next parts or next factorizations. Similarly, when getting one factorization for the first time, there does not happen computation needed for next ones, whereas all the previous ones get in effect fully realized.

In an alternative formulation we can use the following longer version of nfoldr, which is equivalent to the shorter one when e is a neutral element.

(defn nfoldr [f e]
  (fn [n]
    (fn [s]
      (if (zero? n)
        (if (empty? s) e)
        ((fn rec [n]
           (fn [s]
             (if (= 1 n)
               (if (and (seq s) (empty? (rest s))) (first s))
               (if (seq s)
                 (if-some [x ((rec (dec n)) (rest s))]
                   (f (list (first s) x)))))))
         n)))))

---

a special case

This problem is a generalization of the problem of generating partitions described in that question. Let us see how the old problem can be reduced to the current one. We have for every natural number n:

npt(n) = inv(nconcat(n)) = inv(nfoldr(concat2 , ())(n)) = nunfoldr(inv(concat2) , ())(n) = nunfoldr(pt2 , ())(n)

where:

• npt(n) generates n-ary partitions
• nconcat(n) computes n-ary concatenation
• concat2 computes binary concatenation
• pt2 generates binary partitions

So the following definitions give a solution to that problem.

(defn generate [step start]
  (fn [x] (take-while some? (iterate step (start x)))))

(defn pt2-step [[x y]]
  (if (seq y) (list (concat x (list (first y))) (rest y))))

(def pt2-start (partial list ()))

(def pt2 (generate pt2-step pt2-start))

(def npt (nunfoldr pt2 ()))

Answer 1

I will summarize my story of solving this problem, using the old one to create example runs, and conclude with some observations and proposals for extension.

---

solution 0

At first, I refined/generalized the approach I took for solving the old problem. Here I write my own versions of concat and map mainly for a better presentation and, in the case of concat, for some added laziness. Of course we can use Clojure's versions or mapcat instead.

(defn fproduct [f]
  (fn [s]
    (lazy-seq
      (if (and (seq f) (seq s))
        (cons
          ((first f) (first s))
          ((fproduct (rest f)) (rest s)))))))

(defn concat' [s]
  (lazy-seq
    (if (seq s)
      (if-let [x (seq (first s))]
        (cons (first x) (concat' (cons (rest x) (rest s))))
        (concat' (rest s))))))

(defn map' [f]
  (fn rec [s]
    (lazy-seq
      (if (seq s)
        (cons (f (first s)) (rec (rest s)))))))

(defn nunfoldr [f e]
  (fn rec [n]
    (fn [x]
      (if (zero? n)
        (if (= e x) (list ()) ())
        ((comp
           concat'
           (map' (comp
                   (partial apply map)
                   (fproduct (list
                               (partial partial cons)
                               (rec (dec n))))))
           f)
         x)))))

In an attempt to get inner laziness we could replace (partial partial cons) with something like (comp (partial partial concat) list). Although this way we get inner LazySeqs, we do not gain any effective laziness because, before consing, most of the computation required for fully realizing the rest part takes place, something that seems unavoidable within this general approach. Based on the longer version of nfoldr, we can also define the following faster version.

(defn nunfoldr [f e]
  (fn [n]
    (fn [x]
      (if (zero? n)
        (if (= e x) (list ()) ())
        (((fn rec [n]
            (fn [x] (println \< x \>)
              (if (= 1 n)
                (list (list x))
                ((comp
                   concat'
                   (map' (comp
                           (partial apply map)
                           (fproduct (list
                                       (partial partial cons)
                                       (rec (dec n))))))
                   f)
                 x))))
          n)
         x)))))

Here I added a println call inside the main recursive function to get some visualization of eagerness. So let us demonstrate the outer laziness and inner eagerness.

user=> (first ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
(() () () () (0 1 2))
user=> (ffirst ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
()

---

solution 1

Then I thought of a more promising approach, using the function:

(defn transpose [s]
  (lazy-seq
    (if (every? seq s)
      (cons
        (map first s)
        (transpose (map rest s))))))

To get the new solution we replace the previous argument in the map' call with:

(comp
  (partial map (partial apply cons))
  transpose
  (fproduct (list
              repeat
              (rec (dec n)))))

Trying to get inner laziness we could replace (partial apply cons) with #(cons (first %) (lazy-seq (second %))) but this is not enough. The problem lies in the (every? seq s) test inside transpose, where checking a lazy sequence of factorizations for emptiness (as a stopping condition) results in realizing it.

---

solution 2

A first way to tackle the previous problem that came to my mind was to use some additional knowledge about the number of n-ary factorizations of an element. This way we can repeat a certain number of times and use only this sequence for the stopping condition of transpose. So we will replace the test inside transpose with (seq (first s)), add an input count to nunfoldr and replace the argument in the map' call with:

(comp
  (partial map #(cons (first %) (lazy-seq (second %))))
  transpose
  (fproduct (list
              (partial apply repeat)
              (rec (dec n))))
  (fn [[x y]] (list (list ((count (dec n)) y) x) y)))

Let us turn to the problem of partitions and define:

(defn npt-count [n]
   (comp
     (partial apply *)
     #(map % (range 1 n))
     (partial comp inc)
     (partial partial /)
     count))

(def npt (nunfoldr pt2 () npt-count))

Now we can demonstrate outer and inner laziness.

user=> (first ((npt 5) (range 3)))
< (0 1 2) >
(< (0 1 2) >
() < (0 1 2) >
() < (0 1 2) >
() < (0 1 2) >
() (0 1 2))
user=> (ffirst ((npt 5) (range 3)))
< (0 1 2) >
()

However, the dependence on additional knowledge and the extra computational cost make this solution unacceptable.

---

solution 3

Finally, I thought that in some crucial places I should use a kind of lazy sequences "with a non-lazy end", in order to be able to check for emptiness without realizing. An empty such sequence is just a non-lazy empty list and overall they behave somewhat like the lazy-conss of the early days of Clojure. Using the definitions given below we can reach an acceptable solution, which works under the assumption that always at least one of the concat'ed sequences (when there is one) is non-empty, something that holds in particular when every element has at least one binary factorization and we are using the longer version of nunfoldr.

(def lazy? (partial instance? clojure.lang.IPending))
(defn empty-eager? [x] (and (not (lazy? x)) (empty? x)))

(defn transpose [s]
  (lazy-seq
    (if-not (some empty-eager? s)
      (cons
        (map first s)
        (transpose (map rest s))))))

(defn concat' [s]
  (if-not (empty-eager? s)
    (lazy-seq
      (if-let [x (seq (first s))]
        (cons (first x) (concat' (cons (rest x) (rest s))))
        (concat' (rest s))))
    ()))

(defn map' [f]
  (fn rec [s]
    (if-not (empty-eager? s)
      (lazy-seq (cons (f (first s)) (rec (rest s))))
      ())))

Note that in this approach the input function f should produce lazy sequences of the new kind and the resulting n-ary factorizer will also produce such sequences. To take care of the new input requirement, for the problem of partitions we define:

(defn pt2 [s]
  (lazy-seq
    (let [start (list () s)]
      (cons
        start
        ((fn rec [[x y]]
           (if (seq y)
             (lazy-seq
               (let [step (list (concat x (list (first y))) (rest y))]
                 (cons step (rec step))))
             ()))
         start)))))

Once again, let us demonstrate outer and inner laziness.

user=> (first ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
(< (0 1 2) >
() < (0 1 2) >
() < (0 1 2) >
() () (0 1 2))
user=> (ffirst ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
()

To make the input and output use standard lazy sequences (sacrificing a bit of laziness), we can add:

(defn lazy-end->eager-end [s]
  (if (seq s)
    (lazy-seq (cons (first s) (lazy-end->eager-end (rest s))))
    ()))

(defn eager-end->lazy-end [s]
  (lazy-seq
    (if-not (empty-eager? s)
      (cons (first s) (eager-end->lazy-end (rest s))))))

(def nunfoldr
  (comp
    (partial comp (partial comp eager-end->lazy-end))
    (partial apply nunfoldr)
    (fproduct (list
                (partial comp lazy-end->eager-end)
                identity))
    list))

---

observations and extensions

While creating solution 3, I observed that the old mechanism for lazy sequences in Clojure might not be necessarily inferior to the current one. With the transition, we gained the ability to create lazy sequences without any substantial computation taking place but lost the ability to check for emptiness without doing the computation needed to get one more element. Because both of these abilities can be important in some cases, it would be nice if a new mechanism was introduced, which would combine the advantages of the previous ones. Such a mechanism could use again an outer LazySeq thunk, which when forced would return an empty list or a Cons or another LazySeq or a new LazyCons thunk. This new thunk when forced would return a Cons or perhaps another LazyCons. Now empty? would force only LazySeq thunks while first and rest would also force LazyCons. In this setting map could look like this:

(defn map [f s]
   (lazy-seq
     (if (empty? s) ()
       (lazy-cons
         (cons (f (first s)) (map f (rest s)))))))

I have also noticed that the approach taken from solution 1 onwards lends itself to further generalization. If inside the argument in the map' call in the longer nunfoldr we replace cons with concat, transpose with some implementation of Cartesian product and repeat with another recursive call, we can then create versions that "split at different places". For example, using the following as the argument we can define a nunfoldm function that "splits in the middle" and corresponds to an easy-to-imagine nfoldm. Note that all "splitting strategies" are equivalent when f is associative.

(comp
  (partial map (partial apply concat))
  cproduct
  (fproduct (let [n-half (quot n 2)]
              (list (rec n-half) (rec (- n n-half))))))

Another natural modification would allow for infinite factorizations. To achieve this, if f generated infinite factorizations, nunfoldr(f , e)(n) should generate the factorizations in an order of type ω, so that each one of them could be produced in finite time.

Other possible extensions include dropping the n parameter, creating relational folds (in correspondence with the relational unfolds we consider here) and generically handling algebraic data structures other than sequences as input/output. This book, which I have just discovered, seems to contain valuable relevant information, given in a categorical/relational language.

Finally, to be able to do this kind of programming more conveniently, we could transfer it into a point-free, algebraic setting. This would require constructing considerable "extra machinery", in fact almost making a new language. This paper demonstrates such a language.