编写一个 lazy-as-possible unfoldr-like 函数来生成任意分解
Writing a lazy-as-possible unfoldr-like function to generate arbitrary factorizations
问题表述
通俗地说，我想编写一个函数，将生成二进制分解的函数和一个元素（通常是中性的）作为输入，创建一个任意长度的分解生成器。更具体地说，让我们先在Clojure中定义函数nfoldr。
(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))))))))
这里用nil表示"undefined output, input not in function's domain"的意思。此外，让我们将函数 f 的逆关系视为定义 inv(f)(y) = {x | f(x) = y}.
的集值函数
我想定义一个函数 nunfoldr 使得 inv(nfoldr(f , e)(n)) = nunfoldr(inv(f) , e)(n) 对于每个元素 y inv(f)(y) 都是有限的，对于每个二元函数 f，元素e和自然数n.
此外，我希望在二维惰性意义上尽可能惰性地生成因式分解。我的目标是，当第一次获得分解的某些部分时，下一部分或下一个分解所需的计算不会发生（很多）。同样，当第一次得到一个因式分解时，不会发生下一个因式分解所需的计算，而之前的所有因式分解实际上都完全实现了。
在替代公式中，我们可以使用以下较长版本的 nfoldr，当 e 是中性元素时，它等效于较短的版本。
(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)))))
特例
这个问题是that question中描述的分区生成问题的泛化。让我们看看如何将旧问题简化为当前问题。我们对每个自然数都有 n:
npt(n) = inv(nconcat(n)) = inv(nfoldr(concat2 , ())(n)) = nunfoldr(inv(concat2) , ())(n) = nunfoldr(pt2 , ())(n)
其中：
npt(n) 生成 n 元分区nconcat(n) 计算 n 元级联 concat2 计算二进制连接pt2 生成二进制分区
所以下面的定义给出了这个问题的解决方案。
(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 ()))
我将总结我解决这个问题的故事，使用旧问题创建示例运行，并以一些观察和扩展建议作为结尾。
解决方案 0
起初，我refined/generalized解决老问题的方法。在这里我写了我自己的 concat 和 map 版本主要是为了更好的展示，并且在 concat 的情况下，为了一些额外的懒惰。当然我们可以使用 Clojure 的版本或者 mapcat 来代替。
(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)))))
为了获得内心的懒惰，我们可以用 (comp (partial partial concat) list) 之类的东西替换 (partial partial cons)。尽管通过这种方式我们获得了内部 LazySeqs，但我们没有获得任何有效的惰性，因为在 consing 之前，完全实现 rest 部分所需的大部分计算都发生了，这在这种一般方法中似乎是不可避免的。基于nfoldr的较长版本，我们还可以定义以下较快的版本。
(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)))))
在这里，我在主递归函数中添加了一个 println 调用，以获得一些渴望的可视化。那么让我们来展示一下外在的懒惰和内心的渴望吧。
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) >
()
解决方案 1
然后我想到了一个更有前途的方法，使用函数：
(defn transpose [s]
(lazy-seq
(if (every? seq s)
(cons
(map first s)
(transpose (map rest s))))))
为了获得新的解决方案，我们将 map' 调用中的先前参数替换为：
(comp
(partial map (partial apply cons))
transpose
(fproduct (list
repeat
(rec (dec n)))))
我们可以用 #(cons (first %) (lazy-seq (second %))) 替换 (partial apply cons) 来尝试获得内心的懒惰，但这还不够。问题在于 transpose 内的 (every? seq s) 测试，其中检查惰性因式分解序列是否为空（作为停止条件）导致实现它。
解决方案 2
解决我想到的前一个问题的第一种方法是使用一些关于元素的 n 元分解次数的额外知识。这样我们就可以repeat一定次数，只用这个序列作为transpose的停止条件。因此，我们将 transpose 中的测试替换为 (seq (first s))，将输入 count 添加到 nunfoldr 并将 map' 调用中的参数替换为：
(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)))
让我们转向分区问题并定义：
(defn npt-count [n]
(comp
(partial apply *)
#(map % (range 1 n))
(partial comp inc)
(partial partial /)
count))
(def npt (nunfoldr pt2 () npt-count))
现在我们可以展示外在和内在的懒惰了。
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) >
()
但是，对额外知识的依赖和额外的计算成本使该解决方案无法接受。
解决方案 3
最后，我认为在一些关键的地方我应该使用一种惰性序列"with a non-lazy end"，以便能够在没有意识到的情况下检查是否为空。一个空的这样的序列只是一个非惰性空列表，总体上它们的行为有点像 Clojure 早期的 lazy-conss。使用下面给出的定义，我们可以得出一个可接受的解决方案，该解决方案的工作假设总是 concat'ed 序列中的至少一个（当有一个时）是非空的，特别是当每个元素都成立时至少有一个二元因式分解，我们使用的是较长版本的 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))))
())))
请注意，在这种方法中，输入函数 f 应该生成新类型的惰性序列，并且生成的 n 元分解器也将生成此类序列。为了处理新的输入需求，对于分区问题我们定义：
(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)))))
再一次，让我们展示一下外在和内在的懒惰。
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) >
()
为了使输入和输出使用标准惰性序列（牺牲一点惰性），我们可以添加：
(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))
观察和扩展
在创建解决方案 3 时，我观察到 Clojure 中用于惰性序列的旧机制不一定不如当前机制。通过过渡，我们获得了创建惰性序列的能力，而无需进行任何大量计算，但失去了在不进行获取更多元素所需的计算的情况下检查是否为空的能力。因为这两种能力在某些情况下都可能很重要，所以如果引入一种新机制会很好，它将结合以前机制的优点。这样的机制可以再次使用外部 LazySeq thunk，当强制使用时它将 return 空列表或 Cons 或另一个 LazySeq 或新的 LazyCons thunk .这个新的 thunk 在被迫时会 return 一个 Cons 或者另一个 LazyCons。现在 empty? 只会强制 LazySeq thunk，而 first 和 rest 也会强制 LazyCons。在此设置中 map 可能如下所示：
(defn map [f s]
(lazy-seq
(if (empty? s) ()
(lazy-cons
(cons (f (first s)) (map f (rest s)))))))
我还注意到，从解决方案 1 开始采用的方法有助于进一步推广。如果在较长的 nunfoldr 中 map' 调用的参数内，我们将 cons 替换为 concat，将 transpose 替换为笛卡尔积的某些实现和 repeat 通过另一个递归调用，我们可以创建 "split at different places" 的版本。例如，使用以下作为参数，我们可以定义一个 nunfoldm 函数，它 "splits in the middle" 对应于一个易于想象的 nfoldm。请注意，当 f 具有关联性时，所有 "splitting strategies" 都是等价的。
(comp
(partial map (partial apply concat))
cproduct
(fproduct (let [n-half (quot n 2)]
(list (rec n-half) (rec (- n n-half))))))
另一个自然修改将允许无限分解。为了实现这一点，如果 f 生成无限因式分解，nunfoldr(f , e)(n) 应该以 ω 类型的顺序生成因式分解，以便它们中的每一个都可以在有限时间内产生。
其他可能的扩展包括删除 n 参数、创建关系折叠（与我们在此考虑的关系展开相对应）以及将除序列以外的代数数据结构一般处理为 input/output。 This book，我刚刚发现，似乎包含有价值的相关信息，以 categorical/relational 语言给出。
最后，为了能够更方便地进行此类编程，我们可以将其转换为无点代数设置。这将需要构建相当大的 "extra machinery"，实际上几乎是创造一种新语言。 This paper演示了这样一种语言。
问题表述
通俗地说，我想编写一个函数，将生成二进制分解的函数和一个元素（通常是中性的）作为输入，创建一个任意长度的分解生成器。更具体地说，让我们先在Clojure中定义函数nfoldr。
(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))))))))
这里用nil表示"undefined output, input not in function's domain"的意思。此外，让我们将函数 f 的逆关系视为定义 inv(f)(y) = {x | f(x) = y}.
我想定义一个函数 nunfoldr 使得 inv(nfoldr(f , e)(n)) = nunfoldr(inv(f) , e)(n) 对于每个元素 y inv(f)(y) 都是有限的，对于每个二元函数 f，元素e和自然数n.
此外，我希望在二维惰性意义上尽可能惰性地生成因式分解。我的目标是，当第一次获得分解的某些部分时，下一部分或下一个分解所需的计算不会发生（很多）。同样，当第一次得到一个因式分解时，不会发生下一个因式分解所需的计算，而之前的所有因式分解实际上都完全实现了。
在替代公式中，我们可以使用以下较长版本的 nfoldr，当 e 是中性元素时，它等效于较短的版本。
(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)))))
特例
这个问题是that question中描述的分区生成问题的泛化。让我们看看如何将旧问题简化为当前问题。我们对每个自然数都有 n:
npt(n) = inv(nconcat(n)) = inv(nfoldr(concat2 , ())(n)) = nunfoldr(inv(concat2) , ())(n) = nunfoldr(pt2 , ())(n)
其中：
npt(n)生成n元分区nconcat(n)计算n元级联concat2计算二进制连接pt2生成二进制分区
所以下面的定义给出了这个问题的解决方案。
(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 ()))
我将总结我解决这个问题的故事，使用旧问题创建示例运行，并以一些观察和扩展建议作为结尾。
解决方案 0
起初，我refined/generalized解决老问题的方法。在这里我写了我自己的 concat 和 map 版本主要是为了更好的展示，并且在 concat 的情况下，为了一些额外的懒惰。当然我们可以使用 Clojure 的版本或者 mapcat 来代替。
(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)))))
为了获得内心的懒惰，我们可以用 (comp (partial partial concat) list) 之类的东西替换 (partial partial cons)。尽管通过这种方式我们获得了内部 LazySeqs，但我们没有获得任何有效的惰性，因为在 consing 之前，完全实现 rest 部分所需的大部分计算都发生了，这在这种一般方法中似乎是不可避免的。基于nfoldr的较长版本，我们还可以定义以下较快的版本。
(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)))))
在这里，我在主递归函数中添加了一个 println 调用，以获得一些渴望的可视化。那么让我们来展示一下外在的懒惰和内心的渴望吧。
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) >
()
解决方案 1
然后我想到了一个更有前途的方法，使用函数：
(defn transpose [s]
(lazy-seq
(if (every? seq s)
(cons
(map first s)
(transpose (map rest s))))))
为了获得新的解决方案，我们将 map' 调用中的先前参数替换为：
(comp
(partial map (partial apply cons))
transpose
(fproduct (list
repeat
(rec (dec n)))))
我们可以用 #(cons (first %) (lazy-seq (second %))) 替换 (partial apply cons) 来尝试获得内心的懒惰，但这还不够。问题在于 transpose 内的 (every? seq s) 测试，其中检查惰性因式分解序列是否为空（作为停止条件）导致实现它。
解决方案 2
解决我想到的前一个问题的第一种方法是使用一些关于元素的 n 元分解次数的额外知识。这样我们就可以repeat一定次数，只用这个序列作为transpose的停止条件。因此，我们将 transpose 中的测试替换为 (seq (first s))，将输入 count 添加到 nunfoldr 并将 map' 调用中的参数替换为：
(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)))
让我们转向分区问题并定义：
(defn npt-count [n]
(comp
(partial apply *)
#(map % (range 1 n))
(partial comp inc)
(partial partial /)
count))
(def npt (nunfoldr pt2 () npt-count))
现在我们可以展示外在和内在的懒惰了。
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) >
()
但是，对额外知识的依赖和额外的计算成本使该解决方案无法接受。
解决方案 3
最后，我认为在一些关键的地方我应该使用一种惰性序列"with a non-lazy end"，以便能够在没有意识到的情况下检查是否为空。一个空的这样的序列只是一个非惰性空列表，总体上它们的行为有点像 Clojure 早期的 lazy-conss。使用下面给出的定义，我们可以得出一个可接受的解决方案，该解决方案的工作假设总是 concat'ed 序列中的至少一个（当有一个时）是非空的，特别是当每个元素都成立时至少有一个二元因式分解，我们使用的是较长版本的 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))))
())))
请注意，在这种方法中，输入函数 f 应该生成新类型的惰性序列，并且生成的 n 元分解器也将生成此类序列。为了处理新的输入需求，对于分区问题我们定义：
(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)))))
再一次，让我们展示一下外在和内在的懒惰。
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) >
()
为了使输入和输出使用标准惰性序列（牺牲一点惰性），我们可以添加：
(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))
观察和扩展
在创建解决方案 3 时，我观察到 Clojure 中用于惰性序列的旧机制不一定不如当前机制。通过过渡，我们获得了创建惰性序列的能力，而无需进行任何大量计算，但失去了在不进行获取更多元素所需的计算的情况下检查是否为空的能力。因为这两种能力在某些情况下都可能很重要，所以如果引入一种新机制会很好，它将结合以前机制的优点。这样的机制可以再次使用外部 LazySeq thunk，当强制使用时它将 return 空列表或 Cons 或另一个 LazySeq 或新的 LazyCons thunk .这个新的 thunk 在被迫时会 return 一个 Cons 或者另一个 LazyCons。现在 empty? 只会强制 LazySeq thunk，而 first 和 rest 也会强制 LazyCons。在此设置中 map 可能如下所示：
(defn map [f s]
(lazy-seq
(if (empty? s) ()
(lazy-cons
(cons (f (first s)) (map f (rest s)))))))
我还注意到，从解决方案 1 开始采用的方法有助于进一步推广。如果在较长的 nunfoldr 中 map' 调用的参数内，我们将 cons 替换为 concat，将 transpose 替换为笛卡尔积的某些实现和 repeat 通过另一个递归调用，我们可以创建 "split at different places" 的版本。例如，使用以下作为参数，我们可以定义一个 nunfoldm 函数，它 "splits in the middle" 对应于一个易于想象的 nfoldm。请注意，当 f 具有关联性时，所有 "splitting strategies" 都是等价的。
(comp
(partial map (partial apply concat))
cproduct
(fproduct (let [n-half (quot n 2)]
(list (rec n-half) (rec (- n n-half))))))
另一个自然修改将允许无限分解。为了实现这一点，如果 f 生成无限因式分解，nunfoldr(f , e)(n) 应该以 ω 类型的顺序生成因式分解，以便它们中的每一个都可以在有限时间内产生。
其他可能的扩展包括删除 n 参数、创建关系折叠（与我们在此考虑的关系展开相对应）以及将除序列以外的代数数据结构一般处理为 input/output。 This book，我刚刚发现，似乎包含有价值的相关信息，以 categorical/relational 语言给出。
最后，为了能够更方便地进行此类编程，我们可以将其转换为无点代数设置。这将需要构建相当大的 "extra machinery"，实际上几乎是创造一种新语言。 This paper演示了这样一种语言。