我需要创建一个函数，当给定一个潜在无限序列的有限序列时，它会产生作为其“笛卡尔积”的序列。
即给定序列
'((1 2) (3 4))
该函数产生（某种顺序）：
'((1 3) (1 4) (2 3) (2 4)
重要，对于笛卡尔乘积p列表中的每个ps，必须有一些自然数n，使得(= p (last (take n ps)))。或者，非正式地，您只需要遍历序列有限的数量即可到达序列中的任何元素。
此条件在处理无限列表时很重要。
在Haskell，这就是我要做的：
interleave :: [a] -> [a] -> [a]
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs
combine :: [[a]] -> [[a]]
combine = foldr prod [[]]
where
prod xs css = foldr1 interleave [ [x:cs | cs <- css] | x <- xs]
并调用它会得到以下信息：
combine [[0..] [0..]] = [[0,0,0],[1,0,0],[,1,0],[2,0,0],[0,0,1],[1,1,0],...
因此，我试图在Clojure中复制它，就像这样，（几乎是直接翻译）：
(defn interleave
"Returns a lazy sequence of the interleavings of sequences `xs` and `ys`
(both potentially infinite), leaving no elements discarded."
[xs ys]
(lazy-seq
(if-let [[x & xs*] (seq xs)]
(cons x (interleave ys xs*))
ys)))
(defn interleave*
"Converts a sequence of potentially infinite sequences into its lazy
interleaving."
[xss]
(lazy-seq
(when-let [[xs & xss*] (seq xss)]
(interleave xs (interleave* xss*)))))
(defn combine
"Takes a finite sequence of potentially infinite sequences, and combines
them to produce a possibly infinite sequence of their cartesian product."
[xss]
(if-let [[xs & xss*] (seq xss)]
(interleave*
(for [x xs]
(for [cs (combine xss*)]
(lazy-seq (cons x cs)))))
'(()) ))
但是当我跑步时：
(take 1 (combine [(range) (range)]))
我得到：
StackOverflowError cfg.util/combine/iter--3464--3468/fn--3469/fn--3470/iter--3471--3475/fn--3476
所以，如何使它足够懒惰，以避免堆栈溢出？确实，我不了解Clojure的惰性序列模型如何工作，这是主要问题。
[我认为您的解决方案可能在算法上难以处理，并一次次地重建子序列，就像简单的斐波那契函数一样：
(defn fib [n]
(case n
(0N 1N) n
(+ (fib (- n 1)) (fib (- n 2)))))
...重新计算其先例。
无论如何，在[100 10]和(range)的笛卡尔积中搜索(range)：
(first (filter #{[100 10]} (combine [(range) (range)])))
...在合理的时间内未返回。
我可以为您提供一个更快但不那么优雅的解决方案。
首先，有几个实用程序：
[Something from @amalloy以计算有限序列的笛卡尔积：
(defn cart [colls]
(if (empty? colls)
'(())
(for [x (first colls)
more (cart (rest colls))]
(cons x more))))
从Clojure Cookbook改编来映射映射值的功能：
(defn map-vals [f m] (zipmap (keys m) (map f (vals m))))
现在我们想要的函数，我称之为enum-cart，因为它枚举了甚至无限序列的笛卡尔积：
(defn enum-cart [colls]
(let [ind-colls (into (sorted-map) (map-indexed (fn [n s] [n (seq s)]) colls))
entries ((fn tins [ss] (let [ss (select-keys ss (map key (filter val ss)))]
(lazy-seq
(if (seq ss)
(concat
(map-vals first ss)
(tins (map-vals next ss)))))))
ind-colls)
seens (reductions
(fn [a [n x]] (update-in a [n] conj x))
(vec (repeat (count colls) []))
entries)]
(mapcat
(fn [sv [n x]] (cart (assoc sv n [x])))
seens entries)))
想法是生成索引的条目序列，绕过未用尽的序列。由此，我们生成了一个伴随序列，该序列是我们已经从每个序列中看到的。我们将这两个配对，将新元素的自由笛卡尔积与其他序列的自由笛卡尔积相结合。答案是这些免费产品的串联。
例如
(enum-cart [(range 3) (range 10 15)])
...产生
((0 10)
(1 10)
(0 11)
(1 11)
(2 10)
(2 11)
(0 12)
(1 12)
(2 12)
(0 13)
(1 13)
(2 13)
(0 14)
(1 14)
(2 14))
和
(first (filter #{[100 10]} (enum-cart [(range) (range)])))
;(100 10)
...或多或少立即返回。
Notes
所以，我知道了。问题是一个微妙但令人沮丧的问题。问题源于我执行的结构分解，基本上是在每个函数中：我使用了这种成语：[x & xs*] (seq xs)，但是，这实现了xs*的第一个元素，并且实现了x。此行为类似于如果您分别使用first和next来获取列表的开头和结尾，将会看到的内容。
使用first / rest而不是通过这种方式进行解构来解决堆栈溢出：
(defn interleave
"Returns a lazy sequence of the interleavings of sequences `xs` and `ys`
(both potentially infinite), leaving no elements discarded."
[xs ys]
(lazy-seq
(if-let [xs* (seq xs)]
(cons (first xs*) (interleave ys (rest xs*)))
ys)))
(defn interleave*
"Converts a sequence of potentially infinite sequences into its lazy
interleaving."
[xss]
(lazy-seq
(when-let [xss* (seq xss)]
(interleave (first xss*)
(interleave* (rest xss*))))))
(defn combine
"Takes a finite sequence of potentially infinite sequences, and combines
them to produce a possibly infinite sequence of their cartesian product."
[xss]
(if-let [xss* (seq xss)]
(interleave*
(for [x (first xss*)]
(for [cs (combine (rest xss*))]
(lazy-seq (cons x cs)))))
'(()) ))
运行它，我们得到：
(= (take 5 (combine [(range) (range) (range)]))
'((0 0 0) (1 0 0) (0 1 0) (2 0 0) (0 0 1)))