在Clojure序列中修剪周期的不引人注目的方法

Question

我正在尝试编写一个lazy seq来为给定的输入int 生成Collat​​z序列.

我喜欢这个函数,因为它是如此干净地映射到数学定义:

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

问题在于,由于Collat​​z序列的行为方式,这会产生无限的seq:

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

我可以通过添加来轻松地删除循环(take-while #(not= 1 %) ...),但是1 是序列的一部分.我认为所有其他的方法都会在一个丑陋之后修剪周期,并使Collat​​z序列的数学核心模糊不清.

(我已经考虑将看到的值存储在一个原子中并在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.