以不显眼的方式修剪Clojure序列中的循环

Question

我正在尝试编写一个惰性的seq来为给定的输入int生成Collatz序列。

我喜欢这个函数，因为它非常清晰地映射到数学定义：

(defn collatz
"Returns a lazy seq of the Collatz sequence starting at n and ending at 1 (if
ever)."
[n]
(letfn [(next-term [x]
(if (even? x)
(/ x 2)
(inc (* 3 x))))]
(iterate next-term n)))

问题在于，由于 Collatz 序列的行为方式，这会产生无限的序列：

(take 10 (collatz 5))
=> (5 16 8 4 2 1 4 2 1 4)

我可以通过添加(take-while #(not= 1 %) ...)来轻松删除循环，但 1是序列的一部分。我认为在循环之后修剪循环的所有其他方法都是丑陋的，并且混淆了 Collatz 序列的数学核心。

(我已经考虑过将看到的值存储在原子中并在take-while谓词中使用它，或者只是在原子中存储一个标志以获得类似的效果。但我觉得这里有一些更好、更美丽、更少侵入性的方式来做我想做的事。

所以我的问题：在无限序列中检测和修剪周期的干净方法是什么？或者，我可以以一种(也许使用for(的方式生成我的懒惰 seq，当它达到1(含(时会自动修剪？

Answer 1

下面看起来像是定义的或多或少的直译，并给出了您想要的结果：

(defn collatz-iter [x]
(cond (= x 1) nil
(even? x) (/ x 2)
:else (inc (* 3 x))))
(defn collatz [n]
(take-while some? (iterate collatz-iter n)))
(collatz 12) ;; => (12 6 3 10 5 16 8 4 2 1)

基本上，您可以使用nil作为停止序列的值，从而保留最后的 1。

Answer 2

你也可以使用另一种方法，即递归延迟序列生成。这对于这类任务来说很常见，不会破坏惰性序列抽象并避免创建中间序列：

(defn collatz [n]
(if (== n 1)
(list 1)
(lazy-seq (cons n (collatz (if (even? n)
(/ n 2)
(inc (* 3 n))))))))
user> (collatz 12)
;;=> (12 6 3 10 5 16 8 4 2 1)