Clojure:避免Erathosthene筛子中的堆栈溢出？

Question

这是我在Clojure中实现的Erathosthene筛选(基于关于流的SICP课程):

(defn nats-from [n]
  (iterate inc n))

(defn divide? [p q]
  (zero? (rem q p)))

(defn sieve [stream]
  (lazy-seq (cons (first stream)
            (sieve (remove #(divide? (first stream) %) 
               (rest stream))))))

(def primes (sieve (nats-from 2)))

现在,当我拿到前100个素数时,一切都好了:

(take 100 primes)

但是,如果我尝试采用前1000个素数,因为堆栈溢出而导致程序中断.我想知道是否有可能改变某种功能筛选成尾递归,并且仍然保留算法的"流"？

任何帮助???

Answer 1

首先,这不是Eratosthenes的筛子......详情请参阅我的评论.

其次,为近距离投票道歉,因为你的问题不是我指出的那个问题的实际重复......我的不好.

对正在发生的事情的解释

不同之处当然在于您正在尝试构建增量筛,其中remove调用的范围是无限的,因此不可能只是doall围绕它.解决方案是从我最近经常链接的论文中实现一个"真正的"增量SoE - Melissa E. O'Neill的Eratosthenes真正的筛子.

这种特别beatiful Clojure的筛的实施已被写入由Christophe大,并可在这里所有的钦佩谁可能会感兴趣.强烈推荐阅读.

至于问题的根源,我最初认为你的问题是包含对你有用的解释的重复:看到这里和这里.再次,抱歉轻率投票结束.

为什么尾递归无济于事

由于这个问题特别提到将筛分函数作为一种可能的解决方案进行尾递归,我想我会在这里解决这个问题:变换惰性序列的函数通常不应该是尾递归的.

这是一个非常重要的要点,要记住许多无经验的Clojure(或Haskell)程序员.原因是必需的尾递归函数只有在"准备好"时才返回其值 - 在计算的最后.(迭代过程可以在任何特定迭代结束时返回一个值或继续下一次迭代.)相反,生成一个惰性序列的函数应该立即返回一个惰性序列对象,该对象封装了一些代码.可以要求在需要时产生序列的头部或尾部.

因此,堆叠延迟转换问题的答案不是使任何尾递归,而是合并转换.在这种特殊情况下,可以通过使用自定义方案根据优先级队列或映射融合过滤操作来获得最佳性能(有关详细信息,请参阅上述文章).