clojure - 欧拉项目问题 14 的惰性序列 "Look Ahead"

Question

我正在尝试解决Project Euler Problem 14以一种懒惰的方式。不幸的是，我可能正在尝试做不可能的事情:创建一个惰性序列，它既是惰性的，又以某种方式“向前看”尚未计算的值。

我为测试正确性而编写的非惰性版本是:

(defn chain-length [num]
  (loop [len 1
         n  num]
(cond
  (= n 1) len 
  (odd? n) (recur (inc len) (+ 1 (* 3 n)))
  true     (recur (inc len) (/ n 2)))))

这有效，但速度非常慢。我当然可以记住:

(def memoized-chain
   (memoize
     (fn [n]
       (cond
        (= n 1) 1 
         (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
         true     (+ 1 (memoized-chain (/ n 2)))))))

但是，我真正想做的是了解惰性序列的局限性，并编写一个如下所示的函数:

(def lazy-chain
     (letfn [(chain [n] (lazy-seq
                         (cons (if (odd? n)
                                 (+ 1 (nth lazy-chain (dec (+ 1 (* 3 n)))))
                                 (+ 1 (nth lazy-chain (dec (/ n 2)))))
                               (chain (+ n 1)))))]
       (chain 1)))

从中提取元素将导致 n>2 的堆栈溢出，如果您考虑为什么需要在 n=3 处“展望 future ”才能知道惰性列表中第十个元素的值，这是可以理解的因为 (+ 1 (* 3 n)) = 10。

由于惰性列表的开销比内存少得多，我想知道这种事情是否可以通过更延迟的评估或排队来实现？

Answer 1

“展望 future ”的 seq

展望 future 的时髦序列示例可能如下所示:

(def funky-seq
     (let [substrate (atom ())]
       (letfn [(funk [n] (delay (if (odd? n) n @(nth @substrate (inc n)))))]
         (reset! substrate (map funk (range))))
       (map deref @substrate)))

user> (take 10 funky-seq)
(1 1 3 3 5 5 7 7 9 9)

(给那些在不破坏它的情况下让这个变得更简单的人的cookie。:-))

当然，如果确定一个元素的值可能涉及查看一个“ future ”元素，而该元素本身依赖于另一个元素，而该元素需要计算更远的元素......，那么灾难就无法避免了。

欧拉14

问题中的代码试图采用的“展望 future ”方案的基本问题放在一边，这种方法并不能真正解决问题，因为，如果您决定从 1 开始 并向上，您需要考虑分支:Collat​​z 链中的 10 可能通过应用任一规则(n/2 规则应用于 20 或从 3 开始的 3n + 1 规则)。另外，如果您希望向上构建链，则应该颠倒规则，乘以 2 或减去 1 再除以 3 (在每一步中应用产生整数的规则——或者可能两者都产生，如果两者都产生)。

当然，您可以构建一棵树，而不是一个惰性列表，但这看起来与问题中的代码草图完全不同，我希望您最终能够记住东西。

以上内容是为了说明您可能猜测哪个“链构建规则”可能会生成从 1 开始的最长链，同时最终条目保持在下面给定的限制。如果是这种情况，您可能应该证明它是正确的，然后直接实现它(通过从 1< 开始的 loop/recur/);没有证据，你就不能真正声称已经解决了问题。