使用lazy-seq而不吹栈:是否可以将懒惰与尾递归结合起来？

Question

为了学习Clojure,我正在4clojure解决问题.我目前正在问题164,在那里你要枚举(部分)DFA接受的语言.一个有趣的条件是语言可能是无限的,因此解决方案必须是懒惰的(在这种情况下,解决方案的测试用例)(take 2000 ....

我有一个可以在我的机器上运行的解决方案,但是当我在网站上提交它时,它会炸掉堆栈(如果我增加可接受的字符串数量,从2000到20000确定,我也在本地吹掉堆栈,所以这是一个我解决方案的不足之处).

我的解决方案[1]是:

(fn [dfa]
  (let [start-state (dfa :start)
        accept-states (dfa :accepts)
        transitions (dfa :transitions)]
    (letfn [
      (accept-state? [state] (contains? accept-states state))

      (follow-transitions-from [state prefix]
          (lazy-seq (mapcat 
            (fn [pair] (enumerate-language (val pair) (str prefix (key pair))))
            (transitions state))))

      (enumerate-language [state prefix]
        (if (accept-state? state) 
          (cons prefix (follow-transitions-from state prefix))
          (follow-transitions-from state prefix)))
      ]   
      (enumerate-language start-state ""))
  )
)

它接受DFA

'{:states #{q0 q1 q2 q3}
              :alphabet #{a b c}
              :start q0
              :accepts #{q1 q2 q3}
              :transitions {q0 {a q1}
                            q1 {b q2}
                            q2 {c q3}}}

并返回DFA接受的语言(#{a ab abc}).但是,在确定第一个2000接受的DFA字符串时

(take 2000 (f '{:states #{q0 q1} 
                           :alphabet #{0 1}
                           :start q0
                           :accepts #{q0}
                           :transitions {q0 {0 q0, 1 q1} 
                                         q1 {0 q1, 1 q0}}}))

它吹了堆栈.显然我应该将解决方案重组为尾递归,但我不明白这是怎么回事.特别是,我看不出它是如何甚至可以用懒惰尾递归合并(通过两种recur或trampoline).该lazy-seq函数创建一个闭包,因此使用recurinside lazy-seq将使用闭包作为递归点.在lazy-seq内部使用时recur,lazy-seq始终会对其进行求值,因为会recur发出需要评估其参数的函数调用.

在使用时trampoline,我看不出如何迭代地构建一个可以延迟评估其元素的列表.因为我已经使用它并且看到它被使用,trampoline所以只能在它最终完成时返回一个值(即其中一个trampolining函数不返回函数).

其他解决方案被认为超出了范围

我认为这个4Clojure问题的另一种解决方案超出了这个问题的范围.我正在使用一个解决方案iterate,其中每个步骤仅计算字符串'下一步'(从当前状态转换后)接受,因此它根本不会递归.然后,您只跟踪当前状态和使您进入该状态的字符串(这些是下一个状态的前缀).在这种情况下证明困难的是检测接受有限语言的DFA何时不再返回任何结果.我还没有为take-while周围设计一个合适的停止标准iterate,但我很确定我会设法让这个解决方案起作用.对于这个问题,我对基本问题很感兴趣:懒惰和尾递归是否可以合并,还是根本不可能？

[1]请注意,有网站上的一些限制,如不能够使用def和defn,这可以解释我的代码一些特殊性.

Answer 1

使用时lazy-seq只需进行常规函数调用而不是使用recur.懒惰避免了recur否则使用的递归堆栈消耗.

例如,简化版repeat:

(defn repeat [x]
  (lazy-seq (cons x (repeat x))))

Answer 2

问题是你正在构建的东西看起来像：

(mapcat f (mapcat f (mapcat f ...)))

原则上这很好，但是这个列表最右边的元素很长一段时间都没有被实现，当你真正意识到它们时，它们有一大堆惰性序列，需要按顺序强制执行获得单个元素。

如果您不介意剧透，可以在https://gist.github.com/3124087查看我的解决方案。我做的两件事与你不同，而且都很重要：

1. 广度优先遍历树。如果这是非接受状态，您不想“卡在”从 q0 到 q0 的循环中。对于您失败的特定测试用例来说，这似乎不是问题，因为转换传递给您的顺序不同，但此后的下一个测试用例确实具有该特征。
2. 用于doall强制我正在懒惰地构建的序列。因为我知道很多concat人会构建一个非常大的堆栈，而且我也知道序列永远不会是无限的，所以我在构建它时强制执行整个操作，以防止导致堆栈溢出的惰性序列分层。

编辑：一般来说，您不能将惰性序列与尾递归结合起来。您可以拥有一个同时使用这两个元素的函数，当在添加单个元素之前需要完成更多工作时，可能会重复出现，而当有新元素时，可能会重复出现，但大多数时候，它们都有相反的目标并尝试组合如果不小心的话，只会带来痛苦，而不会带来特别的改善。